-3

次の 7 つの点 P1、P2、…、P7 が平面上に与えられ、その x 座標と y 座標は次のとおりです。

ポイント P1 P2 P3 P4 P5 P6 P7

x 値 10 12 19 11 12 14 18

Y 値 25 23 17 6 20 23 25

一番左の点から始まり、右端の点まで厳密に右に移動し、その後、厳密に左に戻って開始点に戻るという制限の下で、7 つのすべての点を結ぶ最短のクローズド ツアーを見つけたいと考えています。
この問題に対する動的なアプローチ(アルゴリズム)を提案できる人はいますか?

4

2 に答える 2

2

すでに述べたように、左から右へ、右から左へ 2^5 (32) 通りの可能なパスがあります。これらのそれぞれを評価し、最短のものを選択してください。

左に行くか右に行くかのどちらかで、各中間点を選択できます。したがって、2^5 の可能性があります。

于 2013-10-01T12:10:32.540 に答える
0

それは非常に単純です squareroot((x2-x1)^2+(y2-y1)^2) x2 は p2 の x であり、x1 は p1 の点であり、すべての距離を取り、最小の結果を取得します。

または、 dijekstra アルゴリズムも表示できます

于 2013-10-01T12:06:36.757 に答える