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

return 
shortestPath;
}
public static void 
main(String[] args) {
Map> vtDistances = Map.
of
(
"Rutland", Map.
of
(
"Burlington", 67,
"White River Junction", 46,

---

9.2. Задача коммивояжера
255
"Bennington", 55,
"Brattleboro", 75),
"Burlington", Map.
of
(
"Rutland", 67,
"White River Junction", 91,
"Bennington", 122,
"Brattleboro", 153),
"White River Junction", Map.
of
(
"Rutland", 46,
"Burlington", 91,
"Bennington", 98,
"Brattleboro", 65),
"Bennington", Map.
of
(
"Rutland", 55,
"Burlington", 122,
"White River Junction", 98,
"Brattleboro", 40),
"Brattleboro", Map.
of
(
"Rutland", 75,
"Burlington", 153,
"White River Junction", 65,
"Bennington", 40));
TSP tsp = 
new 
TSP(vtDistances);
String[] shortestPath = tsp.findShortestPath();
int 
distance = tsp.pathDistance(shortestPath);
System.
out
.println("The shortest path is " +
Arrays.
toString
(shortestPath) + " in " + distance + " miles.");
}
}
Наконец,.мы.можем.перебрать.методом.грубой.силы.все.города.Вермонта.и.най-
ти.кратчайший.путь.через.заданные.пять.городов..Результат.работы.программы.
должен.выглядеть.примерно.так,.а.лучший.путь.показан.на.рис..9.3.
9.2.2. Переходим на следующий уровень
У.задачи.коммивояжера.нет.простого.решения..По.мере.увеличения.количества.
городов.наивный.подход.быстро.становится.нереальным..Количество.генериру-
емых.перестановок.равно.факториалу.от.
n
.(
n
!),.где.
n
.—.количество.городов.в.за-
даче..Если.бы.мы.добавили.еще.один.город.и.их.стало.не.пять,.а.шесть,.то.число.
оцененных.маршрутов.увеличилось.бы.в.шесть.раз..А.при.добавлении.еще.одного.
города.решить.задачу.стало.бы.в.семь.раз.сложнее..Этот.подход.не.масштабируется!
В.реальном.мире.наивный.подход.к.задаче.коммивояжера.используется.крайне.
редко..Большинство.алгоритмов.для.различных.вариаций.этой.задачи.с.большим.
количеством.городов.—.приближенные..Они.пытаются.получить.решение,.близкое.
к.оптимальному..Оно.может.находиться.в.пределах.небольшой.заранее.известной.
полосы,.к.которой.принадлежит.идеальное.решение.(возможно,.такие.решения.
будут.меньше.чем.на.5.%.менее.эффективными,.чем.идеальное).

---