Задача коммивояжера
| Категория реферата: Рефераты по экономике
| Теги реферата: конспект по русскому, титульный лист реферата
| Добавил(а) на сайт: Jarkin.
Предыдущая страница реферата | 1 2 3 4 5 6 7 8 9 10 11 | Следующая страница реферата
Вначале обсудим свойство спрямления. Рассмотрим какую-нибудь цепь, например, на рис.5. Если справедливо неравенство треугольника, то d[1,3]£d[1,2]+d[2,3] и d[3,5]£d[3,4]+d[4,5] Сложив эти два неравенства, получим d[1,3]+d[3,5]£d[1,2]+d[2,3]+d[3,4]+d[4,5]. По неравенству треугольника получим. d[1,5]£d[1,3]+d[3,5]. Окончательно
d[1,5]£ d[1,2]+d[2,3]+d[3,4]+d[4,5]
Итак, если справедливо неравенство треугольника, то для каждой цепи верно, что расстояние от начала до конца цепи меньше (или равно) суммарной длины всех ребер цепи. Это обобщение расхожего убеждения, что прямая короче кривой.
Вернемся к ЗК и опишем решающий ее деревянный алгоритм.
Построим на входной сети ЗК кратчайшее остовное дерево и удвоим все его ребра. Получим граф G – связный и с вершинами, имеющими только четные степени.
Построим эйлеров цикл G, начиная с вершины 1, цикл задается перечнем вершин.
Просмотрим перечень вершин, начиная с 1, и будем зачеркивать каждую вершину, которая повторяет уже встреченную в последовательности. Останется тур, который и является результатом алгоритма.
Пример 1. Дана полная сеть, показанная на рис.5. Найти тур жадным и деревянным алгоритмами.
|
- |
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
- |
6 |
4 |
8 |
7 |
14 |
|
2 |
6 Рекомендуем скачать другие рефераты по теме: изложение по русскому 6 класс, деньги реферат. Категории:Предыдущая страница реферата | 1 2 3 4 5 6 7 8 9 10 11 | Следующая страница реферата Поделитесь этой записью или добавьте в закладки |
|
Главная