Методы разработки алгоритмов: задача коммивояжера

Дисциплина «Алгоритмы и структуры данных» Лекция № 16 Методы разработки алгоритмов: задача коммивояжера. Филатов Вячеслав Валерьевич к.т.н., доцент кафедры КБ-2 «Прикладные информационные технологии» Методы разработки алгоритмов. • • • • • "разделяй и властвуй" (декомпозиции) динамическое программирование "жадные" методы (эвристика) локальный поиск поиск с возвратом (переборные схемы решения) Методы разработки алгоритмов. • "разделяй и властвуй" (декомпозиции) метод предполагает такую декомпозицию (разбиение) задачи размера п на более мелкие задачи, что на основе решений этих более мелких задач становится возможным получение решение исходной задачи Примеры: сортировка слиянием, решение задачи о ханойских башнях, составление расписания теннисного турнира, перемножение длинных целых и т.п. • • • • динамическое программирование "жадные" методы локальный поиск поиск с возвратом Табличный метод декомпозиции • • • • • • Рассмотрим составление расписания проведения теннисного турнира по круговой схеме для n = 2* игроков. Каждый игрок должен сыграть со всеми другими игроками, при этом каждый игрок должен играть по одному матчу в день в течение n - 1 дней — минимального количества дней, необходимых для проведения всего турнира. Расписание проведения турнира, таким образом, представляет собой таблицу, состоящую из п строк и n — 1 столбцов; элементом на пересечении строки i и столбца j является номер игрока, с которым игрок i должен провести матч в j-й день. Метод декомпозиции позволяет составить расписание для половины игроков. Это расписание составляется на основе рекурсивного применения данного алгоритма для половины этой половины игроков и т.д. Когда дня"базовая ситуация", в которой мы просто количество игроков будет сокращено до двух,Номер возникнет 1 2 встреч 3 между 4 6 7 устанавливаем ними. 5 Номер порядок проведения Допустим, в турнире восемь Расписание 1-48заполняет верхний левый угол 1 участвуют 2 3 игроков. 4 5 6для игроков 7 игрока (4 строки х З столбца) Нижний левый угол 2 составляемого 1 4 расписания. 3 6 7 8 (4 строки 5 х З столбца) этого расписания должен свести между собой игроков с более высокими номерами (5 - 8). Эта часть расписания 4 1 4 к каждому 2 7элементу8 в верхнем 5 левом6 углу. получается путем3прибавления числа 3 задачу. 2 Теперь 1 остается 8 свести5между собой 6 7 Итак, нам удалось4упростить игроков с низкими и более высокими номерами. Сделать это нетрудно: надо на 4-й день свести в пары игроков, имеющих номера 1 — 5 6 7 8 1 4 3 2 4, с игроками 5-8 соответственно, переставлять номера 5 — 8. 6 5 8а в последующие 7 2дни просто 1 циклически 4 3 Описанный алгоритм позволяет составить расписание для игроков при любом значении k. 7 8 8 7 5 6 6 5 3 4 2 3 1 2 4 1 Табличный метод декомпозиции Метод декомпозиции позволяет составить расписание для половины игроков. Это расписание составляется на основе рекурсивного применения данного алгоритма для половины этой половины игроков и т.д. Когда количество игроков будет сокращено до двух, возникнет "базовая ситуация", в которой мы просто устанавливаем порядок проведения встреч между ними. • Допустим, в турнире участвуют восемь игроков. Расписание для игроков Номер дня 1-4 заполняет верхний левый угол5 (4 строки х7 З столбца) составляемого 1 2 3 4 6 расписания. Нижний левый угол (4 строки х З столбца) этого расписания Номер 1 2 3 4 5 6 7 8 2 3 4 должен свести между собой игроков с более высокими номерами (5 8). игрока 2 1 4 3 6 7 8 5 1 4 3 Эта 3часть расписания получается числа 4 к каждому 4 1 2 7 8путем5 прибавления 6 4 1 2 4 2 1 8 5 6 7 элементу в3верхнем левом углу. 3 2 1 5 6 7 8 1 4 3 2 • Итак, нам удалось упростить задачу. Теперь остается свести +2между +2 собой +2 6 5 8 7 2 1 4 3 игроков с низкими и более высокими номерами. Сделать это нетрудно: 7 8 5 6 3 2 1 4 надо8 на 4-й7день6свести в пары игроков, имеющих номера 1 — 4, с 5 4 3 2 1 игроками 5-8 последующие +4 соответственно, +4 +4 +4 а в+4 +4 +4 дни просто циклически 2 переставлять номера 5 — 8. • Описанный алгоритм позволяет составить расписание для игроков при любом значении k. 1 • Табличный метод декомпозиции • • • • • • Рассмотрим составление расписания проведения теннисного турнира по круговой схеме для n = 2* игроков. Каждый игрок должен сыграть со всеми другими игроками, при этом каждый игрок должен играть по одному матчу в день в течение n - 1 дней — минимального количества дней, необходимых для проведения всего турнира. Расписание проведения турнира, таким образом, представляет собой таблицу, состоящую из п строк и n — 1 столбцов; элементом на пересечении строки i и столбца j является номер игрока, с которым игрок i должен провести матч в j-й день. Метод декомпозиции позволяет составить расписание для половины игроков. Это расписание составляется на основе рекурсивного применения данного алгоритма для половины этой половины игроков и т.д. Когда Номер дня "базовая ситуация", в которой мы просто количество игроков будет сокращено до двух, возникнет устанавливаем встреч между Номер порядок 2 проведения 3 4 5 ними.6 7 8 Допустим, в турнире участвуют восемь игроков. Расписание для игроков 1-4 заполняет верхний левый угол игрока 1 4 3 6 7 8 5 (4 строки х З столбца) составляемого расписания. Нижний левый угол (4 строки х З столбца) этого 1 собой 2 игроков7 с более высокими 8 5номерами 6 (5 - 8). Эта часть расписания расписания должен4свести между 3 2 числа14 к каждому 8 элементу 5 в верхнем 6 левом 7 углу. получается путем прибавления Итак, нам удалось упростить остается свести с низкими и более 6 7задачу. Теперь 8 1 4 между3собой игроков 2 высокими номерами. Сделать это нетрудно: надо на 4-й день свести в пары игроков, имеющих номера 1 — 5 8 7 2 1 4 3 4, с игроками 5-8 соответственно, а в последующие дни просто циклически переставлять номера 5 — 8. 8 позволяет 5 составить 6 3 2 игроков 1 при любом 4 значении k. Описанный алгоритм расписание для 7 +4 6 +4 5 +4 4 +4 3 +4 2 +4 1 +4 Табличный метод декомпозиции • • • • • • Рассмотрим составление расписания проведения теннисного турнира по круговой схеме для n = 2* игроков. Каждый игрок должен сыграть со всеми другими игроками, при этом каждый игрок должен играть по одному матчу в день в течение n - 1 дней — минимального количества дней, необходимых для проведения всего турнира. Расписание проведения турнира, таким образом, представляет собой таблицу, состоящую из п строк и n — 1 столбцов; элементом на пересечении строки i и столбца j является номер игрока, с которым игрок i должен провести матч в j-й день. Метод декомпозиции позволяет составить расписание для половины игроков. Это расписание составляется на основе рекурсивного применения данного алгоритма для половины этой половины игроков и т.д. Когда количество игроков будет сокращено до двух, возникнет "базовая ситуация", в которой мы просто устанавливаем порядок проведения встреч между ними. Допустим, в турнире участвуют восемь игроков. Расписание для игроков 1-4 заполняет верхний левый угол (4 строки х З столбца) составляемого расписания. Нижний левый угол (4 строки х З столбца) этого расписания должен свести между собой игроков с более высокими номерами (5 - 8). Эта часть расписания получается путем прибавления числа 4 к каждому элементу в верхнем левом углу. Итак, нам удалось упростить задачу. Теперь остается свести между собой игроков с низкими и более высокими номерами. Сделать это нетрудно: надо на 4-й день свести в пары игроков, имеющих номера 1 — 4, с игроками 5-8 соответственно, а в последующие дни просто циклически переставлять номера 5 — 8. Описанный алгоритм позволяет составить расписание для игроков при любом значении k. Задача коммивояжера • Рассмотрим одну знаменитую задачу, для получения оптимального решения которой из всех известных нам алгоритмов подходят лишь алгоритмы полного перебора, время выполнения которых зависит экспоненциально от объема входных данных. Эта задача, которая называется задачей коммивояжера, сводится к поиску в неориентированном графе с весовыми значениями ребер такого маршрута (простого цикла, включающего все вершины), у которого сумма весов составляющих его ребер будет минимальной. Такой маршрут часто называют гамильтоновым циклом. Задача коммивояжера • На рисунке показан граф с шестью вершинами (их часто называют "городами"), который может служить основой для задачи коммивояжера. Заданы координаты каждой вершины, а весом каждого ребра считается его длина. Обратите внимание: мы предполагаем (и такое предположение характерно для задачи коммивояжера), что существуют все ребра графа, т.е. граф является полным. В более общих случаях, когда вес ребер не основывается на евклидовом расстоянии, у ребра может оказаться бесконечный вес, чего в действительности, конечно, не бывает. Какой из этих маршрутов является оптимальным (или, может быть, такого маршрута вообще нет)? Задача коммивояжера • На рисунке показан граф с шестью вершинами (их часто называют "городами"), который может служить основой для задачи коммивояжера. Заданы координаты каждой вершины, а весом каждого ребра считается его длина. Обратите внимание: мы предполагаем (и такое предположение характерно для задачи коммивояжера), что существуют все ребра графа, т.е. граф является полным. В более общих случаях, когда вес ребер не основывается на евклидовом расстоянии, у ребра может оказаться бесконечный вес, чего в действительности, конечно, не бывает. S = 50.00 S = 49.73 S = 48.39 S = 49.78 Задача коммивояжера • На рисунке показан граф с шестью вершинами (их часто называют "городами"), который может служить основой для задачи коммивояжера. Заданы координаты каждой вершины, а весом каждого ребра считается его длина. Обратите внимание: мы предполагаем (и такое предположение характерно для задачи коммивояжера), что существуют все ребра графа, т.е. граф является полным. В более общих случаях, когда вес ребер не основывается на евклидовом расстоянии, у ребра может оказаться бесконечный вес, чего в действительности, конечно, не бывает. S = 50.00 S = 49.73 S = 48.39 S = 49.78 Переборные схемы решения: задача коммивояжера • • • Вспомним задачу коммивояжера: мы описали так называемый "жадный алгоритм", позволяющий найти хороший, хотя и необязательно оптимальный, маршрут. Посмотрим, как можно было бы найти оптимальный маршрут путем систематического просмотра всех маршрутов. Это можно было бы сделать, рассмотрев все перестановки узлов и определив маршрут, который проходит через узлы в соответствующей последовательности, учитывая наилучший из найденных до сих пор маршрутов. Время, которое потребуется на реализацию такого подхода на графе с п узлами, равняется О(n!), поскольку необходимо рассмотреть (n - 1)! различных перестановок, а оценка каждой перестановки занимает время О(п). Обратите внимание: нам не нужно рассматривать все п! перестановок, поскольку исходный пункт маршрута не имеет значения. Следовательно, мы можем рассматривать только те перестановки, которые начинаются с 1. Переборные схемы решения: задача коммивояжера • Построим начало дерева решений: Переборные схемы решения: задача коммивояжера - метод ветвей и границ • Рассмотрим несколько иной подход, который в наихудшем случае оказывается ничуть не лучше описанного выше, однако в среднем — в сочетании с методом ветвей и границ, который мы далее кратко рассмотрим, — позволяет получить ответ намного быстрее, чем метод "перебора всех перестановок". Построение дерева начинается с корня, который представляет все маршруты. Маршруты соответствуют уже упоминавшимся выше "конфигурациям". Каждый узел имеет двух сыновей, и маршруты, которые представляет узел, делятся этими сыновьями на две группы: которые содержат определенное ребро и у которых такого ребра нет. Переборные схемы решения: задача коммивояжера • – ограничения эвристик Допустим, требуется определить нижнюю границу для всех решений задачи коммивояжера. Примем во внимание, что стоимость любого маршрута можно вычислить как половину суммы по всем узлам n стоимости пар ребер этого маршрута, инцидентных с узлом n. Из этого замечания можно вывести следующее правило. Сумма стоимости двух ребер, инцидентных узлу n и входящих в маршрут, не может быть меньше суммы двух ребер наименьшей стоимости, инцидентных узлу n. Таким образом, ни один из маршрутов не может стоить меньше, чем половина суммы по всем узлам n стоимости двух ребер наименьшей стоимости, инцидентных узлу n. • На данном графе мера расстояний между вершинами не является евклидовой, т.е. она никоим образом не связана с расстоянием на плоскости между городами, соединенными ребром. Такой мерой стоимости может служить, например, время в пути или плата за проезд. В данном случае ребрами с наименьшей стоимостью, инцидентными узлу а, являются (a, d) и (а, b) с суммарной стоимостью 5. Для узла b такими ребрами являются (а, b) и (b, е) с суммарной стоимостью, равной 6. Аналогично, суммарная стоимость двух ребер с наименьшей стоимостью, инцидентных узлам с, d и е, равняется соответственно 8, 7 и 9. Нижняя граница стоимости маршрута составит, таким образом, (5+6+8+7+9)/2=17.5 Спасибо за внимание!