Проблема с путешествующим покупателем
Задача путешествующего покупателя ( TPP ) - это NP-сложная задача, изучаемая в теоретической информатике . Учитывая список торговых площадок, стоимость перемещения между разными торговыми площадками и список доступных товаров вместе с ценой каждого такого товара на каждой торговой площадке, задача состоит в том, чтобы найти для данного списка товаров маршрут с минимальными затратами. совокупная стоимость покупок и путешествий. Задача коммивояжера (TSP) - частный случай этой проблемы.
Отношение к задаче коммивояжера (TSP)
Проблему можно рассматривать как обобщение задачи коммивояжера, то есть каждый товар доступен только на одном рынке, и на каждом рынке продается только один товар. Поскольку TSP является NP-сложным, TPP является NP-сложным. [1]
Решение ТЭС
Подходы к решению проблемы путешествующего покупателя включают динамическое программирование [2] и алгоритмы запретного поиска . [3]
Смотрите также
использованная литература
