7

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

配送車は、一連の配送 (d 1、d 2、...d n ) を行う必要があり、任意の順序で配送できます。つまり、集合 D = {d 1、 d 2 ,...d n } は有効なソリューションですが、特定のソリューションは、ルートの一端にある基地局を出る前に決定する必要があります (たとえば、パッケージを車両の LIFO に積み込む必要があると想像してください)。 ）。

さらに、さまざまな順列のコストは同じではありません。これは、d i-1と d iの間を移動した距離の 2 乗の合計として計算できます。ここで、d 0は基地局と見なされます。ただし、方向の変更を伴うセグメントには 3 倍の費用がかかることに注意してください。 (これが鉄道または気送管で行われており、後退すると他の交通が妨げられると想像してください)。

D基地局からの距離 (つまり、abs(di -djは 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)) と比較すると、.

私の質問: もっともらしい問題の説明を思いつくことができますか?それは、不注意な人をより悪い(または別の方法でひどい) ソート アルゴリズムの実装に自然に導くようなものです。

4

6 に答える 6

6

この質問を面接で使用して、応募者が一見複雑な質問の簡単な解決策に気付くことができるかどうかを確認していると思います.

[この仮定は間違っています -- MarkusQ]

あなたはあまりにも多くの情報を与えています。

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

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

私は方向転換のペナルティを取り除きます。

もう 1 つの主要な手がかりは、アルゴリズムへの入力値、つまり整数のリストです。順列のリスト、またはすべての順列を提供します。これにより、O(n!) アルゴリズムが実際に期待される可能性があると考えるようになります。

私はそれを次のように表現します：

n 個の配達場所のすべての可能な順列のリストが与えられた場合、配達の各順列 (d 1、d 2、...、d n ) は次のように定義されたコストを持ちます。

P のコストが他の順列以下になるように順列 P を返します。

実際に行う必要があるのは、最初の順列を読み取ってソートすることだけです。

彼らがコストを比較するために単一のループを構築する場合、彼らのアルゴリズムの大きなランタイムが何であるかを彼らに尋ねます.nは配達場所の数です（別のトラップ）.

于 2009-03-13T17:49:48.503 に答える
2

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

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

例えば：

d0 = 0

deliveries = (-1,1,1,2)

この場合の最適なパスは のよう1 > 2 > 1 > -1です。

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

于 2009-03-13T16:48:22.457 に答える
1

これは、巡回セールスマンというより、ナップザック問題を思い起こさせます。しかし、ナップサックは NP 困難な問題でもあるため、問題をナップサックと関連付けると、人々をだまして動的計画法を使用して複雑すぎる解決策を考えさせることができる可能性があります。基本的な問題は次のとおりです。

重量 W を超えることなく、少なくとも V の値を達成できますか?

ここで、問題は、V が一意である場合に、かなり良い解決策を見つけることができることです。たとえば、次のようになります。

各タイプのアイテム j が重量単位 (vj = pj/wj) ごとに異なる値を持つナップザック問題は、最も簡単な NP 完全問題の 1 つと見なされます。実際、経験的な複雑さは O((log n)2) のオーダーであり、非常に大きな問題を非常に迅速に解決できます。たとえば、2003 年には、n = 10,000 のインスタンスを解決するのに必要な平均時間は、市販のパーソナル コンピューターを使用して 14 ミリ秒未満でした1。

したがって、いくつかの停留所/パッケージが同じ vj を共有している可能性があることを述べて、人々に次の非常に難しい解決策について考えてもらいたいと思うかもしれません:

ただし、同じ値 vj を共有する複数のアイテムの退化したケースでは、vj = 定数である極端なケースでは、O(2N/2N) の複雑さを持つサブセット和の問題であり、はるかに困難になります。

したがって、値ごとの重みを値ごとの距離に置き換えて、いくつかの距離が実際には同じ値を共有し、縮退する可能性があると述べると、一部の人々はこの罠に陥る可能性があります。

于 2009-03-22T07:49:09.757 に答える
1

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

(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."

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

于 2009-03-18T16:51:36.950 に答える
0

これは単なる (NP-Hard)巡回セールスマン問題ではありませんか? あなたがそれをもっと難しくするつもりはないようです。

おそらく、実際のアルゴリズムが不明確になるように問題を表現します。たとえば、経路を単線の鉄道路線として記述することで、ドメインの知識からバックトラックがよりコストがかかることを推測する必要があります。

誰かが再帰的な比較をしたくなるような方法で質問を説明するのはどうですか? たとえば、「(これまでの) 最良の結果の最適な最大サブセットを使用して、アルゴリズムを高速化できますか?」

ところで、これの目的は何ですか - インタビュー対象者を拷問することが目的のようです。

于 2009-03-13T16:49:03.500 に答える
0

配送トラックが基地に戻らなければならない (往復する) 必要があるかどうかを明確にする必要があります。トラックが戻ってきた場合、単純な並べ替えでは最短ルートは生成されません。これは、最も遠い地点からベースまでの戻りの 2 乗に多くのコストがかかるためです。「出る」途中でいくつかのホップを逃して、帰りにそれらを使用すると、安くなることがわかります.

誰かをだまして間違った答えをさせた場合 (たとえば、すべての情報を提供しないなど)、それは彼らの愚かさなのか、それともあなたの欺瞞なのか?

賢者がエゴの嘘に注意を払わなければ、賢者の知恵はどれほど偉大でしょうか?

于 2009-03-23T08:58:32.577 に答える