Пример (задача 3_1)

Пример (задача 3_1)

Пять булочных небольшого городка обслуживает хлебобулочный комбинат, который, арендуя пять автомобилей, ежедневно поставляет в каждую булочную заказанную продукцию, причем объем продукции всегда соответствует максимальной загрузке автомобиля (таким образом, использование одного авто для попутной доставки в несколько булочных исключается). Специалист отдела логистики лично проехал между всеми этими объектами и занес в таблицу реальное расстояние между i-й и j-й булочными (если между ними есть дорога): т. о. были учтена дорожная ситуация. Найти оптимальный путь от комбината к каждой из булочных. Критерий: минимизация расходов на транспортировку, соответствующих пройденному расстоянию. Рассчитать минимально возможные ежедневные расходы комбината на транспорт, если учитывается только эксплуатации груженого автотранспорта (от комбината до булочной).

В составленной специалистом таблице под №6 указан сам хлебобулочный комбинат.

	1	2	3	4	5	6
1	0	5	4	12	1	нет
2	5	0	3	10	6	13
3	4	3	0	6	13	22
4	1	8	8	0	6	12
5	4	9	3	8	0	10
6	нет	13	24	14	20	0

Пример решения задачи 3.1

Инициализация:

(i=6, metka[6]=1):

№элемента	1	2	3	4	5	6
Массив Metka	0	0	0	0	0	1
Массив Pred_num	6	6	6	6	6	6
Массив Curr_dist	нет	13	24	14	20	0

Общий шаг:

Запускаем цикл от 1 до 5.

1.  Возьмем наиболее близкую к нужной и еще неотмеченную вершину, это вершина №2 (j=2)

1.1.Пометим ее как рассмотренную metka[2]:=1

1.2.В цикле по k от 1 до 6 сравним d[i,j]+d[j,k] и d[i,k], т. е. в данном случае curr_dist[2]+d[2,k] и curr_dist[k] (иными словами здесь сравнивается кратчайший из известных путей 2 от вершины 6 через вершину №2 к остальным вершинам и прямой путь от вершины №6 к остальным, т. е. на первом шаге тот, что был первоначально записан в матрице D)

при k=1: curr_dist[2]+d[2,1]=13+5=18, curr_dist[1]=¥, 18<¥ Þ 18 Þ curr_dist[1]:=18, pred_num[1]:=2

при k=2: curr_dist [2]+d[2,2]=13+0=13, curr_dist [2]=13 Þ никаких изменений

при k=3: curr_dist [2]+d[2,3] =13+3=16, curr_dist [3]=24, 16<24 Þ curr_dist[3]:=16, pred_num [3]:=2

при k=4: curr_dist [2]+d[2,4] =13+10=23, curr_dist [4]=14 Þ никаких изменений

при k=5: curr_dist [2]+d[2,5] =13+6=19, curr_dist [5]=20, 19<20 Þ curr_dist[5]:=17, pred_num [5]:=2

при k=6: curr_dist [2]+d[2,6] =13+13=26, curr_dist [6]=0 Þ никаких изменений

№элемента	1	2	3	4	5	6
Массив Metka	0	1	0	0	0	1
Массив Pred_num	2	6	2	6	2	6
Массив Curr_dist	18	13	16	14	17	0

2.  Возьмем наименьшую из неотмеченных вершин, это №4 (j=4)

2.1.Пометим ее как рассмотренную metka[4]:=1

2.2.В цикле по k от 1 до 6 сравним curr_dist[4]+d[4,k] и curr_dist[k] (иными словами здесь сравниваются наименьшие из известных путей от вершины 6 через вершину №4 к остальным вершинам и наиболее короткий известный путь от №6 к остальным)

при k=1: curr_dist [4]+d[4,1] =14+1=15, curr_dist [1]=18 Þ curr_dist [1]:=15, pred_num [1]:=4

при k=2: curr_dist [4]+d[4,2] =14+8=22, curr_dist [2]=13 Þ никаких изменений

при k=3: curr_dist [4]+d[4,3] =14+8=22, curr_dist [3]=16 Þ никаких изменений

при k=4: curr_dist [4]+d[4,4] =14+0=14, curr_dist [4]=14 Þ никаких изменений

при k=5: curr_dist [4]+d[4,5] =14+6=20, curr_dist [5]=17 Þ никаких изменений

при k=6: curr_dist [4]+d[4,6] =14+12=26, curr_dist [6]=0 Þ никаких изменений

№элемента	1	2	3	4	5	6
Массив Metka	0	1	0	1	0	1
Массив Pred_num	4	6	2	6	2	6
Массив Curr_dist	15	13	16	14	17	0

3.  Возьмем неотмеченную вершину, теперь это вершина №1 (j=1)

3.1.Пометим ее как рассмотренную metka[1]:=1

3.2.В цикле по k от 1 до 6 сравним curr_dist [1]+d[1,k] и curr_dist [k] (иными словами здесь сравниваются наименьшие из известных путей от вершины 6 через вершину №1 к остальным вершинам и наиболее короткий известный путь от №6 к остальным)

при k=1: curr_dist [1]+d[1,1] =15+0=15, curr_dist [1]=15 Þ никаких изменений

при k=2: curr_dist [1]+d[1,2] =15+5=20, curr_dist [2]=13 Þ никаких изменений

при k=3: curr_dist [1]+d[1,3] =15+4=19, curr_dist [3]=16 Þ никаких изменений

при k=4: curr_dist [1]+d[1,4] =15+12=27, curr_dist[4]=14 Þ никаких изменений

при k=5: curr_dist [1]+d[1,5] =15+1=16, curr_dist [5]=17 Þ curr_dist [5]:=16, pred_num [5]:=1

при k=6: curr_dist [1]+d[1,6] =15+¥=¥, curr_dist [6]=0 Þ никаких изменений

№элемента	1	2	3	4	5	6
Массив Metka	1	1	0	1	0	1
Массив Pred_num	4	6	2	6	1	6
Массив Curr_dist	15	13	16	14	16	0

4.  Возьмем неотмеченную вершину, например №5 (j=5)

4.1.Пометим ее как рассмотренную metka[5]:=1

4.2.В цикле по k от 1 до 6 сравним curr_dist [5]+d[5,k] и curr_dist [k] (иными словами здесь сравниваются наименьшие из известных путей от вершины 6 через вершину №5 к остальным вершинам и наиболее короткий известный путь от №6 к остальным)

при k=1: curr_dist [5]+d[5,1] =16+4=20, curr_dist [1]=15 Þ никаких изменений

при k=2: curr_dist [5]+d[5,2] =16+9=25, curr_dist [2]=13 Þ никаких изменений

при k=3: curr_dist [5]+d[5,3] =16+3 =19, curr_dist [3]=16 Þ никаких изменений

при k=4: curr_dist [5]+d[5,4] =16+8=24, curr_dist [4]=14 Þ никаких изменений

при k=5: curr_dist [5]+d[5,5] =16+0=16, curr_dist [5]=16 Þ никаких изменений

при k=6: curr_dist [5]+d[5,6] =16+¥=¥, curr_dist [6]=0 Þ никаких изменений

№элемента	1	2	3	4	5	6
Массив Metka	1	1	0	1	1	1
Массив Pred_num	4	6	2	6	1	6
Массив Curr_dist	15	13	16	14	16	0

5.  Возьмем последнюю вершину №3 (j=3)

5.1.Пометим ее как рассмотренную metka[3]:=1

5.2. Очевидно, что поскольку в массиве curr_dist путей больше 16 не осталось, тогда как curr_dist[3]=16, то дальнейшее улучшение результата невозможно.

№элемента	1	2	3	4	5	6
Массив Metka	1	1	1	1	1	1
Массив Pred_num	4	6	2	6	1	6
Массив Curr_dist	15	13	16	14	16	0

Вывод:

Путь от 6 до 1: pred_num[1]=4, pred_num[4]=6, pred_num[6]=0. Длина=curr_dist[1]=15. Сам путь (6,4,1).

Путь от 6 до 2: pred_num[2]=6, pred_num[6]=0. Длина=curr_dist[2]=13. Сам путь (6,2).

Путь от 6 до 3: pred_num[3]=2, pred_num[2]=6, pred_num[6]=0. Длина=curr_dist[3]=16. Сам путь (6,2,3).

Путь от 6 до 4: pred_num[4]=6, pred_num[6]=0. Длина=curr_dist[4]=14. Сам путь (6,4).

Путь от 6 до 5: pred_num[5]=1, pred_num[1]=4, pred_num[4]=6, pred_num[6]=0. Длина=curr_dist[5]=16. Сам путь (6,4,1,5).