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

• Veröffentlicht in: Системні дослідження та інформаційні технології
• Datum: 2012
• Hauptverfasser: Морозов, А.В., Панішев, А.В.
• Format: Artikel
• Sprache: Ukrainian
• Veröffentlicht: Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2012
• Schlagworte: Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах
• Online Zugang: https://nasplib.isofts.kiev.ua/handle/123456789/50164
• Назва журналу: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Zitieren: Метод гілок та меж у гальмітоновій задачі про сільського листоношу / А.В. Морозов, А.В. Панішев // Систем. дослідж. та інформ. технології. — 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.