さまざまな価格の商品sを提供するショップが多数あります。aショップが特定の商品を提供していない可能性があります。お店同士（通り）をつなぐことができます。
タスクは、合計価格が最小になるように、あるホーム ロケーションから (およびホーム ロケーションに戻る) 最適なルート (サイクル) を見つけることです。合計価格は、商品の価格の合計と店舗間の距離の合計です。
商品の価格はショップごとにわかっています。この情報を入手するために店舗に行く必要はありません。
制約は次のとおりです。
- バイヤー/旅行者は記事のリストを購入したいと考えており、すべての記事の可能性もあります
- すべての商品は、少なくとも 1 つのショップで入手可能です
- 店舗間の距離はコストで表されるため、ルートの合計コストを計算する際に、購入した商品のコストに単純に追加できます。
- ショップは複数回訪れることができますが、それによって移動が増加し、ルートの総コストが高くなります
私はnetworkxで最初のモデリングを行い、各ノード (ショップ) が提供する製品のすべての価格のリストを保持する有向グラフ (距離/コストを重みとして) としてショップ (および家) をモデル化しました。
私の最初の試みは力ずくのソリューションを作成することでした。すべての単純なサイクルを反復することで成功しました。次に、サイクルごとに、移動コストと商品のコスト (つまり、サイクルのショップに表示される最低価格) を計算します。
現在、上記は機能しますが、スケーリングしません: すべてのサイクルを列挙するための時間の複雑さはO((n+e)(c+1))、n 個のノード、e 個のエッジ、および c 個の基本回路 (有向グラフのすべての基本回路を見つけることです。DB Johnson、SIAM Journal on Computing 4、いいえ. 1, 77-84, 1975 )。そして、サイクル (回路) の数は非常に急速に増加します。
# random 'streetlike' shop-graphs
number of shops: 3, cycles: 2
number of shops: 4, cycles: 11
number of shops: 5, cycles: 11
number of shops: 6, cycles: 60
number of shops: 7, cycles: 229
number of shops: 8, cycles: 868
number of shops: 9, cycles: 1399
number of shops: 10, cycles: 61139
number of shops: 11, cycles: 60066
number of shops: 12, cycles: 1246579
number of shops: 13, cycles: 7993420
よりスケーラブルな問題の説明について何か提案はありますか? 動的または線形計画法のソリューションについて考えていますが、アイデアを聞きたいです。
更新: このトピックに関する博士論文全体を見つけました: ftp://tesis.bbtk.ull.es/ccppytec/cp181.pdf