Методы программирования и прикладные алгоритмы. Учебное пособие СанктПетербург 2007
 Скачать 2.32 Mb.
|
|
y c b a z x b x b x y x b y i j k s t c is c kj c kt c jt a) ) ) ) ) Рис. 4.24. Построение подоптимального маршрута для задачи коммивояжера 162 шаге (рис. 4.24, б ) допустим, что ближайшим к городу b является город x. Включим город x в объезд, при этом снова разрывается одно из ребер оптимального маршрута. На рис. 4.24, в и г показа- но включение третьего города y в объезд. Рис. 4.24, д показывает в общем виде включение очередного города, ближайшего к уже построенному маршруту, помеченному жирными линиями, в объ- езд. Из каждой вершины, уже вошедшей в объезд, могут отходить участки пути, оставшиеся от оптимального маршрута. При вклю- чении очередного города t между городами j и k, помимо исклю- чения ребра (j, k) со стоимостью c jk исключаем одно ребро (i, s) оптимального пути, имеющее стоимость c is . Для доказательства теоремы нужно показать, что вносим в объезд стоимость, не более чем в два раза большую, чем стоимость удаляемого оптимального ребра. При включении города t увеличиваем стоимость объезда на ∆ = c kt + c jt − c kj (4.23) Так как стоимости удовлетворяют правилу треугольника, можем оценить c jt − c kj ≤ c kt (4.24) Кроме этого, c jt ≤ c is , (4.25) иначе, в соответствии с алгоритмом включения города, ближай- шего к объезду, на этом шаге включался бы город s, а не t. Тогда, из (4.23)–(4.25) получаем ∆ ≤ 2c jt ≤ 2c is Таким образом, после включения n городов, стоимость полу- ченного объезда будет составлять T (n) ≤ 2(O(n) − c 0 ). (4.26) Чтобы стоимость T (n) была ближе к O(n), в качестве c 0 нужно выбрать ребро оптимального объезда с максимальной стоимостью c max 163 2 1 8 4 3 5 а) 7 6 1 1 1 1 1 1 1 1 2 1 3 6 4 8 ) 5 7 1 2 2 2 1 2 2 2 Рис. 4.25. Оптимальный и подоптимальный маршруты для задачи коммивояжера Оценку теоремы 4.2 нельзя улучшить, так как можно приве- сти пример, в котором выражение (4.26) выполняется со знаком равенства. Пример 4.6 Рассмотрим граф, задаваемый матрицей стоимостей c ij = min{|i − j|, n − |i − j|}. Для случая n = 8 получим матрицу C = 1 2 3 4 5 6 7 8 1 −∞ 1 2 3 4 3 2 1 2 1 −∞ 1 2 3 4 3 2 3 2 1 −∞ 1 2 3 4 3 4 3 2 1 −∞ 1 2 3 4 5 4 3 2 1 −∞ 1 2 3 6 3 4 3 2 1 −∞ 1 2 7 2 3 4 3 2 1 −∞ 1 8 1 2 3 4 3 2 1 −∞ Эта матрица симметрична, и удовлетворяет неравенству тре- угольника. Оптимальный объезд для такой матрицы стоимости легко получить, он изображен на рис. 4.25, а, его стоимость равна 8. Применив алгоритм включения ближайшего города в объезд, получим маршрут, показанный на рис. 4.25, б. Его стоимость рав- на 14, и с учетом c max = 1 получим, что выполняется равенство (4.26) 14 = 2(8 − 1). 164 библиографический список 1. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. 536 с. 2. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. М.: Изд. дом «Вильямс», 2003. 384 с. 3. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М.: Мир, 1998. 703 c. 4. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. М.: Мир, 1981. 368 c. 5. Кнут Д. Искусство программирования. М.: Изд. дом «Ви- льямс», 2005. Т. 1–3. 6. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. МЦНМО, 2004. 960 с. 7. Крук Е. А., Семенов С. В., Трояновский Б. К., Федоренко С. В. Рекуррентные уравнения. / ГААП. СПб., 1997. 24 с. 8. Крук Е. А., Овсянников Е. П., Семенов С. В., Федоренко С. В. Исчерпывающий поиск. / ГААП. СПб., 1997. 32 с. 9. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алго- ритмы. Теория и практика. М.: Мир, 1980. 476 с. 165 Учебное издание Крук Евгений Аврамович Овчинников Андрей Анатольевич МЕТОДЫ ПРОГРАММИРОВАНИЯ И ПРИКЛАДНЫЕ АЛГОРИТМЫ Учебное пособие Редактор А. В. Семенчук Подписано к печати 30.03.07. Формат бумаги 60 × 84 1/16. Бумага офсетная. Печать офсетная. Усл. печ. л. 9,64. Уч.-изд. л. 10. Тираж 150 экз. Заказ № Отпечатано с оригинал-макета, подготовленного кафедрой безопасности информационных систем Санкт-Петербургского государственного университета аэрокосмического приборостроения Редакционно-издательский центр ГУАП 190000, Санкт-Петербург, Б. Морская ул., 67 |