Loading article…
巡回購買者問題( TPP )は、オペレーションズ リサーチと 理論計算機科学で研究されるNP 困難な問題です。市場の一覧、異なる市場間の移動コスト、入手可能な商品の一覧と各市場での各商品の価格が与えられた場合、与えられた商品の一覧に対して、購入と移動の合計コストが最小となる経路を見つけることが課題となります。巡回セールスマン問題(TSP) は、この問題の特殊なケースです。
巡回セールスマン問題（TSP）との関係
この問題は巡回セールスマン問題の一般化と見ることができ、巡回セールスマン問題は各品目が1つの市場でのみ入手可能で、各市場では1つの品目のみが販売されるTPPの特殊なケースと見ることができます。TSPはNP困難であるため、TPPはNP困難です。[1]
TPPの解決
巡回購入者問題を解決するためのアプローチには、動的計画法[2]やタブー探索アルゴリズム[3]などがある。
参照
参考文献
- ^ 「旅行購入者問題に対するヒューリスティックス」（PDF）。2015年9月24日時点のオリジナル（PDF）よりアーカイブ。
- ^ 「追加制約を伴う巡回購入者問題に対する動的プログラミングアプローチ」(PDF)。2019年9月29日時点のオリジナル(PDF)からアーカイブ。
- ^ 「巡回購入問題を解決するためのタブー探索アプローチ」(PDF)。2016年6月10日時点のオリジナル(PDF)からアーカイブ。