Презентации по Математике

Задача коммивояжёра
Задача коммивояжёра
Задача коммивояжёра Общая схема метода ветвей и границ Метод ветвей и границ - общий метод для нахождения решений задач дискретной и комбинаторной оптимизации. Метод является алгоритмом перебора с отсевом подмножеств допустимых решений, не содержащих оптимальных решений. Опишем идею метода на примере поиска минимума функции f(x) на конечном множестве допустимых значений Ω. Метод ветвей и границ основан на трёх процедурах: ветвление, нахождение оценок (границ), отсев вариантов. Ветвление состоит в разбиении по некоторому правилу A множества допустимых решений на подмножества Процедура нахождения оценок заключается в поиске по некоторому правилу B нижних границ для минимальных значений функции f(x) на Пусть полученные нижние границы . Очевидно, . Из полученных подмножеств выбираем подмножество Ωm, у которого По правилу A разбиваем Ωm на подмножества и вычисляем по правилу B нижние границы для минимальных значений функции f(x) на Задача коммивояжёра Общая схема метода ветвей и границ Ω Ω1 Ωm Ωk . . . . . . Ωm1 Ωmp Ωmk . . . γ . . . Ωmp1 Ωmph Ωmpk . . . . . . γ1 γm γk γm1 γmp γmk γmp1 γmph γmpk
Продолжить чтение