1

Xにはn個のノードがあり、Yにはm個のノードがあり、nはm未満です。セット X をセット Y に一致させ、X のすべてのノードを最後に取得する際に 2 つのエッジが交差しないように、完全に交差のないマッチング グラフが必要です。結果のグラフの重みの合計は最小限に抑える必要があります。動的プログラミングアルゴリズムを考案する。これは私がそれを考えた方法です：

X と Y のノードは x0 に配置され、xi は Y0、Yi などへの水平エッジを持つことができますが、Y は X よりも多くのノードを持ちます。 Y、または対角近傍 (i, j-1)、(i,j+1) を設定し、コストを最小化するエッジを選択します。また、X と Y で既に取得されているノードを追跡します。時間の複雑さ O( nm)

これを実装できるより良い方法はありますか。どんな助けでも大歓迎です。これは私が中間試験で受けた質問ですが、選択に任せました。

4

1 に答える 1

0

をとw(x, y)のノード間のエッジの重みとし、を頂点との解 (クロス フリー マッチング グラフの最小値)とします。ここで、とです。xXyYM(i, j){x_0, x_1, ..., x_i} subset X{y_0, y_1, ..., y_j} subset Yi < |X|j < |Y|

例M(0, j) = min( w(x_0, y_a) ) for 0 <= a <= j。M(i, i-1) = infinity「正しい」セットが小さい場合は一致しないためです。

接続されているかどうかのi, j2 つの可能性があるからです。その再帰のために、次のことが保持されます。x_iy_j

M(i, j) = min( w(i,j) + M(i-1, j-1), M(i, j-1) )
于 2014-03-06T11:00:55.187 に答える