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

Abstract

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.