Метод ближайшего соседа

Алгоритм решения включает следующие шаги.

1 шаг. Выбрать первую вершину.

2 шаг. Для выбранной вершины найти наиболее близкую к ней. Если данная вершина уже вошла в маршрут, то она блокируется, и выбирается следующая по степени близости.

3 шаг. Повторять шаг 2 до тех пор, пока маршрут (путь) не пройдет через все вершины.

4 шаг. Выбрать вторую вершину и повторить шаги 2–3.

5 шаг. Процесс считается законченным, когда гамильтоновы контуры построены для всех вершин, выбранных в качестве начальных.

6 шаг. Рассчитать длину каждого из полученных маршрутов и выбрать минимальное значение.

Задача

Решить задачу коммивояжера со следующей матрицей расстояний.

Символ ¥ на главной диагонали означает фактический запрет на переход вида i ® i (из города в него же).

Решение

Решение задачи начнем с рассмотрения первой вершины в качестве начальной. Наиболее близкой к ней вершиной является четвертая. Расстояние между первым и четвертым городом 8 км. Наиболее близкой к четвертой вершине является пятая и шестая. Так как данные вершины еще не входили в маршрут, то далее следует рассматривать два варианта.

10 5

8

1 4

10 6

Для пятой вершины наиболее близкой является первая, которая уже вошла в маршрут. Поэтому выбираем следующую по близости вершину – третью. Для шестой вершины ближайшим соседом является вторая, которую и выбираем для проходящего через нее пути.

1 7

9

10 5 3

1 4

10 6 2

Ближайшей к третьей вершине является шестая (первая, четвертая и пятая вошли в путь). Ко второй – третья (четвертая и шестая вошли в маршрут).

1 4 5

1 13

9 13 4 15

10 5 3 6

1 4

3 7

10 6 2 3

5 3

4 6

Следующей по степени близости к шестой вершине является вторая; к третьей – пятая. Данные вершины были последними в цепи городов, которые необходимо посетить, поэтому для создания замкнутого маршрута вернемся в первый город.

1 4 5

1 13 13 4

9 15 3 21

10 5 3 6 2 1

1 4

3 7 4 7

10 6 2 3 5 1

4 6

Суммарное расстояние для пути:

1 – 4 – 5 – 3 – 6 – 2 – 1 Z = 8 + 10 + 9 + 15 + 3 + 21 = 64 км.

1 – 4 – 6 – 2 – 3 – 5 – 1 Z = 8 + 10 + 3 + 7 + 4 + 7 = 39 км.

Для других вершин замкнутые контуры построены на рисунках.

2 6 2 4 5 6

а)

3 10 10 8 9 11

3 8 10 7 12 19

2 6 4 5 1 3 2

Суммарное расстояние:

2 – 6 – 4 – 5 – 1 – 3 – 2 Z = 3 + 8 + 10 + 7 + 12 + 19 = 59 км.

б) 5 4 6

10 5 3

4 7 8 10 3 7

3 5 1 4 6 2 3

Суммарное расстояние:

3 – 5 – 1 – 4 – 6 – 2 – 3 Z = 4 + 7 + 8 + 10 + 3 + 7 = 39 км.

в)

4 5 2 4

8 9 3 8

10 7 10 3 11 13

4 5 1 2 6 3 4

Суммарное расстояние:

4 – 5 – 1 – 2 – 6 – 3 – 4 Z = 10 + 7 + 10 + 3 +11 + 13 = 54 км.

г) 4 6

5 3

10 3 7 4 7 8

4 6 2 3 5 1 4

Суммарное расстояние:

4 – 6 – 2 – 3 – 5 – 1 – 4 Z = 10 + 3 + 7 + 4 + 7 + 8 = 39 км.

д)

5 4 6

10 5 3

7 8 10 3 7 4

5 1 4 6 2 3 5

Суммарное расстояние:

5 – 1 – 4 – 6 – 2 – 3 – 5 Z = 7 + 8 + 10 + 3 + 7 + 4 = 39 км.

е)

6 6 2 4 5 6

3 10 10 8 9 11

3 5 10 7 12 15

6 2 4 5 1 3 6

Суммарное расстояние:

6 – 2 – 4 – 5 – 1 – 3 – 6 Z = 3 + 5 + 10 + 7 + 12 + 15 = 52 км.

Оптимальными маршрутами следования будут:

1 – 4 – 6 – 2 – 3 – 5 – 1;

3 – 5 – 1 – 4 – 6 – 2 – 3;

4 – 6 – 2 – 3 – 5 – 1 – 4;

5 – 1 – 4 – 6 – 2 – 3 – 5.

Для всех этих маршрутов общее расстояние обхода всех городов является минимальным и составляет 39 км.

Не нашли, что искали? Воспользуйтесь поиском: