私は修士プロジェクトに取り組んでおり、Java で次の問題をプログラミングする方法についていくつかのアイデアを提供してくれることを期待していました。
トレーダーがアイテムのリストを購入したいと考えています。彼がアイテムを購入できる複数の売り手/市場があります。市場は買い手までの距離が異なります。買い手は、可能な限り最短距離で最も安い商品を購入する方法を見つけ出さなければなりません。
基本的に、買い手は、最も安い商品を見つけようとすると同時に、旅費を最小限に抑えたいと考えています。
説明が理にかなっていることを願っています。明確でない場合はお知らせください。別の方法で説明します。
これまでのところ、Buyer クラス、Seller クラス、Item クラス、および Main クラスがあります。買い手の場所と売り手の場所を Java Point 型で入れる予定です。
ダイクストラの最短経路のアルゴリズムのようなものを使用することを考えていましたが、問題は、買い手が少し遠くに移動すると、アイテムが安くなる可能性があることです。
あなたの助けと時間を前もってありがとう。
まず、これはアルゴリズムの質問であり、Javaの質問ではありません。使用するアルゴリズムを理解すると、選択した言語で簡単に実装できるようになります（ただし、PythonはJavaよりもはるかに簡単です）。
アルゴリズムに関しては、これはNP困難な問題であるため、既知の多項式時間アルゴリズムはありません。（そしてあなたがそれを見つけた場合、あなたは百万ドルの賞金を獲得します）。どのような入力を処理することが期待されていますか？最悪の場合の複雑さが悪い場合でも、実際にはうまく機能するものがあるかもしれません。
旅費が総費用に含まれると仮定し、旅費と購入費の合計を最小限に抑えたいとします。これは、巡回セールスマン問題が特殊なケースである巡回購入者問題とまったく同じように聞こえます。wiki 記事の参照には、問題に対するいくつかの異なる解決策があります。この問題は NP 困難であるため、高速で最適な解を与えることが保証されている既知の解は存在しないことに注意してください。
「買い手は、可能な限り最短距離で最も安い商品を購入する方法を見つけ出さなければなりません。」
それは、最も安い商品の場所を見つけて、それらの間の最短ルートを見つけるだけです. 同じアイテムが異なる場所で同じ価格で入手できる場合、各ルートの最短経路を実行します。
または、すべてのアイテムをカバーする最短ルートを見つけて、価格を合計します。
移動距離のコスト ファクターを追加した場合にのみ (場所間のガソリン代など)、移動距離が買い物にかかる費用に関係します。
「遺伝的アルゴリズム 巡回セールスマン問題」で検索してみてください。
ダイクストラの方向性は正しいと思います。顧客の優先順位を移動距離で考慮する必要があるという同様の問題があり、優先順位を距離に関連付ける方法を単純に決定しました。あなたの場合は、旅費とアイテムのコストを簡単に比較できるため、さらに簡単になります。両方の合計をエッジの重みとしてください。