Метод гілок та меж у гальмітоновій задачі про сільського листоношу

• Опубліковано в: : Системні дослідження та інформаційні технології
• Дата: 2012
• Автори: Морозов, А.В., Панішев, А.В.
• Формат: Стаття
• Мова: Українська
• Опубліковано: Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2012
• Теми: Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах
• Онлайн доступ: https://nasplib.isofts.kiev.ua/handle/123456789/50164
• Назва журналу: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Цитувати: Метод гілок та меж у гальмітоновій задачі про сільського листоношу / А.В. Морозов, А.В. Панішев // Систем. дослідж. та інформ. технології. — 2012. — № 2. — С. 57-66. — Бібліогр.: 6 назв. — укр.

Cформульовано гамільтонову задачу про сільського листоношу, яка є узагальненням гамільтонової задачі комівояжера. Запропоновано модифікацію класичного методу гілок та меж (методу Літтла), яка дозволяє знаходити точний розв’язок гамільтонової задачі про сільського листоношу або коректно встановити його відсутність. Сформулирована гамильтоновая задача о сельском почтальоне, которая является обобщением гамильтоновой задачи коммивояжера. Предложена модификация классического метода ветвей и границ (метода Литтла), позволяющая находить точное решение гамильтоновой задачи о сельском почтальоне или корректно установить его отсутствие. The Hamiltonian Rural Postman Problem, which is generalization of the Hamiltonian Travelling Salesman Problem, is formulated. Modification of the classical branch-and-bound algorithm (Little’s method) which allows to find exact solution of the Hamiltonian Rural Postman Problem or correctly determine lack of solution is offered.