Метод ветвей и границ. Решение задачи о коммивояжере - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Метод ветвей и границ. Решение задачи о коммивояжере, слайд №1

Метод ветвей и границ. Решение задачи о коммивояжере, слайд №2

Метод ветвей и границ. Решение задачи о коммивояжере, слайд №3

Метод ветвей и границ. Решение задачи о коммивояжере, слайд №4

Метод ветвей и границ. Решение задачи о коммивояжере, слайд №5

Метод ветвей и границ. Решение задачи о коммивояжере, слайд №6

Метод ветвей и границ. Решение задачи о коммивояжере, слайд №7

Метод ветвей и границ. Решение задачи о коммивояжере, слайд №8

Метод ветвей и границ. Решение задачи о коммивояжере, слайд №9

Метод ветвей и границ. Решение задачи о коммивояжере, слайд №10

Метод ветвей и границ. Решение задачи о коммивояжере, слайд №11

Метод ветвей и границ. Решение задачи о коммивояжере, слайд №12

Метод ветвей и границ. Решение задачи о коммивояжере, слайд №13

Метод ветвей и границ. Решение задачи о коммивояжере, слайд №14

Метод ветвей и границ. Решение задачи о коммивояжере, слайд №15

Метод ветвей и границ. Решение задачи о коммивояжере, слайд №16

Метод ветвей и границ. Решение задачи о коммивояжере, слайд №17

Метод ветвей и границ. Решение задачи о коммивояжере, слайд №18

Метод ветвей и границ. Решение задачи о коммивояжере, слайд №19

Метод ветвей и границ. Решение задачи о коммивояжере, слайд №20

Метод ветвей и границ. Решение задачи о коммивояжере, слайд №21

Метод ветвей и границ. Решение задачи о коммивояжере, слайд №22

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Метод ветвей и границ. Решение задачи о коммивояжере. Доклад-сообщение содержит 22 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

МЕТОД ВЕТВЕЙ И ГРАНИЦ РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ

Слайд 2

Описание слайда:

Вступление В 1859 г. Сэр Вильям Гамильтон, знаменитый математик, давший миру теорию комплексного числа и кватерниона, предложил детскую головоломку, в которой предлагалось совершить «круговое путешествие» по 20 городам, расположенных в различных частях земного шара. Каждый город соединялся дорогами с тремя соседними так, что дорожная сеть образовывала 30 ребер додекаэдра, в вершинах которого находились города a, b, … t. Обязательным условием являлось требование: каждый город за исключением первого можно посетить один раз. Гамильтонова задача о путешественнике нередко преобразуется в задачу о коммивояжере. Коммивояжер - не свободно путешествующий турист, а деловой человек, ограниченный временными, денежными или какими-либо другими ресурсами. Гамильтонова задача может стать задачей о коммивояжере, если каждое из ребер снабдить числовой характеристикой. Это может быть километраж, время на дорогу, стоимость билета, расход горючего и т.д. Таким образом, условные характеристики дадут числовой ряд, элементы которого могут быть распределены между ребрами как угодно.

Слайд 3

Описание слайда:

Рассмотрим задачу о коммивояжере. Рассмотрим задачу о коммивояжере. Имеются n городов, расстояния (стоимость проезда, расход горючего на дорогу и т.д.) между которыми известны. Коммивояжер должен пройти все n городов по одному разу, вернувшись в тот город, с которого начал. Требуется найти такой маршрут движения, при котором суммарное пройденное расстояние (стоимость проезда и т.д.) будет минимальным. задача коммивояжера - это задача отыскания кратчайшего гамильтонова цикла в полном графе. Можно предложить следующую простую схему решения задачи коммивояжера: сгенерировать все n! возможных перестановок вершин полного графа, подсчитать для каждой перестановки длину маршрута и выбрать кратчайший. Однако, n! с ростом n растет быстрее, чем любой полином от n, и даже быстрее, чем . Таким образом, решение задачи коммивояжера методом полного перебора оказывается практически неосуществимым, даже при достаточно небольших n. Существует метод решения задачи коммивояжера, который дает оптимальное решение. Этот метод называется методом ветвей и границ. Решение задачи коммивояжера методом ветвей и границ по-другому называют алгоритмом Литтла. Если считать города вершинами графа, а коммуникации (i,j) - его дугами, то требование нахождения минимального пути, проходящего один и только один раз через каждый город, и возвращения обратно, можно рассматривать как нахождение на графе гамильтонова контура минимальной длины. Для практической реализации идеи метода ветвей и границ применительно к задаче коммивояжера нужно найти метод определения нижних границ подмножества и разбиения множества гамильтоновых контуров на подмножества (ветвление). Определение нижних границ базируется на том утверждении, что если ко всем элементам i-й строки или j-го столбца матрицы C прибавить или отнять число , то задача останется эквивалентной прежней, то есть оптимальность маршрута коммивояжера не изменится, а длина любого гамильтонова контура изменится на данную величину .

Слайд 4

Описание слайда:

Опишем алгоритм Литтла для нахождения минимального гамильтонова контура для графа с n вершинами. Граф представляют в виде матрицы его дуг. Если между вершинами Xi и Xj нет дуги, то ставится символ «?». Опишем алгоритм Литтла для нахождения минимального гамильтонова контура для графа с n вершинами. Граф представляют в виде матрицы его дуг. Если между вершинами Xi и Xj нет дуги, то ставится символ «?». Алгоритм Литтла для решения задачи коммивояжера можно сформулировать в виде следующих правил: 1. Находим в каждой строке матрицы минимальный элемент и вычитаем его из всех элементов соответствующей строки. Получим матрицу, приведенную по строкам, с элементами 2. Если в матрице , приведенной по строкам, окажутся столбцы, не содержащие нуля, то приводим ее по столбцам. Для этого в каждом столбце матрицы выбираем минимальный элемент , и вычитаем его из всех элементов соответствующего столбца. Получим матрицу каждая строка и столбец, которой содержит хотя бы один нуль. Такая матрица называется приведенной по строкам и столбцам. 3. Суммируем элементы и , получим константу приведения которая будет нижней границей множества всех допустимых гамильтоновых контуров, то есть 4. Находим степени нулей для приведенной по строкам и столбцам матрицы. Для этого мысленно нули в матице заменяем на знак «?» и находим сумму минимальных элементов строки и столбца, соответствующих этому нулю. Записываем ее в правом верхнем углу клетки

Слайд 5

Описание слайда:

5. Выбираем дугу , для которой степень нулевого элемента достигает максимального значения 5. Выбираем дугу , для которой степень нулевого элемента достигает максимального значения 6. Разбиваем множество всех гамильтоновых контуров на два подмножества и . Подмножество гамильтоновых контуров содержит дугу , - ее не содержит. Для получения матрицы контуров , включающих дугу , вычеркиваем в матрице строку и столбец . Чтобы не допустить образования негамильтонова контура, заменим симметричный элемент на знак «?». 7. Приводим матрицу гамильтоновых контуров . Пусть - константа ее приведения. Тогда нижняя граница множества определится так 8. Находим множество гамильтоновых контуров , не включающих дугу . Исключение дуги достигается заменой элемента в матрице на ?. 9. Делаем приведение матрицы гамильтоновых контуров . Пусть - константа ее приведения. Нижняя граница множества определится так 10. Сравниваем нижние границы подмножества гамильтоновых контуров и . Если , то дальнейшему ветвлению в первую очередь подлежит множество . Если же , то разбиению подлежит множество .

Слайд 6

Описание слайда:

Процесс разбиения множеств на подмножества сопровождается построением дерева ветвлений. Процесс разбиения множеств на подмножества сопровождается построением дерева ветвлений. 11. Если в результате ветвлений получаем матрицу , то определяем полученный ветвлением гамильтонов контур и его длину. 12. Сравниваем длину гамильтонова контура с нижними границами оборванных ветвей. Если длина контура не превышает их нижних границ, то задача решена. В противном случае развиваем ветви подмножеств с нижней границей, меньшей полученного контура, до тех пор, пока не получим маршрут с меньшей длиной или не убедимся, что такого не существует. 3. Математическая модель задачи коммивояжера Задача коммивояжера может быть сформулирована как целочисленная введением булевых переменных , если маршрут включает переезд из города i непосредственно в город j и в противном случае. Тогда можно задать математическую модель задачи, то есть записать целевую функцию и систему ограничений

Слайд 7

Описание слайда:

условия (2) - (4) в совокупности обеспечивают, что каждая переменная равна или нулю, или единице. При этом ограничения (2), (3) выражают условия, что коммивояжер побывает в каждом городе один раз в него прибыв (ограничение (2)), и один раз из него выехав (ограничение (3)). условия (2) - (4) в совокупности обеспечивают, что каждая переменная равна или нулю, или единице. При этом ограничения (2), (3) выражают условия, что коммивояжер побывает в каждом городе один раз в него прибыв (ограничение (2)), и один раз из него выехав (ограничение (3)). Однако этих ограничений не достаточно для постановки задачи коммивояжера, так как они не исключают решения, где вместо простого цикла, проходящего через n вершин, отыскиваются 2 и более отдельных цикла (подцикла), проходящего через меньшее число вершин. Поэтому задача, описанная уравнениями (2) - (4) должна быть дополнена ограничениями, обеспечивающими связность искомого цикла. Для того, чтобы исключить при постановке задачи все возможные подциклы в систему ограничений задачи включают следующее ограничение: , где , и . 4. Алгоритм решения Дана матрица расстояний, представленная в таблице 1. Необходимо с помощью алгоритма Литтла решить задачу коммивояжера.

Слайд 8

Описание слайда:

Слайд 9

Описание слайда:

1) Справа к таблице присоединяем столбец Ui, в котором записываем минимальные элементы соответствующих строк. Вычитаем элементы Ui из соответствующих элементов строки матрицы. 1) Справа к таблице присоединяем столбец Ui, в котором записываем минимальные элементы соответствующих строк. Вычитаем элементы Ui из соответствующих элементов строки матрицы.

Слайд 10

Описание слайда:

2) Внизу полученной матрицы присоединяем строку Vj, в которой записываем минимальные элементы столбцов. Вычитаем элементы Vj из соответствующих столбцов матрицы.

Слайд 11

Описание слайда:

3) В результате вычислений получаем матрицу, приведенную по строкам и столбцам, которая изображена в виде таблицы 2.

Слайд 12

Описание слайда:

4) Находим константу приведения 4) Находим константу приведения Таким образом, нижней границей множества всех гамильтоновых контуров будет число 5) Находим степени нулей полностью приведенной матрицы. Для этого как бы заменяем в ней все нули на знак «?» и устанавливаем сумму минимальных элементов соответствующей строки и столбца. Степени нулей записаны в правых верхних углах клеток, для которых . 6) Определяем максимальную степень нуля. Она равна 19 и соответствует клетке (1;5). Таким образом, претендентом на включение в гамильтонов контур является дуга (1;5). 7) Разбиваем множество всех гамильтоновых контуров на два: и . Матрицу с дугой (1;5) получаем табл.2 путем вычеркивания строки 1 и столбца 5. Чтобы не допускать образования негамильтонова контура, заменяем элемент (5;1) на знак «?».

Слайд 13

Описание слайда:

Слайд 14

Описание слайда:

8) Матрицу гамильтоновых контуров получим из таблицы 2 путем замены элемента (1;5) на знак «?».

Слайд 15

Описание слайда:

9) Делаем дополнительное приведение матрицы контуров : = 0. Нижняя граница множества равна . 9) Делаем дополнительное приведение матрицы контуров : = 0. Нижняя граница множества равна . 10) Находим константу приведения для множества контуров : Следовательно, нижняя граница множества равна 11) Сравниваем нижние границы подмножеств и . Так как то дальнейшему ветвлению подвергаем множество . На рис.1 представлено ветвление по дуге (1;5). Рис.1 Переходим к ветвлению подмножества . Его приведенная матрица представлена в таблице ниже.

Слайд 16

Описание слайда:

Слайд 17

Описание слайда:

12) Узнаем степени нулей матрицы. Претендентами на включение в гамильтонов контур будут несколько дуг (5;2) и (6;3). Для дальнейших расчетов выберем дугу (6;3). Разбиваем множество на два подмножества: и (табл. 3 и 4). Чтобы не допустить образования негамильтонова контура, в таблице 3 заменяем элемент (3;6) на знак «?» Табл.3

Слайд 18

Описание слайда:

Табл.4

Слайд 19

Описание слайда:

Определим константы приведения для этих матриц , Следовательно , Так как , то дальнейшему ветвлению подлежит подмножество . Находим степени нулей матрицы.

Слайд 20

Описание слайда:

Претендентом к включению в гамильтонов контур станет дуга (3;2). Разбиваем множество на два и .

Слайд 21

Описание слайда:

Очевидно Очевидно , Следовательно, очередному ветвлению нужно подвергнуть подмножество . Переходим к ветвлению подмножества . Определяем степени нулей. Претендентом на включение в гамильтонов контур является дуга (5;4). Разбиваем множество на два подмножества: и . Находим нижние границы , Следовательно, очередному ветвлению нужно подвергнуть подмножество . Но его матрица имеет размерность . Поэтому в гамильтонов контур следует включить дуги, соответствующие в матрице нулевым элементам. Определим полученный гамильтонов контур. В него вошли дуги Длина контура равна Так как границы оборванных ветвей больше длины контура 1 - 5 - 4 - 6 - 3 - 2 - 1, то этот контура имеет наименьшую длину. алгоритм крускал коммивояжер

Слайд 22

Описание слайда:

Выводы Выводы Задача коммивояжера является частичным случаем гамильтоновой задачи о путешественнике. Суть задачи коммивояжера состоит в нахождении суммарной минимальной характеристики (расстояния, стоимости проезда и т.д.), при этом коммивояжер должен пройти все n городов по одному разу, вернувшись в тот город, с которого начал. Существуют несколько методов решения задачи коммивояжера: метод полного перебора, с помощью метода ветвей и границ (алгоритм Литтла), алгоритма Крускала, «деревянного» алгоритма и т.д. Однако только метод ветвей и границ дает нам в итоге самое оптимальное решение. Основная идея метода Литтла состоит в том, что вначале строят нижнюю границу длин маршрутов для всего множества гамильтоновых контуров . Затем все множество контуров разбивают на два подмножества таким образом, чтобы первое подмножество состояло из гамильтоновых контуров, содержащих некоторую дугу (i,j), а другое подмножество не содержало этой дуги. Для практической реализации идеи метода ветвей и границ применительно к задаче коммивояжера нужно найти метод определения нижних границ подмножества и разбиения множества гамильтоновых контуров на подмножества (ветвление). Такое определение нижних границ базируется на том утверждении, что если ко всем элементам i-й строки или j-го столбца матрицы C прибавить или отнять число , то задача останется эквивалентной прежней, то есть оптимальность маршрута коммивояжера не изменится, а длина любого гамильтонова контура изменится на данную величину .