Лаб 4 / Лаб 4
.docxЛабораторная работа №4
Решение задачи о коммивояжере
Постановка задачи. Пусть имеется n пунктов и задана матрица c={cij} расстояний между ними. Выезжая из одного пункта, коммивояжер должен побывать во всех пунктах по одному и только по одному разу и вернуться в исходный пункт. Требуется определить: в каком порядке следует объезжать пункты, чтобы суммарное пройденное расстояние было бы минимальным (найти минимальный полный замкнутый маршрут).
Вариант 6
Пусть имеется восемь пунктов, взаимные расстояния между которыми представлены в таблице:
-
i\j
1
2
3
4
5
6
7
8
1
-
34
57
18
49
35
64
34
2
34
-
26
50
25
42
20
74
3
57
26
-
50
38
28
53
72
4
18
50
50
-
54
46
59
59
5
49
25
38
54
-
18
61
43
6
35
42
28
46
18
-
65
70
7
64
20
53
59
61
65
-
26
8
34
74
72
59
43
70
26
-
Требуется:
- определить в каком порядке следует объезжать пункты, чтобы суммарное пройденное расстояние было бы минимальным;
- сравнить результат решения поставленной задачи с результатами её решения при условии, что имеет место запрет на коммуникации между пунктами (1-4), (3-6), и (6-7), а длина пути между пунктами по направлению (1-6), (4-2), (4-5), (8-3) и (2-8) уменьшена на 12 км.
-
i\j
1
2
3
4
5
6
7
8
1
-
34
57
-
49
23
64
34
2
34
-
26
38
25
42
20
62
3
57
26
-
50
38
-
53
60
4
-
38
50
-
42
46
59
59
5
49
25
38
42
-
18
61
43
6
23
42
-
46
18
-
-
70
7
64
20
53
59
61
-
-
26
8
34
62
60
59
43
70
26
-
Рис. 1 – Ответ на первое задание
Рис. 2 – Ответ на второе задание
Листинг кода:
import java.util.Arrays;
class TSPBruteForce {
private static int[][] graph;
private static int[] path;
private static int minCost = Integer.MAX_VALUE;
public static void tsp(int[] currentPath, boolean[] visited, int currentCost, int n, int pos) {
if (pos == n) {
if (graph[currentPath[pos - 1]][0] != 0) {
int cost = currentCost + graph[currentPath[pos - 1]][0];
if (cost < minCost) {
minCost = cost;
path = Arrays.copyOf(currentPath, n);
}
}
return;
}
for (int i = 1; i < n; i++) {
if (!visited[i] && graph[currentPath[pos - 1]][i] != 0) {
visited[i] = true;
currentPath[pos] = i;
tsp(currentPath, visited, currentCost + graph[currentPath[pos - 1]][i], n, pos + 1);
visited[i] = false;
}
}
}
public static void main(String[] args) {
/* graph = new int[][]{{0, 34, 57, 18, 49, 35, 64, 34},
{34, 0, 26, 50, 25, 42, 20, 74},
{57, 26, 0, 50, 38, 28, 53, 72},
{18, 50, 50, 0, 54, 46, 59, 59},
{49, 25, 38, 54, 0, 18, 61, 43},
{35, 42, 28, 46, 18, 0, 65, 70},
{64, 20, 53, 59, 61, 65, 0, 26},
{34, 74, 72, 59, 43, 70, 26, 0},
};*/
graph = new int[][]{{0, 34, 57, 10000, 49, 23, 64, 34},
{34, 0, 26, 38, 25, 42, 20, 62},
{57, 26, 0, 50, 38, 10000, 53, 60},
{10000, 38, 50, 0, 42, 46, 59, 59},
{49, 25, 38, 42, 0, 18, 61, 43},
{23, 42, 10000, 46, 18, 0, 100000, 70},
{64, 20, 53, 59, 61, 100000, 0, 26},
{34, 92, 60, 59, 43, 70, 26, 0},
};
int n = graph.length;
path = new int[n];
path[0] = 0; // Начинаем с вершины 0
boolean[] visited = new boolean[n];
visited[0] = true; // Вершина 0 посещена
tsp(path, visited, 0, n, 1);
System.out.println("Minimum TSP Cost: " + (minCost));
System.out.print("TSP Path: 1 ");
boolean vav = true;
for (int i : path) {
if (vav) {
vav = false;
continue;
}
System.out.print("-> " + (i + 1) + " ");
}
System.out.println("-> 1");
}
}