Задача коммивояжера - презентация, доклад, проект скачать

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

Содержание ▲

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

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

Слайд 1

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

ЗАДАЧА КОММИВОЯЖЕРА

Слайд 2

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

ЗАДАЧА КОММИВОЯЖЕРА Задача заключается в определении оптимального маршрута объезда n городов по критерию времени, стоимости или длине маршрута. Эта задача связана с определением гамельтонова цикла минимальной длины. Основным методом решения таких задач является метод ветвей и границ. Сущность метода заключается в том, что все множество допустимых решений задачи делится на последовательно уменьшающиеся подмножества с помощью процедуры ветвления. В результате находится последовательность объезда пунктов (маршрут), протяженность которого меньше любого другого возможного варианта, т.е. строится оптимальный кольцевой маршрут.

Слайд 3

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

ЗАДАЧА КОММИВОЯЖЕРА Построить оптимальный кольцевой маршрут для неографа G(X,Y) (рис. 10.36) с вершинами хi , Пропускные способности ребер указаны на графе. Рис. 10.36

Слайд 4

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

ЗАДАЧА КОММИВОЯЖЕРА 1. Составим матрицу пропускных способностей ребер C(G) графа G(X,U) рис.10.37. Рис. 10.37

Слайд 5

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

ЗАДАЧА КОММИВОЯЖЕРА Пропускную способность между однородными вершинами условно принимаем равную бесконечности, т.е. (клетки главной диагонали матрицы С) (табл. 10.14). (10.14)

Слайд 6

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

ЗАДАЧА КОММИВОЯЖЕРА Для определения нижней границы множества выполним приведение матрицы (табл. 10.14), т.е. в каждом столбце и строке матрица должна содержать не менее одного нуля. С этой целью выберем в каждой строке минимальный элемент и запишем их в правой колонке табл. 10.14. Табл. 10.14.

Слайд 7

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

ЗАДАЧА КОММИВОЯЖЕРА Вычитая из элементов каждой строки соответствующие значения min aik, получаем табл. 10.15. Табл. 10.15

Слайд 8

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

ЗАДАЧА КОММИВОЯЖЕРА Для завершения приведения матрицы табл. 10.15 вычитаем минимальные значения в каждом столбце min aik и получим приведенную матрицу (табл. 10.16). Сумма констант приведения по строкам и столбцам матрицы составит: Н= 6 + 7 + 6+ 9+ 5 + 5 + 1+4 = 43. Сумма констант приведения Н = 43 является границей всех циклов, т.е. любой вариант кольцевого маршрута не может быть меньше этой нижней границы.

Слайд 9

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

ЗАДАЧА КОММИВОЯЖЕРА С помощью ветвления рассматриваются циклы (последовательности обхода вершин графа), которые могут привести к построению оптимального (минимального) кольцевого маршрута. На первом этапе построения древовидного графа множество всех циклов делится на два подмножества: первое из них включает все циклы (замкнутые маршруты) с перемещением от вершины хi к вершине хк, а второе множество содержит циклы без этого перемещения. На графе ветвления от исходной вершины Н = 43 отходят две дуги (ветви): к вершине (i,k), изображающей первое из этих подмножеств и к вершине, указывающее второе (рис. 10.38).

Слайд 10

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

ЗАДАЧА КОММИВОЯЖЕРА Рис. 10.38 Рассмотрим, как выбирается пара вершин (i,k) и . Пара вершин (xi, хk) на основании a(i,k), которые рассчитываются для всех клеток приведенной матрицы (10.15), содержащих нули. Для определения a(i,k) в строке xi выбирается минимальный элемент (cik = 0) и минимальный в столбце хк. Эти минимальные элементы складываются, а их сумма равна значению a(i,k).

Слайд 11

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

ЗАДАЧА КОММИВОЯЖЕРА В рассматриваемом примере эти значения элементов в строках укажем справа, а в столбцах — внизу (табл. 10.16), сумму минимальных элементов запишем в клетках, содержащих нули и отметим их кружком (табл. 10.16). Вычислим a(i,k) для каждой клетки с нулевым элементами:

Слайд 12

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

ЗАДАЧА КОММИВОЯЖЕРА (10.16)

Слайд 13

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

ЗАДАЧА КОММИВОЯЖЕРА Запишем значения α(i,k) в соответствующих клетках с нулями, отмечая их кружками в табл. 10.16, выбираем наибольшее значение α(i,k) Таких значений в табл. 10.16 четыре. Выбираем одно из них, например, α(3,1) = 0 + 4 =4 (для строки х3 и столбца x1. Вычеркивая их, получаем табл. 10.17, в которой нуль, расположенный в строке х1 и столбце х3, заменяем на ∞, так как вершина х3 не должна иметь цикла (3,1), т.е. c13 =∞

Слайд 14

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

ЗАДАЧА КОММИВОЯЖЕРА (10.17) Рис. 10.39

Слайд 15

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

ЗАДАЧА КОММИВОЯЖЕРА Определяем ребро ветвления, деля множества маршрутов на два: и (3,1), рис. 10.39. Нижняя граница вершины представляет сумму значений нижней границы предыдущей вершины, равной 43 и т.е. Для определения нижней границы вершины вторым слагаемым берется сумма констант приведения матрицы 10.17. Для приведения этой матрицы из строки х1 следует вычесть минимальный элемент 4 и получим матрицу 10.18.

Слайд 16

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

ЗАДАЧА КОММИВОЯЖЕРА Сумма констант приведения равна h = 4. Нижняя граница вершины (3,1) составит H(3,1) = 43 + 4 = 47 (рис. 10.40). Рис. 10.40

Слайд 17

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

ЗАДАЧА КОММИВОЯЖЕРА Для получения следующей пары вершин от вершины (3,1) определим α и выберем новую пару вершин, входящих в концевой маршрут.

Слайд 18

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

ЗАДАЧА КОММИВОЯЖЕРА В табл. 10.18 укажем минимальные элементы в строках и столбцах, записанных справа и внизу этой таблицы соответственно. Вычислим сумму констант приведения α(i,k) и включим их в табл. 10.18: Табл. 10.18

Слайд 19

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

ЗАДАЧА КОММИВОЯЖЕРА Принимаем вершины х1 и х2 с величиной приведения в качестве звена в кольцевом маршруте. В табл. 10.18 вычеркиваем столбец х2 и получаем табл. 10.19: Табл.10.19

Слайд 20

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

ЗАДАЧА КОММИВОЯЖЕРА Определяем вершины ветвления для ребер (1,2) и Нижняя граница вершины определяется из условия , Для определения нижней границы вершины (1,2) вторым слагаемым берем сумму констант приведения табл. 10.19, вычитая из строки х2 а25 = 7 и в столбце х3 величину α43 = 5, чтобы матрица имела нули в каждой строке и каждом столбце. Величина приведения h = 7 + 5. Н(1,2) = 47 + 7 + 5 = 59.

Слайд 21

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

ЗАДАЧА КОММИВОЯЖЕРА Приведенная матрица табл. 10.20 имеет вид: Табл. 10.20 Определяем значения для клеток с нулевыми элементами:

Слайд 22

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

ЗАДАЧА КОММИВОЯЖЕРА Рис. 10.41 Исключаем из табл. 10.20 х5 строку и столбец х6. Получаем табл. 10.21: (10.21)

Слайд 23

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

ЗАДАЧА КОММИВОЯЖЕРА Приведем табл. 10.21, вычитая из каждого элемента строки х6 минимальный элемент а64 = 3, Получаем табл. 10.22 в виде: (10.22) Строим подграф (рис. 10.42), исключаем в табл. 10.22 строку х6 и столбец х4, так как α(6,4) = 5. Получаем табл. 10.23, в которой α44 = 0. Заменяем ∞ чтобы исключить цикл.

Слайд 24

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

ЗАДАЧА КОММИВОЯЖЕРА Рис. 10.42 (10.23) Рис. 10.43

Слайд 25

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

ЗАДАЧА КОММИВОЯЖЕРА Строим древовидный граф ветвлений (рис. 10.45), соединяя отдельные элементы графа (рис. 10.39-10.43) и гамельтонов цикл обхода вершин исходного графа (рис. 10.44). Рис. 10.44

Слайд 26

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

ЗАДАЧА КОММИВОЯЖЕРА Гамельтонов цикл образуют ребра (x3,x1), (x1,x2), (х2,х5), (х5,х6), (х6,х4), (х4,х3). Длина маршрута обхода вершин x3 → x1 → x2 → x5→ x6→ x4 → x3 графа G(X,Y) (рис. 10. 37) составляет М = 6 + 11 + 14 + 5 + 12 + 14 = 62 и совпадает с нижней границей графа (рис. 10.45).

Слайд 27

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

ЗАДАЧА КОММИВОЯЖЕРА Рис.10.37 Рис. 10.45

Слайд 28

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

ЗАДАЧА КОММИВОЯЖЕРА Последовательность решения задачи коммивояжера методом ветвей и границ состоит в следующем: 1. На основании графа посещения городов составляется матрица расстояний от соответствующих вершин. 2. Проводится приведение матрицы, вычитая минимальные элементы по строкам и столбцам. 3. Определяем нижнюю границу всего множества маршрутов, складывая значения вычитаемых минимальных элементов.

Слайд 29

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

ЗАДАЧА КОММИВОЯЖЕРА 4. В каждой клетке приведенной матрицы, в которых aik = 0, заменяем поочередно нули на ∞ и вычисляем суммы новых констант приведения H(xi, xk), которые записываем в клетке с нулем, отмеченной кружком. 5. Выбираем ребро ветвления (i,k) по максимальной величине суммы констант приведения Нтах. Затем исключаем его из множества путем замены элемента матрицы а1к =∞. В результате будет определено подмножество маршрутов {(i,k)}. 6. В полученной матрице расстояний по строкам получаем нули, вычитая минимальное значение элементов в соответсвующих строках и определяем нижнюю границу подмножества маршрутов H(i,k).

Слайд 30

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

ЗАДАЧА КОММИВОЯЖЕРА 7. Включаем ребро (i,k) в маршрут, вычеркивая строку i и столбец к в приведенной матрице расстояний и заменяя симметричный элемент aik =∞ для исключения образования негамельтонова цикла. 8. Приводим сокращенную матрицу (получаем нули в строках вычитанием минимального элемента) и определяем нижнюю границу подмножества H(i,k). 9. Сравниваем нижние границы подмножеств H(i,k) и H(i,k) и подмножество с меньшим значением нижней границы подвергаем ветвлению. 10. Определяем гамельтонов цикл при получении окончательной матрицы размерности 2x2.

Теги Задача коммивояжера

Похожие презентации