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

private final 
Map> distances;
public 
TSP(Map> distances) {
this
.distances = distances;
}
public static 
 
void 
swap(T[] array, 
int 
first, 
int 
second) {
T temp = array[first];
array[first] = array[second];
array[second] = temp;
}
Перебор всех вариантов
Наивный.подход.к.решению.задачи.коммивояжера.требует.сгенерировать.все.
возможные.варианты.перестановок.городов..Существует.множество.алгоритмов.
генерации.перестановок,.они.довольно.просты,.так.что.вы.почти.наверняка.смо-
жете.придумать.такой.алгоритм.самостоятельно.
Один.из.типичных.подходов.—.поиск.с.возвратом..Впервые.он.встретился.нам.
в.главе.3.в.контексте.решения.задачи.с.ограничениями..При.решении.такой.за-
дачи.поиск.с.возвратом.используется.после.того,.как.найдено.частичное.решение,.
которое.не.удовлетворяет.ограничениям.задачи..В.таком.случае.вы.возвращаетесь.
к.более.раннему.состоянию.и.продолжаете.поиск.по.пути,.отличному.от.того,.
который.привел.к.частично.неверному.решению.
Найти.все.перестановки.элементов.списка.(в.частности,.наших.городов).можно.
также.с.помощью.поиска.с.возвратом..Чтобы.после.перестановки.элементов.
перейти.к.последующим.перестановкам,.можно.вернуться.к.состоянию,.предше-
ствовавшему.тому,.при.котором.была.выполнена.перестановка,.и.выбрать.другую.
комбинацию.для.перехода.по.другому.пути.(листинг.9.5).
Данная.рекурсивная.функция.отмечена.как.«помощник»,.так.как.на.самом.деле.
она.будет.вызываться.другой.функцией,.которая.принимает.меньше.аргументов..
Параметры.
allPermutationsHelper()
.—.это.начальная.перестановка,.с.которой.

---

9.2. Задача коммивояжера
253
мы.работаем,.перестановки,.сгенерированные.на.данный.момент,.и.количество.
оставшихся.элементов.для.обмена.