Оптимизация построения кольцевых маршрутов в почтовой связи

H2=0

Полученную  таблицу не требуется приводить по строкам и столбцам.  Найдем Θ(i,j) и выберем максимальную.

 

j i	1	3	4	6
1	∞	0	0	0
2	5	0	2	∞
3	0	∞	0	2
4	1	0	∞	3

 

 

 

 

Ɵ(1,3)=0+0=0

Ɵ(1,4)=0+0=0

Ɵ(1,6)=2+0=2

Ɵ(2,3)=2+0=2

Ɵ(3,1)=1+0=1

Ɵ(3,4)=0+0=0

Ɵ(4,3)=1+0=1

 

МаксимальнаяΘ(1,6), соответственно вычеркиваем 1-ю строку и 6-ой столбец. Так как в новой таблице отсутствует клетка (j,i), соответствующая обратному переезду, то в виде графика изображаем часть кольцевого маршрута.

 

1. 6

  ∞

 

2. 5

 

По вершинам уже включенным в маршрут видно: если в клетку (2,1) не поставить бесконечность, то не исключено получение подцикла.

 

 

j i	1	3	4
2	∞	0	2
3	0	∞	0
4	1	0	∞

H3=0

 

Полученную  таблицу не требуется приводить по строкам и столбцам.  Найдем Θ(i,j) и выберем максимальную.

 

j i	1	3	4
2	∞	0	2
3	0	∞	0
4	1	0	∞

 

Ɵ(2,3)=2+0=2

Ɵ(3,1)=1+0=1

Ɵ(3,4)=2+0=2

Ɵ(4,3)=1+0=1

 

МаксимальнаяΘ(2,3), соответственно вычеркиваем 2-ю строку и 3-ий столбец. Так как в новой таблице отсутствует клетка (j,i), соответствующая обратному переезду, то в виде графика изображаем часть кольцевого маршрута.

 

 

 

 

 

2                 3

 

                           1

 

5                 6

 

 

 

По вершинам уже включенным в маршрут видно: если в клетку (3,1) не поставить бесконечность, то не исключено получение подцикла.

 

j i	1	4
3	∞	0
4	1	∞

 

Полученную матрицу следует  привести по строкам, так как там  нет 0.

 

j i	1	4	min
3	∞	0	0
4	1	∞	1

 

Полученная матрица.

 

j i	1	4
3	∞	0
4	0	∞

H4=1

 

В результате имеем кольцевой  маршрут протяженностью L

 

 

 

 

Вывод. Найденный кольцевой маршрут от вершины (6,5) является оптимальным, поскольку нет ни одной свободной вершины (от которой можно продолжить ветвление) с нижней границей меньше, чем нижняя граница у последней вершины найденного кольцевого маршрута (42).

 

 

 

 

 

 

 

 

 

 

 

 

 

41

 

 

44 41

 

 

 

 

 

 

44 41

 

 

 

 

 

 

43 41

 

 

 

 

 

 

 

43 42-1

 

 

 

 

 

 

∞ 41