Алгоритм ближайшего соседа
Формулируется следующим образом:
Пункты обхода плана последовательно включаются в маршрут, причем, каждый очередной включаемый пункт должен быть ближайшим к последнему выбранному пункту среди всех остальных, ещё не включенных в состав маршрута.
Алгоритм прост в реализации, быстро выполняется, но, как и другие «жадные» алгоритмы, может выдавать неоптимальные решения.
Рассмотрим для примера сеть на рисунке, представляющую узкий ромб.
Пусть коммивояжер стартует из города 1. Алгоритм “иди в ближайший город” выведет его в город 2, затем 3, затем 4; на последнем шаге придется платить за жадность, возвращаясь по длинной диагонали ромба. В результате получится не кратчайший, а длиннейший путь.
2.3 Блок-схемы
Рисунок 6 – Блок схема для функции нахождения кратчайшего пути
Рисунок 7 – Блок-схема для функции нахождения контура минимальной длины
2.4 Описание формата входных данных
Пользователь вводит количество вершин, квадратную матрицу и с какой вершины начинаем выполнять алгоритм.
2.5 Описание формата выходных данных
На вывод поступают данные о матрице смежности, расстояниях до вершин и длине контура минимальной длины.
2.6 Описание тестовых данных
Граф для нахождения кратчайшего пути G1(V,E), где V – множество вершин, а E – множество ребер. (Рисунок 8)
Рисунок 8 - Граф для первого задания
Матрица смежности графа G1 приведена в таблице 1.
Таблица 1- Матрица смежности
|
1 |
2 |
3 |
4 |
5 |
6 |
1 |
0 |
1 |
4 |
0 |
2 |
0 |
2 |
0 |
0 |
0 |
9 |
0 |
0 |
3 |
4 |
0 |
0 |
7 |
0 |
0 |
4 |
0 |
9 |
7 |
0 |
0 |
2 |
5 |
0 |
0 |
0 |
0 |
0 |
8 |
6 |
0 |
0 |
0 |
0 |
0 |
0 |
Граф для нахождения кратчайшего пути G2(V,E), где V – множество вершин, а E – множество ребер, представлен на рисунке 9.
Рисунок 9– Граф для второго задания
Матрица смежности графа G2 приведена в таблице 2.
Таблица 2- Матрица смежности
|
1 |
2 |
3 |
4 |
5 |
1 |
0 |
1 |
0 |
0 |
3 |
2 |
0 |
0 |
2 |
3 |
1 |
3 |
0 |
0 |
0 |
1 |
0 |
4 |
0 |
0 |
0 |
0 |
2 |
5 |
3 |
0 |
0 |
0 |
0 |
2.7 Результаты работы программы на тестовых данных
Пользователь вводит количество ребер, далее происходит ввод матрицы смежности на экран. Далее пользователь вводит номер стартовой вершины, от которой будет происходить поиск кратчайших путей до остальных вершин с помощью алгоритма Дейкстры.
После ввода указанных в таблице 1 данных результатом работы программы будут являться кратчайшие пути до вершин. Результат работы программы представлен на рисунке 10.
Рисунок 10 – Работа первой функции
Пользователь вводит количество ребер, далее происходит ввод матрицы смежности на экран. Далее пользователь вводит номер стартовой вершины, от которой будет происходить поиск кратчайших путей до остальных вершин с помощью алгоритма ближайшего соседа.
После ввода указанных в таблице 2 данных результатом работы программы будут являться кратчайшие пути до вершин. Результат работы программы представлен на рисунке 11.
Рисунок 11 – Результат выполнения второго задания