Содержание
- 2. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Метод ветвей и границ Branch-and-Bound Method Вариант поиска с
- 3. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Метод ветвей и границ Все решения 1 группа решений
- 4. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Метод ветвей и границ Branch-and-Bound Method Пример: задача об
- 5. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Некоторое решение Старт Финиш
- 6. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Лучшее решение
- 7. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Лучшее решение
- 8. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Условия применимости метода ветвей и границ (МВГ) Для каждого
- 9. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Общий алгоритм МВГ S1 = А1; k = 1;
- 10. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Задача коммивояжёра (ЗК) The Traveling Salesman Problem (TSP) Коммивояжёр
- 11. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Пример (n = 5) 25 27 5 22 10
- 12. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Дано: 1. n – количество городов 2. C =
- 13. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Метод ветвей и границ в ЗК Основные идеи: Ветвление
- 14. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Ветвление YLeft(k) = Yk ∪ {(i, j)}, ZLeft(k) =
- 15. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Операция «приведения матрицы» По строкам: для ∀i∈1..n: gi =
- 16. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Приведённая матрица C*ij = Cij – gi – hj
- 17. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Пример Вычитание по строкам - 25 - 5 -
- 18. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Вычитание по столбцам - 3 d = 44 +
- 19. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Результат операции приведения матрицы В каждой строке и в
- 20. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Включение дуги i-j (левая ветвь дерева) Например, 3-5 Действия
- 21. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Вычёркивание 3-й строки и 5-го столбца (размер матрицы уменьшается
- 22. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Исключение дуги i-j (правая ветвь дерева) Например, 3-5 Действия
- 23. 09.02.2016 Метод ветвей и границ Задача коммивояжёра После ветвления по дуге (3,5) (3,5) (3,5) 47 62=47+15
- 24. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Какое ветвление сделать на первом шаге ? Дуга (3,5)
- 25. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Кандидаты на ветвление (включение-исключение) Δd = 3 Δd =
- 26. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Эвристика*: выбор дуги для ветвления При переходе в правую
- 27. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Эвристика: выбор дуги для ветвления Выбрать в приведённой матрице
- 28. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Эвристика: Рассмотрим множество пар (ν,λ), таких, что C*ν,λ= 0:
- 29. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Итак, в примере, следуя указанной эвристике, выбирается ребро (2,
- 30. 09.02.2016 Метод ветвей и границ Задача коммивояжёра После ветвления по дуге (2,1) (2,1) (2,1) 47 50=47+3
- 31. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Правая ветвь (исключая (2, 1)) - 12 - 3
- 32. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Поддерево от ветки (2, 1) (2, 1) Δd =
- 33. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Левая ветвь (включая (4, 5)) - 1 - 2
- 34. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Правая ветвь (исключая (4, 5)) - 18 68=50+18
- 35. 09.02.2016 Метод ветвей и границ Задача коммивояжёра (2, 1) (4, 5) (4, 5) 50 68=50+18 53=50+3
- 36. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Поддерево от ветки (4, 5) (4, 5) (1, 4)
- 37. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Запрет (4, 1) ??? Частичное решение (2,1), (4,5), (1,4)
- 38. 09.02.2016 Метод ветвей и границ Задача коммивояжёра К этому моменту 47 Все решения (2,1) (4,5) (1,4)
- 39. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Ветвление узла (2,1) Δd = 3 Δd = 8
- 40. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Поддерево от ветки (2, 1) (2, 1) (4, 1)
- 41. 09.02.2016 Метод ветвей и границ Задача коммивояжёра (4,1) – левая ветвь узла (2,1) Δd = 0
- 42. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Ветвление узла (4,1) (4, 1) (2, 3) (2, 3)
- 43. 09.02.2016 Метод ветвей и границ Задача коммивояжёра (2, 3) – левая ветка узла (4,1) Δd =
- 44. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Ветвление узла (2,3) (2, 3) (3, 5) (3, 5)
- 45. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Ветвление узла (2,3) (2, 3) (3, 5) (3, 5)
- 46. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Итак 47 Все решения (2,1) (4,5) (1,4) (5,3) (3,2)
- 47. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Сложность алгоритма Сложность точного алгоритма ЗК (методом ВиГ) в
- 48. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Приближённые решения (не минимальной стоимости) Зачем нужны приближённые решения?
- 49. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Приближённые решения (не минимальной стоимости) Алгоритм ближайшего соседа (АБС)
- 50. 09.02.2016 Метод ветвей и границ Задача коммивояжёра 2 – 1 – 5 – 3 – 4
- 51. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Ещё пример: n = 6 Оптимальное решение 1 –
- 52. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Б: 3 – 6 – 5 – 1 –
- 53. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Оценка степени приближения алгоритма ближайшего соседа (АБС) Nn –
- 54. 09.02.2016 Метод ветвей и границ Задача коммивояжёра 2. Алгоритм включения ближайшего города (АВБГ) Если есть цепочка
- 55. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Пример: n = 6 Оптимальное решение 1 – 4
- 56. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Пример получения обхода АВБГ 2 – 3 – 6
- 57. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Пример получения обхода АВБГ 2 – 3 – 6
- 58. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Пример получения обхода АВБГ 2 – 3 – 6
- 59. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Пример получения обхода АВБГ 2 – 3 – 6
- 60. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Пример получения обхода АВБГ 2 – 3 – 6
- 61. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Пример получения обхода АВБГ 2 – 3 – 6
- 62. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Пример получения обхода АВБГ 2 – 3 – 6
- 63. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Пример получения обхода АВБГ 3 – 6 – 2
- 64. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Пример получения обхода АВБГ 3 – 6 – 2
- 65. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Пример получения обхода АВБГ 3 – 6 – 2
- 66. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Пример получения обхода АВБГ 3 – 6 – 2
- 67. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Пример получения обхода АВБГ 3 – 6 – 2
- 68. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Пример получения обхода АВБГ 3 – 6 – 2
- 69. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Пример получения обхода АВБГ 3 – 6 – 2
- 70. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Оценка степени приближения АВБГ In – маршрут АВБГ, ⏐In⏐
- 71. 09.02.2016 Метод ветвей и границ Задача коммивояжёра Сложность приближённых алгоритмов АБС ≈ C1n2 АВБГ ≈ C2n2,
- 73. Скачать презентацию