この問題を引き起こす最も陰湿な方法は何ですか？

StackOverflow https://stackoverflow.com/questions/643594

  •  22-07-2019
  •  | 
  •  

質問

これまでの私のベストショット：

  

配達車両は一連の配達を行う必要があります（d 1 、d 2 、... d n ）任意の順序で行います。つまり、集合D = {d 1 、d 2 、... d n <のすべての可能な順列/ sub>}は有効なソリューションですが、ルートの一方の端で基地局を出る前に特定のソリューションを決定する必要があります（たとえば、パッケージを車両LIFOにロードする必要があると想像してください）。

     

さらに、さまざまな順列のコストは同じではありません。 d i -1 とd i の間の移動距離の2乗の合計として計算できます。ここで、d 0 は方向の変更を伴うセグメントには3倍のコストがかかるという注意事項があります（これが鉄道や空気圧チューブで行われ、バックアップすると他のトラフィックが中断されることを想像してください）。

     

配信のセット D を、基地局からの距離として表します（ abs（d i -d j ）は2つの配信間の距離です）および反復子 permutations（D）は各順列を連続して生成し、他の順列のコスト以下のコストを持つ順列。

今、この説明から直接実装すると、次のようなコードになります：

function Cost(D) ...

function Best_order(D)
    for D1 in permutations(D)
        Found = true
        for D2 in permutations(D)
            Found = false if cost(D2) > cost(D1)
        return D1 if Found

O（n * n！^ 2）は次のとおりです。かなりひどい-特に、洞察力のある人が単にDをソートすることで見つけるO（n log（n））と比較して。

私の質問：当然のことながら不注意をソートアルゴリズムの悪い（または別の恐ろしい）実装に導くもっともらしい問題の説明を思いつくことができますか？

役に立ちましたか？

解決

この質問をインタビューに使用して、申請者が一見複雑な質問の簡単な解決策に気付くことができるかどうかを確認していると仮定します。

[この仮定は正しくありません-MarkusQ]

情報が多すぎます。

これを解決するための鍵は、ポイントが1つの次元にあり、並べ替えだけが必要であることを認識することです。この質問をより難しくするために、この事実をできるだけ隠します。

最大の手がかりは距離の式です。方向を変更するとペナルティが発生します。私の頭に浮かぶ最初のことは、このペナルティを最小限に抑えることです。ペナルティを取り除くには、特定の方向に並べる必要があります。この順序は自然な並べ替え順序です。

方向を変更した場合のペナルティを削除します。それはあまりにも多くのプレゼントです。

もう1つの重要な手がかりは、アルゴリズムへの入力値である整数のリストです。並べ替えのリスト、またはすべての並べ替えを提供します。これにより、O（n！）アルゴリズムが実際に期待されるかもしれないと考えるようになります。

次のように言います：

  

可能なすべてのリストを与える   n個の配送場所の順列、   配達の各順列   （d 1 、d 2 、...、   d n ）のコストは次で定義されています：

     

     

次のような置換Pを返す   Pのコストがany以下   その他の順列。

実際に行う必要があるのは、最初の順列で読み取られ、並べ替えるだけです。

単一のループを構築してコストを比較する場合、アルゴリズムのbig-oランタイムは何であるかを尋ねます。ここで、nは配信ロケーションの数です（別のトラップ）。

他のヒント

これは直接的な答えではありませんが、もっと明確にする必要があると思います。

d i を負にすることはできますか？もしそうなら、私が見る限り、ソートだけでは十分ではありません。

例：

d 0 = 0

deliverries =（-1,1,1,2）

この場合の最適なパスは 1＆gt; 2＆gt; 1＆gt; -1 。

編集：これは実際には最適なパスではないかもしれませんが、ポイントを示しています。

あなたは最初に最適な解決策を見つけたので、次のように言い換えることができます

＆quot;次のルールは、次のコンビネーションが最も最適であることを証明します。最適とは、すべてのステージ（A ..Z）は1回だけ存在する必要があります。

確信：

A->C->D->Y->P->...->N

ステージコスト：

A->B = 5,
B->A = 3,
A->C = 2,
C->A = 4,
...
...
...
Y->Z = 7,
Z->Y = 24."

それは誰かをしばらく忙しくしておくべきです。

これはナップザックの問題を思い出させます。しかし、ナップザックはNPハードの問題でもあるため、ナップザックとあなたの問題を関連付けている場合、動的プログラミングを使用して非常に複雑なソリューションを考えさせることができるかもしれません。基本的な問題は次のとおりです。

  

少なくともVの値を達成できます   重量Wを超えずに？

問題は、Vが一意である場合、距離など、かなり良い解決策を見つけることができることです：

  

各タイプのナップザック問題   ごとに異なる値を持つアイテムj   重量単位（vj = pj / wj）は   最も簡単な   NP完全な問題。確かに経験的   複雑さはO（（log   n）2）非常に大きな問題は   非常に迅速に解決されました、例えば2003年に   解決に必要な平均時間   n = 10,000のインスタンスは14未満でした   商品パーソナルを使用したミリ秒   computers 1 。

したがって、複数のストップ/パッケージが同じvjを共有している可能性があることを述べたい場合があります。

  

ただし、   複数のアイテムの縮退ケース   同じ値vjを共有すると   極端ではるかに難しい   vj =定数である場合   複雑なサブセット合計問題   O（2N / 2N）の。

したがって、値ごとの重みを値ごとの距離に置き換えて、複数の距離が実際に同じ値を共有する可能性があると述べた場合、退化する人もいるでしょう。

これは単なる（NP-Hard）旅行セールスマンの問題ではありませんか？あなたがそれをずっと難しくするつもりはないようです。

実際のアルゴリズムが不明確になるように問題をフレージングすることもできます-例えば経路を単線の鉄道線として記述することにより、人はドメインの知識からバックトラックの方が費用がかかることを推測する必要があります。

誰かが再帰比較をするように誘惑されるような方法で質問を説明するのはどうですか？ 「最高の（これまでの）結果の最適な最大サブセットを使用してアルゴリズムを高速化できますか？」

ところで、これの目的は何ですか-インタビュイーを拷問することを意図しているようです。

配達用トラックを拠点に戻す必要があるか（往復する必要があるか）、明確にする必要があります。トラックが 戻ってきた場合、最も遠い地点から拠点までの戻りの2乗は非常にコストがかかるため、単純なソートでは最短経路は生成されません。 「外出」の途中でいくつかのホップを見逃し、帰りの途中でそれらを使用する方が安くなることがわかりました。

（たとえば、すべての情報を渡さずに）誰かを悪い答えにだました場合、それはその愚かさまたはそれを引き起こしたあなたの欺isですか？

賢者の知恵は、彼らが自我の嘘を聞かないなら、どれほど素晴らしいですか？

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top