Проблема путешествующего покупателя
Задача путешествующего покупателя ( TPP ) — это NP-сложная задача, изучаемая в области исследования операций и теоретической информатики . Учитывая список торговых площадок, стоимость перемещения между различными торговыми площадками и список доступных товаров вместе с ценой каждого такого товара на каждой торговой площадке, задача состоит в том, чтобы найти для заданного списка товаров маршрут с минимальным совокупная стоимость покупок и поездки. ( Задача коммивояжера TSP) является частным случаем этой задачи.
Связь с задачей коммивояжера (TSP)
[ редактировать ]Эту проблему можно рассматривать как обобщение задачи коммивояжера, которую можно рассматривать как частный случай ТТП, когда каждый товар доступен только на одном рынке, и на каждом рынке продается только один товар. Поскольку TSP является NP-жестким, TPP является NP-жестким. [1]
Решение ТПП
[ редактировать ]Подходы к решению проблемы путешествующего покупателя включают динамическое программирование. [2] и алгоритмы табу-поиска . [3]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ «Эвристика для задачи путешествующего покупателя» (PDF) . Архивировано из оригинала (PDF) 24 сентября 2015 г.
- ^ «Подход к динамическому программированию для задачи путешествующего покупателя с дополнительными ограничениями» (PDF) . Архивировано из оригинала (PDF) 29 сентября 2019 г.
- ^ «Подход к поиску табу для решения проблемы путешествующих покупок» (PDF) . Архивировано из оригинала (PDF) 10 июня 2016 г.