3

私は次の問題（carrercupにある）のアルゴリズムについて考えています：

N個の頂点とN個のエッジを持つポリゴンが与えられます。すべての頂点にint番号（負の場合もあります）があり、すべてのエッジにset（*、+）の演算があります。毎回、ポリゴンからエッジEを削除し、edge（V1、V2）によってリンクされた2つの頂点を、値がV1 op（E）V2の新しい頂点にマージします。最後のケースは、2つのエッジを持つ2つの頂点であり、結果はより大きなものになります。指定されたポリゴンから取得できる最大の結果値を返します。

欲張り法だけでもいいと思います。つまり、k個のエッジを持つポリゴンの場合、折りたたみ時に最大数を生成するペア（p、q）を見つけます。（p、q）= max（{i演算j：i、j-隣接するエッジ）

次に、ポリゴンの再帰を呼び出します。1.関数CollapseMaxPair（P（k））-k個のエッジを持つポリゴンを取得し、k-1個のエッジを持つ「折りたたまれた」ポリゴンを返します。2。次に再帰：

 P = P(N);
 Releat until two edges left
     P =  CollapseMaxPair( P )
 maxvalue = max ( two remained values)

どう思いますか？

4

3 に答える 3

5

私はここでこの質問に答えました：グーグルインタビュー：ポリゴンの最大合計を見つけてください、そしてその質問はこれの複製であると私に指摘されました。まだ誰もこの質問に完全に答えていないので、ここにもこの答えを追加することにしました。

正しく識別（タグ付け）したように、これは実際に行列の乗算の問題と非常によく似ています（すばやく実行するために、どの順序で行列を乗算しますか）。

これは、動的アルゴリズムを使用して多項式で解くことができます。

代わりに、同様の、より古典的な（そして同一の）問題を解決します。数値、加算、乗算を含む数式が与えられた場合、それを括弧で囲む方法によって最大値が得られます。たとえば、 は以上になり6+1 * 2ます。(6+1)*26+(1*2)

入力a1 to an実数とo（1）、... o（n-1）のいずれか*またはを示し+ます。私たちのアプローチは次のように機能します。a1、... ajの最大式（括弧を付けた後）を表すサブ問題F（i、j）を観察します。このようなサブ問題のテーブルを作成し、F（1、n）がまさに私たちが探していた結果であることを確認します。

定義

F(i,j)

 - If i>j return 0 //no sub-formula of negative length
 - If i=j return ai // the maximal formula for one number is the number
 - If i<j return the maximal value for all m between i (including) and j (not included) of:
     F(i,m) (o(m)) F(m+1,j) //check all places for possible parenthasis insertion

これはすべての可能なオプションを通過します。正しさの証明は、サイズn = jiでの誘導によって行われ、非常に簡単です。

ランタイム分析を行いましょう：

小さなサブ問題の値を動的に保存しない場合、これはかなり遅くなりますが、このアルゴリズムを比較的速く実行することができます。O(n^3)

インデックスi、jのセルにF（i、j）が含まれる* nテーブルTを作成します。ここで、iよりも小さいjのF（i、i）とF（i、j）を埋めます。これらの値を直接計算できるため、各セルは対角線上に移動してF（i + 1、i + 1）を入力します（再帰式の以前のすべての値がすでにわかっているため、これをすばやく実行できます）。このnを繰り返します。 n個の対角線（実際にはテーブル内のすべての対角線）の回数と各セルの塗りつぶしには（O（n））が必要です。各セルにはO（n）セルがあるため、各対角線をO（n ^ 2）で塗りつぶします。つまり、すべての対角線を塗りつぶします。 O（n ^ 3）のテーブル。表に記入した後、問題の解決策であるF（1、n）が明らかにわかります。

テーブルに記入する順序

今、あなたの問題に戻ります

ポリゴンをnさまざまな数式（各頂点から開始する数式）に変換し、数式値のアルゴリズムを実行すると、必要な値が正確に得られます。

于 2013-01-19T07:55:51.233 に答える
1

欲張りアルゴリズムが失敗する場合は次のとおりです。

ポリゴンが頂点A、B、C、D（左上、右上、右下、左下）を持つ正方形であると想像してください。これにより、エッジ（A、B）、（A、D）、（B、C）、および（C、D）が得られます。

重みをA=-1、B = -1、C = -1、D=1,000,000とします。

A (-1) ------ B (-1)  
|             |  
|             |  
|             |  
|             |  
D(1000000) ---C (-1)

明らかに、最善の戦略は、（A、B）、次に（B、C）を折りたたむことです。これにより、Dだけで終わる可能性があります。ただし、アルゴリズムは（A、D）または（D、C）のいずれかで始まり、最適ではありません。

最小合計を組み合わせる欲張りアルゴリズムにも同様の弱点があるため、別のことを考える必要があります。

私は、すべての正の数を一方の側に、すべての負の数をもう一方の側にまとめようとする方法を理解し始めています。

最初のポリゴンを完全に状態と考えると、エッジが折りたたまれている場合、すべての可能な子状態が後続のグラフであると想像できます。これにより、木のような構造が作成されます。BFSまたはDFSは、最終的には最適なソリューションを提供しますが、最悪の場合、ツリー全体をトラバースするという犠牲を払って、おそらくあなたが望むほど効率的ではありません。

あなたが探しているのは、このツリーを検索するための貪欲な最良優先アプローチであり、これはおそらく最適です。おそらく、それを介してA *のような検索を作成できますが、許容できるヒューリスティックが何であるかはわかりません。

于 2013-01-18T17:02:09.007 に答える
0

欲張りアルゴリズムは機能しないと思います。頂点をA=0、B = 1、C = 2とし、エッジをAB = a-5b、BC = b + c、CA=-20とします。欲張りアルゴリズムは、最初に値3を評価するためにBCを選択し、次にAB、値、-15を選択します。ただし、使用するより良いシーケンスがあります。最初にABを評価し、値を-5にします。次に、BC、値-3を評価します。しかし、私はより良いアルゴリズムを知りません。

于 2013-01-18T15:38:26.800 に答える