Computer Science на языке Java 2022 Дэвид Копец Классические задачи Computer Science на языке Java 2022 ббк

254
Глава 9.
Другие задачи
Поиск методом грубой силы
Теперь.мы.можем.сгенерировать.все.перестановки.для.списка.городов,.но.это.не.
совсем.то.же.самое,.что.путь.для.задачи.коммивояжера..Напомню,.что.в.задаче.
о.коммивояжере.продавец.должен.в.конце.вернуться.в.тот.город,.с.которого.начал..
Мы.можем.легко.добавить.расстояние.от.последнего.города,.в.котором.побывал.
продавец,.до.города,.который.он.посетил.первым,.когда.вычислим,.какой.путь.
кратчайший..Теперь.мы.готовы.проверить.все.сгенерированные.пути..Поиск.
методом.грубой.силы.просматривает.каждый.путь.в.списке.и,.используя.рассто-
яние.между.двумя.городами.в.таблице.поиска.(
distances
),.вычисляет.суммарное.
расстояние.для.каждого.пути..Функция.выводит.кратчайший.путь.и.суммарное.
расстояние.для.него.(листинг.9.7).
Листинг 9.7. 
TSP.java (продолжение)
public int 
pathDistance(String[] path) {
String last = path[0];
int 
distance = 0;
for 
(String next : Arrays.
copyOfRange
(path, 1, path.length)) {
distance += distances.get(last).get(next);
// расстояние, чтобы вернуться из последнего города в первый
last = next;
}
return 
distance;
}
public 
String[] findShortestPath() {
String[] cities = distances.keySet().toArray(String[]::
new
);
List paths = 
permutations
(cities);
String[] shortestPath = 
null
;
int 
minDistance = Integer.
MAX_VALUE
; // произвольное большое число
for 
(String[] path : paths) {
int 
distance = pathDistance(path);
// необходимо добавить расстояние от последнего города до первого
distance += distances.get(path[path.length — 1]).get(path[0]);
if 
(distance < minDistance) {
minDistance = distance;
shortestPath = path;
}
}
// добавим первый город в конец и вернемся
shortestPath = Arrays.
copyOf
(shortestPath, shortestPath.length + 1);
shortestPath[shortestPath.length — 1] = shortestPath[0];