Построение и анализ алгоритмов. Алгоритмы на графах. МОД в задаче коммивояжёра. (Лекция 6.2)

1. Построение и анализ алгоритмов

Лекция 6.2
Раздел: Алгоритмы на графах
Тема лекции:
Часть 2.
Минимальное остовное дерево (МОД) как
приближение в задаче коммивояжёра
01.03.2015
МОД в задаче коммивояжёра
1

2. МОД как приближение в задаче коммивояжёра

На лекции 2 рассматривались приближённые алгоритмы
решения задачи коммивояжёра (ЗК):
• АБС – алгоритм ближайшего соседа
• АВБГ – алгоритм включения ближайшего города
Если рассматривается евклидов (частный) случай ЗК, то
существуют оценки отклонения стоимости приближённого
решения от стоимости точного решения.
Евклидова ЗК:
Матрица стоимостей {Cij}:
(а) симметрична
(б) удовлетворяет неравенству треугольника
Cij Cik + Ckj , i, j, k
01.03.2015
МОД в задаче коммивояжёра
2

3. Более точная терминология

Лучше (более точно) называть это задачей коммивояжёра с
неравенством треугольника (ЗКНТ)
На плоскости при использовании евклидова расстояния неравенство
треугольника выполняется (но есть и другие случаи с НТ)
vi pi ( xi , yi )
Cij ( xi x j ) 2 ( yi y j ) 2
Если стоимости вычисляются как евклидово расстояние, то это и есть
евклидова задача коммивояжёра (ЕЗК).
Т.о. оценки верны в случае ЗКНТ и в т.ч. в евклидовом случае.
01.03.2015
МОД в задаче коммивояжёра
3

4. Оценка степени приближения алгоритмов АБС и АВБГ в евклидовом случае

Nn – маршрут АБС, Nn – его длина (стоимость).
In – маршрут АВБГ, In – его длина (стоимость).
On – оптимальный маршрут, On – его длина (стоимость).
Nn 1
2 ( log 2 n 1).
On
In
2
On
Было ранее без доказательства.
01.03.2015
МОД в задаче коммивояжёра
4

5. Новое: Приближённый алгоритм двойного обхода МОД при решении ЗК

1)Для заданного графа ЗКНТ построить МОД
2)Начиная с любой вершины обойти по рёбрам МОД все
вершины, «спрямляя пути» при возвратах к уже
посещённым вершинам, и вернуться в стартовую вершину
Другие формулировки п.2:
2’) Сделать двойной обход МОД. В списке пройденных
вершин вычеркнуть повторения (оставить первые
вхождения).
2”) Обойти МОД в прямом порядке, фиксируя первые
посещения вершин.
01.03.2015
МОД в задаче коммивояжёра
5

6. Пример

Граф
4
1
10
2
5
2
12
3
5
2
10
3
18
6
4
12
8
16
6
18
16
2
5
10
18
6
10
6
16
6
4
1
8
6
Граф и МОД
18
4
16
5
4
4
14
14
МОД
4
1
6
2
5
6
4
4
3
2
18
5
01.03.2015
6
= 4 + 6 + 6 + 4 + 18 + 5 = 43
МОД в задаче коммивояжёра
6

7.

= 4 + 6 + 6 + 4 + 18 + 5 = 43
10
4
1
2
6
6
6
4
4
6
3
18
4
16
5
10
4
14
4
2
6
6
4
4
3
10
5
2
4
1
2
10
6
6
4
4
5
01.03.2015
2
10
16
6
3
2
12
8
6
6
2
5
6
5
10
18
6
= 2 + 4 + 10 + 6 + 4 + 18 = 44
1
2
16
18
1
12
8
6
5
2
5
3
2
5
4
1
3
18
18
4
16
= 2 + 6 + 6 + 4 + 10 + 5 = 33
МОД в задаче коммивояжёра
5
4
14
7

8. Оценка приближения алгоритма двойного обхода МОД (АДО МОД)

Пусть
On – оптимальный маршрут, On – его длина (стоимость);
OДn – остовное дерево, OДn – его длина (стоимость);
МOДn – минимальное остовное дерево, МOДn – его
стоимость;
Мn – маршрут АДО МОД, Мn – его стоимость.
Оценка:
Mn
2
On
01.03.2015
МОД в задаче коммивояжёра
8

9. Доказательство оценки

Пусть есть оптимальный маршрут (цикл) On .
Удалим одно из рёбер этого цикла – получим ОДn .
При этом On OДn МOДn .
В силу неравенства треугольника и смысла АДО МОД
имеем 2 МOДn Мn .
Из неравенств 2 On 2 МOДn и 2 МOДn Мn
следует, что 2 On Мn , т.е.
Mn
2
On
01.03.2015
МОД в задаче коммивояжёра
9

10. Другие примеры АДО МОД

1
4
1
4
5
5
2
6
2
7
6
7
3
3
8
8
МОД графа
Граф (вершины)
01.03.2015
МОД в задаче коммивояжёра
10

11. Пример (продолжение)

1
1
4
4
5
2
6
3
5
7
2
6
7
3
8
МОД графа
01.03.2015
8
Двойной обход МОД графа
МОД в задаче коммивояжёра
11

12. Пример (продолжение)

1
1
4
4
5
5
2
6
2
7
6
7
3
3
8
8
Двойной обход МОД графа
Маршрут в ЗК.
Приближение АДО МОД.
Стоимость = 19.074
01.03.2015
МОД в задаче коммивояжёра
12

13.

1
1
4
4
5
2
6
5
7
3
2
6
7
3
8
8
Оптимальный маршрут.
Если начать АДО МОД с вершины 7,
то можно получить …
Стоимость = 14.715
Меньше, чем АДО МОД, на 23%.
01.03.2015
МОД в задаче коммивояжёра
13

14.

КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
01.03.2015
МОД в задаче коммивояжёра
14