[Baì toán] Tìm đường đi Hamiton ngắn nhất.

[Bài toán] Nhân viên giao bánh piza phải giao bánh cho N khách hàng. Từ cửa hàng bánh , anh ta phải đi giao bánh cho N khách hàng sau đó trở về nhà của mình. Vị trí của của hàng bánh, nhà của anh ta và của khách hàng theo mẫu sau (x,y). Khoảng cách giữa 2 vị trí (x1,y1) và (x2,y2) được tính theo công thức sau: |x1-x2| + |y1-y2|.
Hãy viết chương trình tính đường đi ngắn nhất cho nhân viên trên.
[Input]
Có 10 test case được chứa trong file dữ liệu đầu vào OPTIMALPATH.INP. Dòng đầu ghi số khách hàng N. Dòng sau ghi vị trí (x,y) của văn phòng, nhà của nhân viên và của N khách hàng.
[Output]
Ghi ra file OPTIMALPATH.OUT đường đi ngắn nhất cho mỗi test case. Với mỗi test case được bắt đầu bằng #C.
[I/O example]
5
0 0 100 100 70 40 30 10 10 5 90 70 50 20
6
88 81 85 80 19 22 31 15 27 29 30 10 20 26 5 14
7
22 47 72 42 61 93 8 31 72 54 0 64 26 71 93 87 84 83
8
30 20 43 14 58 5 91 51 55 87 40 91 14 55 28 80 75 24 74 63
9
3 9 100 100 16 52 18 19 35 67 42 29 47 68 59 38 68 81 80 37 94 92
10
39 9 97 61 35 93 62 64 96 39 36 36 9 59 59 96 61 7 64 43 43 58 1 36
10
26 100 72 2 71 100 29 48 74 51 27 0 58 0 35 2 43 47 50 49 44 100 66 96
10
46 25 16 6 48 82 80 21 49 34 60 25 93 90 26 96 12 100 44 69 28 15 57 63
10
94 83 72 42 43 36 59 44 52 57 34 49 65 79 14 20 41 9 0 39 100 94 53 3
10
32 79 0 0 69 58 100 31 67 67 58 66 83 22 44 24 68 3 76 85 63 87 7 86
[Output]
#1 200
#2 304
#3 265
#4 307
#5 306
#6 366
#7 256
#8 399
#9 343
#10 391
Chương trình cài đặt.

#include<iostream>
#define myABS(value) ((value < 0) ? -(value) : (value))
using namespace std;
int matrix[12][12];
int position[12][2];
int minPath;
bool isVisited[12];
int customerNo;
void DFS(int vertice, int pathLength, int verticeCount){
 if(verticeCount == customerNo+1){
  if(pathLength + matrix[vertice][1] < minPath){
   minPath = pathLength + matrix[vertice][1];
  }
  return;
 }
 for(int i=2;i<customerNo+2;i++){
  if(!isVisited[i] && i != vertice && pathLength + matrix[vertice][i] < minPath){
   isVisited[i] = true;
   DFS(i, pathLength + matrix[vertice][i], verticeCount+1);
   isVisited[i] = false;
  }
 }
}
int main(){
 freopen("OPTIMALPATH.INP","r",stdin);
 freopen("OPTIMALPATH.OUT","w", stdout);
 customerNo;
 int tc;
 for(tc=1;tc<=10;tc++){
  cin>>customerNo;
  for(int i=0;i<customerNo + 2;i++){
   cin>>position[i][0]>>position[i][1];
  }
  for(int i=0;i<customerNo+1;i++){
   for(int j=i;j<customerNo+2;j++){
    if(i==j){
     matrix[i][j]=0;
    }else{
     matrix[i][j] = matrix[j][i] =  myABS(position[i][0] - position[j][0]) + myABS(position[i][1] - position[j][1]);
    }
   }
  }
  minPath = 1000000000;
  for(int i=0;i<customerNo+2;i++) isVisited[i] = false;
  isVisited[0] = true;
  DFS(0,0,1);// office's index.
  cout<<"#"<<tc<<" "<<minPath<<endl;
  
 }

 return 0;
}

Cám ơn bạn đã đọc bài viết này. Hãy chia sẻ bài viết và bình luận ý kiến của bạn ở bên dưới.

Share this

Chào mừng bạn đến với SimpleCodeCJava Blog - Mục đích của chúng tôi khi thành lập blog này là muốn chia sẻ những kiến thức và kinh nghiệm lập trình mà chúng tôi đã học được với mong muốn giúp đỡ mọi người, giúp bạn rút ngắn được thời gian tìm hiểu cũng như việc giải quyết những vấn đề trong lập trình C và Java.