Содержание
- 2. ЗАДАЧА КОММИВОЯЖЕРА Задача заключается в определении оптимального маршрута объезда n городов по критерию времени, стоимости или
- 3. ЗАДАЧА КОММИВОЯЖЕРА Построить оптимальный кольцевой маршрут для неографа G(X,Y) (рис. 10.36) с вершинами хi , Пропускные
- 4. ЗАДАЧА КОММИВОЯЖЕРА 1. Составим матрицу пропускных способностей ребер C(G) графа G(X,U) рис.10.37. Рис. 10.37
- 5. ЗАДАЧА КОММИВОЯЖЕРА Пропускную способность между однородными вершинами условно принимаем равную бесконечности, т.е. (клетки главной диагонали матрицы
- 6. ЗАДАЧА КОММИВОЯЖЕРА Для определения нижней границы множества выполним приведение матрицы (табл. 10.14), т.е. в каждом столбце
- 7. ЗАДАЧА КОММИВОЯЖЕРА Вычитая из элементов каждой строки соответствующие значения min aik, получаем табл. 10.15. Табл. 10.15
- 8. ЗАДАЧА КОММИВОЯЖЕРА Для завершения приведения матрицы табл. 10.15 вычитаем минимальные значения в каждом столбце min aik
- 9. ЗАДАЧА КОММИВОЯЖЕРА С помощью ветвления рассматриваются циклы (последовательности обхода вершин графа), которые могут привести к построению
- 10. ЗАДАЧА КОММИВОЯЖЕРА Рис. 10.38 Рассмотрим, как выбирается пара вершин (i,k) и . Пара вершин (xi, хk)
- 11. ЗАДАЧА КОММИВОЯЖЕРА В рассматриваемом примере эти значения элементов в строках укажем справа, а в столбцах —
- 12. ЗАДАЧА КОММИВОЯЖЕРА (10.16)
- 13. ЗАДАЧА КОММИВОЯЖЕРА Запишем значения α(i,k) в соответствующих клетках с нулями, отмечая их кружками в табл. 10.16,
- 14. ЗАДАЧА КОММИВОЯЖЕРА (10.17) Рис. 10.39
- 15. ЗАДАЧА КОММИВОЯЖЕРА Определяем ребро ветвления, деля множества маршрутов на два: и (3,1), рис. 10.39. Нижняя граница
- 16. ЗАДАЧА КОММИВОЯЖЕРА Сумма констант приведения равна h = 4. Нижняя граница вершины (3,1) составит H(3,1) =
- 17. ЗАДАЧА КОММИВОЯЖЕРА Для получения следующей пары вершин от вершины (3,1) определим α и выберем новую пару
- 18. ЗАДАЧА КОММИВОЯЖЕРА В табл. 10.18 укажем минимальные элементы в строках и столбцах, записанных справа и внизу
- 19. ЗАДАЧА КОММИВОЯЖЕРА Принимаем вершины х1 и х2 с величиной приведения в качестве звена в кольцевом маршруте.
- 20. ЗАДАЧА КОММИВОЯЖЕРА Определяем вершины ветвления для ребер (1,2) и Нижняя граница вершины определяется из условия ,
- 21. ЗАДАЧА КОММИВОЯЖЕРА Приведенная матрица табл. 10.20 имеет вид: Табл. 10.20 Определяем значения для клеток с нулевыми
- 22. ЗАДАЧА КОММИВОЯЖЕРА Рис. 10.41 Исключаем из табл. 10.20 х5 строку и столбец х6. Получаем табл. 10.21:
- 23. ЗАДАЧА КОММИВОЯЖЕРА Приведем табл. 10.21, вычитая из каждого элемента строки х6 минимальный элемент а64 = 3,
- 24. ЗАДАЧА КОММИВОЯЖЕРА Рис. 10.42 (10.23) Рис. 10.43
- 25. ЗАДАЧА КОММИВОЯЖЕРА Строим древовидный граф ветвлений (рис. 10.45), соединяя отдельные элементы графа (рис. 10.39-10.43) и гамельтонов
- 26. ЗАДАЧА КОММИВОЯЖЕРА Гамельтонов цикл образуют ребра (x3,x1), (x1,x2), (х2,х5), (х5,х6), (х6,х4), (х4,х3). Длина маршрута обхода вершин
- 27. ЗАДАЧА КОММИВОЯЖЕРА Рис.10.37 Рис. 10.45
- 28. ЗАДАЧА КОММИВОЯЖЕРА Последовательность решения задачи коммивояжера методом ветвей и границ состоит в следующем: 1. На основании
- 29. ЗАДАЧА КОММИВОЯЖЕРА 4. В каждой клетке приведенной матрицы, в которых aik = 0, заменяем поочередно нули
- 31. Скачать презентацию