Эвристика ближайшего соседа для задачи коммивояжера на Java

Question

Я хочу написать Java-программу, которая решает проблему коммивояжера с помощью эвристики ближайшего соседа.Шаги алгоритма будут выглядеть примерно так:

Шаг 1. Начните с любой случайной вершины, назовите ее текущей вершиной

Шаг 2. Найдите ребро, дающее минимальное расстояние между текущей вершиной.и непосещенную вершину, назовите ее V

Шаг 3: Теперь установите эту текущую вершину в непосещенную вершину V и отметьте эту вершину V как посещенную

Шаг 4: Завершите условие, если все вершиныпосещаются по крайней мере один раз

Шаг 5: перейдите к шагу 2

У меня есть проблемы, чтобы выяснить, какие структуры данных будут подходить для решения этой проблемы.Как я могу определить узел с наименьшим расстоянием до текущего узла (шаг 2)?Будет ли приоритетной очередью хорошим выбором?Какие еще структуры данных я могу использовать?Как я могу убедиться, что второй последний узел в туре соединяется с начальным узлом?Должен ли я использовать стек?Что еще я мог бы использовать?

Answer 1

Для того, чтобы найти коммивояжера с оптимальным (лучшим) решением, вам нужно будет сгенерировать все возможные пути на вашем графике и найти путь с наименьшей стоимостью (наименьшая сумма ребер между вершинами).Подход к ближайшему соседу, который вы описываете, близок к использованию жадных алгоритмов .Предполагая, что у вас есть n вершин в вашем графе и каждая вершина связана, вы можете решить задачу коммивояжера, используя подход жадной стратегии / ближайшего соседа, выполнив следующие действия (предположим, что у вас есть Set из Vertex объектов класса):

1. Создание Set исходных не посещенных вершин.
2. Создание Map подобно Map<Vertex, Integer>, где ключом является начальная вершина, а значением является общая стоимость пути.
3. Создайте Map с ключом, который является начальной вершиной пути, и значение List<Vertex>, которое представляет путь (Map<Vertex, List<Vertex>>).
4. Выберите одну случайную вершину, которая не была выбрана ранее (присутствует в Set форме, шаг 1).
5. Выберите вершину, ближайшую к вершине, выбранной на шаге 4 (вам нужно будет проверить стоимость ребер для всех не посещенных вершин и выбрать наименьшую из них).Добавьте вершину к List<Vertex>, связанному с ключом, который является текущей начальной вершиной (выбранной на шаге 4) и сохранен в Map, созданном на шаге 3. ( Примечание : здесь вы будете принимать во внимание все разные вершинычем вершина, выбранная на шаге 4).
6. Увеличение значения стоимости пути, связанного с текущей стартовой вершиной, выбранной на шаге 4, которая сохраняется в Map, созданном на шаге 2.
7. Повторшаги 5-6 до тех пор, пока не останется вершины, которую нужно посетить, проверив ближайший край к текущей последней вершине (вам нужно будет посетить все вершины, начиная с вершины, выбранной на шаге 4).
8. Удалить начальную вершину, выбраннуюна шаге 4 создайте форму Set, созданную на шаге 1.
9. Повторяйте шаги 4-8, пока у вас не останется вершин для выбора на шаге 4.

Затем вы сможете отсортировать Map создан на шаге 2 по значению и выберите запись с наименьшей стоимостью.Затем вы можете получить его ключ и выбрать путь из Map, созданного на шаге 2 ранее выбранным ключом, что связано с наименьшей общей стоимостью.Это будет лучший путь, рассчитанный по этому алгоритму.