Метод ветвей и границ. Задача коммивояжера

Среди методов, привлекаемых к решению задач исследования операций (ИО) особое место занимает метод ветвей и границ (МВГ), который внес оригинальный взгляд в целом на проблемы оптимизации и позволил по другому воспринимать смысл оптимальности решений. Авторы разработанного метода предложили оценивать целевую функцию (ЦФ) задачи нижней границей целевой функции (НГЦФ) всего множества решений конкретной задачи, не получая ни всех решений, ни одного из них. Располагая такой оценкой, можно формировать решения задачи последовательно их улучшая не сильно уклоняясь от НГЦФ. В статье предлагается детальный разбор этого метода решения на числовом примере с подробными комментариями выполняемых действий при поиске оптимального решения.

Читать далее

Источник: Хабрахабр

Перейти на сайт

Похожие новости

• [Перевод] Обход двухфакторной аутентификации в публичной баг-баунти программе: путь к $6000
• Кратко про XHTTP для VLESS: что, зачем и как
• [Перевод] Как я нашёл уязвимость в ядре Linux при помощи модели o3
• SelfCoerce для локального повышения привилегий на Windows 10
• Теория мертвого 2GIS
• Постквантовые криптостандарты США на алгоритмы электронной подписи на основе хеш-функций с сохранением состояния
• Новые возможности менеджера секретов Deckhouse Stronghold: пространства имён, резервные копии и репликация данных
• [Перевод] Single Sign-On c OpenAM и OpenIG: практические примеры реализации
• Безопасность по ГОСТу: процесс интеграции HSM отечественного производства
• Каких коммуникаторов не хватает PR-индустрии?