1

最初は別のドメインの問題がありましたが、現在は簡略化してグラフに変換しています。

グラフは

  • 双方向
  • 完全に接続された
  • 各頂点には正のコストがあります
  • 各エッジには負のコストがあります
  • 始点と終点が同じ

総ユーティリティ コストを最大化するノードのみをトラバースする必要があります。

よく知られたグラフの問題のように聞こえますか?

例：

V = {A, B, C}

vertex points = {0, 6, 5}

edge cost = {[A,B]=-8, [A,C]=-2, [B,C]=-10}

したがって、解決策は、頂点Cのみにアクセスして戻ってくることです。合計1点になります。

頂点に到達すると、ポイントは 0 になります。

4

2 に答える 2

3

これを景品巡回セールスマン問題といいます。

于 2013-04-24T16:08:34.423 に答える
1

これは、最長経路問題と言い換えることができるため、一般的なグラフでは NP 困難である必要があると思います。方法を確認するために、エッジと頂点のコストを変更します。

c(e)をエッジ のコストとeし、 を頂点e = {u,v}およびc(u), c(v)のコストとuするv。各エッジの新しいコストを に設定しc_new(e) = c(e) + 1/2*(c(u)+c(v))ます。この背後にある直感は、頂点からそれ自体へのサイクルでは、通過する各頂点に付随する 2 つのエッジを使用するため、各エッジの頂点の半分のコストしかカウントできないということです。到着時にコストの半分を支払い、頂点を離れるときに残りの半分を支払うと考えてください。

エッジのコストを変更した後、頂点コストはエッジのコストで考慮されるため、無視できます。問題は、エッジの重みの合計を最大化する単純なパスを見つけることになります。これは、最長パス問題として知られる NP 困難な問題です。

于 2013-04-23T16:50:03.323 に答える