Битонический путь

Рис 1.

На плоскости даны n точек. Обойти эти точки по одному разу и вернутся в точке x¹, причем обойти таким образом чтобы длина была минимум.

Определение:

Битонический путь – замкнутый путь проходящий по одному разу через любую точку и обладает свойством :

Эта задача – частный случай задачи Гамильтонова контура Путь : <1,3,5,4,6,8,7,2,1> – длина

Найти битонический путь минимальной суммарной длины

<1,i₂, …,i_k , … , i_n-1 , i_n,1> = µ

Эта задача решается методом динамического программирования .

Рассмотрим часть пути на множестве вершин

Пусть путь имеющий саммую маленкую длину имеет :

- промежуткий путь проходящий 1...j

Случаи :

1. Часть путь , соединяется так же будет кратчайщей

–кратчай.

2. 

3. 

Пусть µ - оптимальный путь на множестве вершин - µ(1,j).

Пусть - предпоследняя вершина предшествует вершину j

если

если

При этом часть пути µ( ) такая является Оптимальной

Доказательство :

Длина кратчайшей пути :

чем хотя бы одно слагаеммых пе оптимальной то что приводят противоречи то - оптимальной.

- длина оптимальной пути .

Эта формула рассмотряется только для

Пример

Для графа в рис 1.

1 1 2 2 2 2 3 3 7 4 4 6 5 4 10 6 6 2 7 8 10 8 9 11

Построим матрицу M , используем метрику

Аналогично получаем М

	2	3	4	5	6	7	8
1	1.0	6.1	7.5	11.5	19.8	28.0	29.4
2		6.4	7.8	11.8	20.0	28.3	29.7
3			10.9	14.9	23.1	31.3	32.8
4				14.0	22.3	30.5	31.9
5					15.8	24.0	25.5
6						19.8	21.2
7							29.1

Матрица S

	2	3	4	5	6	7	8
1	1	2	3	4	5	6	7
2		1	3	4	5	6	7
3			2	4	5	6	7
4				3	5	6	7
5					2	6	7
6						5	7
7							5

Орт = m[7,8] + 30.6

Битонический путь : 1 3 4 5 8 7 6 2 1

Записать схему динамического программирования «снизу-вверх» и процедур выдачи на печать оптимального решения :

Вход

Выход :

1. 

2. 

3. 

4. 

5. 

6. 

7. 

8. 

9. 

10. 

11. 

12. 

13. 

14. 

Процердур выдачи на печать Бетонический путь.

Вход :

Выход : на печать

1. 

2. 

3. Печать(st , n, st1)

1. 

2. 

3. 

4. 

5. 

6. 

7. 

8. 

9. 

10. 

11. 

12.