5

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

指定されたポリゴンから取得できる最大の結果値を返します。

最後のケースでは、他の数値が負になる可能性があるため、2つのマージは必要ない場合があります。その場合、大きい方の数値を返すだけです。

私が問題にどのように取り組んでいるか：

 p[i,j] denotes the maximum value we can obtain by merging nodes from labelled i to j.
 p[i,i] = v[i] -- base case
 p[i,j] = p[i,k] operator in between p[k+1,j] , for k between i to j-1.
and then p[0,n] will be my answer.
Second point , i will have to start from all the vertices and do the same as above as this will be cyclic n vertices n edges.
The time complexity for this is n^3 *n i.e n^4 .

これより上手くできますか？

4

2 に答える 2

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:45:34.793 に答える
0

ブルートフォース検索の必要性を減らすことができると思います。例：チェーンがある場合

x + y + z

値が合計である単一の頂点に置き換えることができます。それ以上のことはできません。+ ve整数を扱う場合は、加算後に乗算を行う必要があります。したがって、すべてが正の場合は、すべての+チェーンを減らしてから、複数回減らします。

したがって、-veの数がある場合が残ります。単一の-ve数の戦略は非常に明白であり、2つの-ve数の場合はいくつかのケースがあり（--x-が正であることを思い出してください）、2 -ve数を超える場合は注意が必要です：- ）。

于 2013-01-19T07:50:25.897 に答える