5

次の課題を解決するために使用するのに適したヒューリスティックは何ですか?

Quality Blimps Inc. は、他の都市 (N) への販売を拡大することを検討しているため、飛行船を販売するために他の都市に飛ぶセールスマンとしてあなたを雇いました。飛行船は旅行に費用がかかる可能性があるため、旅行ごとにいくつの飛行船を持って行き、いつ本部に戻ってより多くの飛行船を手に入れるかを決定する必要があります. Quality Blimps には無制限の飛行船があります。

訪問する各都市で販売できる飛行船は 1 つだけですが、移動費が高額な都市もあるため、すべての都市を訪問する必要はありません。各都市には飛行船の初期価格が設定されていますが、飛行船の販売数が増える (そして目新しさが薄れる) と、この価格は一定の割合で下がります。利益を最大化する良いルートを見つけます。

https://www.hackerrank.com/codesprint4/challenges/tbsp

この課題は、標準的な巡回セールスマン問題に似ていますが、さらにひねりが加えられています。セールスマンは、自分の旅費と飛行船の両方を追跡する必要があります。都市ごとに飛行船の価格は異なりますが、これらの価格は旅を続けるうちに下がります。利益を最大化するために使用する高速なアルゴリズム (つまり n log n ) は何でしょうか?

ある方法でアイテムを輸送する価格は、TSP をより単純にします。セールスマンが都市 A にいて、B に行きたい場合、B に直接行くコストと、最初に本社に戻ってより多くの飛行船を受け取るコストを比較できます。つまり、A 経由で B に余分な飛行船を持っていくか、その間に戻る方が安くなります。このチェックにより、一連のループ旅行が作成され、営業担当者は収益の高い順に通過できます。しかし、そもそもこれらのループを特定するにはどうすればよいでしょうか?

4

4 に答える 4

3

このような問題のアルゴリズムは、通常、「ソリューションを何度も実行して、最適なソリューションを選択する」ようなものです。また、次に試すソリューションを選択するには、以前の反復の結果を使用します。

特定のアルゴリズムについては、枝刈り、シミュレーテッド アニーリング、タブー検索、遺伝的アルゴリズム、ニューラル ネットワークを使用してバックトラックを試してみてください (関連性があると思われる順に)。また、Tyler Durden によって提案されたモンテカルロ ツリー検索のアイデアはかなりクールに見えます。

于 2013-02-12T11:32:22.610 に答える
3

これは検索の問題です。ネットワークが力ずくで解決できるよりも大きいと仮定すると、最適なアルゴリズムはモンテカルロ木探索になります。

于 2013-02-06T18:43:22.917 に答える
0

これは古典的な最適化問題のように見えますが、これはシミュレーテッド アニーリング アルゴリズムで処理できることがわかっています (1980 年代に、シミュレーテッド アニーリングの最初の商用利用である Wintek 電子 CAD 自動配置プログラムに取り組んできました)。ほとんどの最適化アルゴリズムは、あなたのような多くの変数の問題を処理できます。問題は、最適なソリューション (あなたの場合は最低コスト) を得るために、フィットネス アルゴリズムを正しく設定することです。

他の最適化アルゴリズムは一見の価値があるかもしれません - 私はシミュレーテッド アニーリング アルゴリズムを実装した経験があります。

(シミュレーテッド アニーリング ルートに進む場合は、PJ van Laarhoven と EH Aarts による「Simulated Annealing: Theory and Applications (Mathematics and Its Applications)」を入手することをお勧めしますが、絶版になっているため、探し出す必要があります ( 1980 年代に私が使っていた本かもしれません)。

于 2013-02-13T12:03:55.670 に答える