Cài đặt code bài toán người du lịch cài đặt bằng C++, Java
Bài toán người du lịch: Một nguời du lịch muốn đi tham quan n thành phố T1,T2…, Tn . Xuất phát từ một thành phố nào đó, người du lịch muốn đi qua tất cả các thành phố còn lại, mỗi thành phố đi qua duy nhất 1 lần rối quay trở trở lại thành phố xuất phát.
Gọi Cij là chi phí đi từ thành phố Ti đến Tj . Hãy tìm một hành trình thỏa yêu cầu bài toán sao cho chi phí là nhỏ nhất.
Hãy cùng Lập trình không khó đi giải quyết bài toán này nhé các bạn
Code bài toán người du lịch
Chúng ta sẽ lưu ma trận chi phí đi từ Ti đến Tj là a[i][j]. Như vậy, tại đường chéo của ma trận thì chi phí sẽ bằng 0. Giả sử với ma trận sau:
|
1 2 3 4 5 |
int graph[4][4] = { {0, 10, 15, 20}, {10, 0, 35, 25}, {15, 35, 0, 30}, {20, 25, 30, 0} }; |
Chúng ta giả sử có 4 thành phố: T0, T1, T2, T3. Như vậy thì hàng đầu tiên là chi phí đi từ T0 đến T0, T1, T2, T3 lần lượt là 0, 10, 15, 20. Tương tự với các hàng phía sau.
Lưu ý: cost = 999999 ngầm hiểu ở đây là khai báo giá trị cost khởi tạo là vô cùng lớn.
Source code C/C++:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
/* * C++ Program to Implement Traveling Salesman Problem using Nearest neighbour Algorithm */ #include<stdio.h> #include<conio.h> #include<iostream> using namespace std; int c = 0,cost = 999999; int graph[4][4] = { {0, 10, 15, 20}, {10, 0, 35, 25}, {15, 35, 0, 30}, {20, 25, 30, 0} }; void swap (int *x, int *y) { int temp; temp = *x; *x = *y; *y = temp; } void copy_array(int *a, int n) { int i, sum = 0; for(i = 0; i <= n; i++) { sum += graph[a[i % 4]][a[(i + 1) % 4]]; } if (cost > sum) { cost = sum; } } void permute(int *a, int i, int n) { int j, k; if (i == n) { copy_array(a, n); } else { for (j = i; j <= n; j++) { swap((a + i), (a + j)); permute(a, i + 1, n); swap((a + i), (a + j)); } } } int main() { int i, j; int a[] = {0, 1, 2, 3}; permute(a, 0, 3); cout<<"minimum cost:"<<cost<<endl; getch(); } |
> Lời giải tham khảo tại: sanfoundry.com
Kết quả chạy:
|
1 |
minimum cost:80 |
Source code Java:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
import java.util.InputMismatchException; import java.util.Scanner; import java.util.Stack; public class TSPNearestNeighbour { private int numberOfNodes; private Stack<Integer> stack; public TSPNearestNeighbour() { stack = new Stack<Integer>(); } public void tsp(int adjacencyMatrix[][]) { numberOfNodes = adjacencyMatrix[1].length - 1; int[] visited = new int[numberOfNodes + 1]; visited[1] = 1; stack.push(1); int element, dst = 0, i; int min = Integer.MAX_VALUE; boolean minFlag = false; System.out.print(1 + "\t"); while (!stack.isEmpty()) { element = stack.peek(); i = 1; min = Integer.MAX_VALUE; while (i <= numberOfNodes) { if (adjacencyMatrix[element][i] > 1 && visited[i] == 0) { if (min > adjacencyMatrix[element][i]) { min = adjacencyMatrix[element][i]; dst = i; minFlag = true; } } i++; } if (minFlag) { visited[dst] = 1; stack.push(dst); System.out.print(dst + "\t"); minFlag = false; continue; } stack.pop(); } } public static void main(String... arg) { int number_of_nodes; Scanner scanner = null; try { System.out.println("Enter the number of nodes in the graph"); scanner = new Scanner(System.in); number_of_nodes = scanner.nextInt(); int adjacency_matrix[][] = new int[number_of_nodes + 1][number_of_nodes + 1]; System.out.println("Enter the adjacency matrix"); for (int i = 1; i <= number_of_nodes; i++) { for (int j = 1; j <= number_of_nodes; j++) { adjacency_matrix[i][j] = scanner.nextInt(); } } for (int i = 1; i <= number_of_nodes; i++) { for (int j = 1; j <= number_of_nodes; j++) { if (adjacency_matrix[i][j] == 1 && adjacency_matrix[j][i] == 0) { adjacency_matrix[j][i] = 1; } } } System.out.println("the citys are visited as follows"); TSPNearestNeighbour tspNearestNeighbour = new TSPNearestNeighbour(); tspNearestNeighbour.tsp(adjacency_matrix); } catch (InputMismatchException inputMismatch) { System.out.println("Wrong Input format"); } scanner.close(); } } |
> Lời giải tham khảo tại : sanfoundry.com
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
$javac TSPNearestNeighbour.java $java TSPNearestNeighbour Enter the number of nodes in the graph 9 Enter the adjacency matrix 000 374 200 223 108 178 252 285 240 356 374 000 255 166 433 199 135 095 136 017 200 255 000 128 277 128 180 160 131 247 223 166 128 000 430 047 052 084 040 155 108 433 277 430 000 453 478 344 389 423 178 199 128 047 453 000 091 110 064 181 252 135 180 052 478 091 000 114 083 117 285 095 160 084 344 110 114 000 047 078 240 136 131 040 389 064 083 047 000 118 356 017 247 155 423 181 117 078 118 000 the citys are visited as follows 1 5 3 2 9 7 4 6 8 |
