19

形式のデカルト ポイントがほとんどありません: (x,y)
ここで、x と y は両方とも非負の整数です。

たとえば
、 (0,0) 、 (1,1)、 (0,1)


上記の点を、ある点から別の点に移動すると
x または y が 1 ずつ変化する ように配置するアルゴリズムが必要です。


つまり、斜め移動は避けたい。

したがって、上記の点は
(0,0)、(0,1)、(1,1) のように配置されます。

同様に、(0,0)、(1,1)、(0,2)
の場合、そのような配置はありえません。

何と呼べばいいのかわかりませんが、マンハッタンオーダー
と呼んでいます。

誰でも助けることができますか？

4

6 に答える 6

12

頂点を繰り返さない配置を探している場合:

あなたが探しているように見えるのは、グリッド グラフのハミルトニアン パスです。

これは、一般的なグリッド グラフの NP 完全であることが知られています。グリッド グラフのハミルトン パスを参照してください。

したがって、ハミルトン経路/ユークリッド巡回セールスマン問題で知られている近似/ヒューリスティック/その他のアルゴリズムのいずれかで運を試すことができます。

繰り返すことができるアレンジメントを探しているが、アレンジメント内の可能な限り少ない数のポイントが必要な場合:

これも NP 完全です。上記の問題はそれに縮小することができます。これは、グラフにハミルトニアン パスがある場合にのみ、最小可能ウォークに n 個の頂点があるためです。

ポイントの配置だけを探している場合は、

次に、グラフが接続されているかどうかを確認するだけです。接続されていない場合、そのような配置はあり得ません。

深さ優先検索を実行して、それを把握できます。グラフが接続されている場合、深さ優先検索でもそのような配置が得られます。

より最適なものが必要な場合 (ただし、かなり高速な時間で)、ユークリッド巡回セールスマン問題の近似アルゴリズムを使用できます。

于 2010-07-16T18:22:15.223 に答える
4

頂点をポイントとし、エッジを有効なステップとしてグラフを作成できます。

次に探しているのは、このグラフのハミルトンパスです。これは、一般的な形式では、NP完全問題であり、既知の効率的な解決策（つまり、ポイント数に応じて適切にスケーリングされる解決策）がないことを意味します。ウィキペディアでは、 「ほとんどのグラフで高速」で役立つ可能性のあるランダム化アルゴリズムについて説明しています。

ランダムな頂点から開始し、訪問されていないネイバーが存在する場合は続行します。未訪問のネイバーがなく、形成されたパスがハミルトニアンでない場合は、ランダムに均一にネイバーを選択し、そのネイバーをピボットとして使用して回転します。（つまり、そのネイバーにエッジを追加し、ループを形成しないように、そのネイバーから既存のエッジの1つを削除します。）次に、パスの新しい端でアルゴリズムを続行します。

ただし、この特定の状況では、より効率的なソリューションが存在する可能性があります。

于 2010-07-16T18:07:06.587 に答える
2

これは、各ノードが最大で4つのエッジであるグラフと考えてください。次に、深さ/幅優先探索を実行します。

于 2010-07-16T18:07:59.327 に答える
1

これは、連続する各ポイント間の距離を最小化することで簡略化できます。（0,0）から（0,1）への移動は単純に1単位ですが、（0,0）から（1,1）への移動は実際にはsqrt（2）です。したがって、ポイントをグラフに配置してから、単純な最小-合計距離トラバーサル（巡回セールスマン）を実行すると、ポイントが正しく配置されるはずです。

編集：1より大きいステップが必要ない場合は、1より大きいエッジを追加しないでください。トラバーサルは引き続き正しく機能し、1より大きい移動が必要なパスは無視されます。

編集2：さらに明確にするために、任意のエッジ選択アルゴリズムを使用できます。スペースが対角線でない限り、2つのスペースを移動しても問題がない場合は、（0,2）と（0,4）の間にエッジを配置することを選択できます。最小距離アルゴリズムは引き続き機能します。エッジをスマートな方法で配置するだけで、任意の数の選択基準を使用して結果を決定できます。

于 2010-07-16T18:05:23.260 に答える
0

これを行う1つの方法は、座標の2つのソートされたリストを作成することです。1つはxで並べ替えられ、もう1つはyで並べ替えられます。次に、再帰的に解決策を見つけます。

コードが来る（まだどの言語かわからない;おそらく擬似コード？）...編集-とにかく私の答えは他のいくつかほど良くないので、気にしないでください。

于 2010-07-16T18:05:28.760 に答える
0

ブルート フォースの再帰的な REXX ルーチンはどうですか... 考えられるすべてのパスを試して、うまくいくパスを出力してください。

/* rexx */
point. = 0  /* Boolean for each existing point */
say 'Enter origin x and y coordinate:'
pull xo yo
point.xo.yo = 1  /* Point exists... */
say 'Enter destination x and y coordinate:'
pull xd yd
point.xd.yd = 1  /*  Point exists... */
say 'Enter remaining x and y coordinates, one pair per line:'
do forever
  pull x y
  if x = '' then leave
  point.x.y = 1
end

path = ''
call findpath xo yo path
say 'All possible paths have been displayed'
return

findpath: procedure expose point. xd yd
arg x y path
if \point.x.y then return               /* no such point */
newpoint = '(' || x y || ')'
if pos(newpoint, path) > 0 then return  /* abandon on cycle */
if x = xd & y = yd then                 /* found a path */
  say path newpoint
else do                                 /* keep searching */
  call findpath x+1 y path newpoint
  call findpath x-1 y path newpoint
  call findpath x y+1 path newpoint
  call findpath x y-1 path newpoint
  end
return

セッションの例:

Path.rex
Enter origin x and y coordinate:
0 0
Enter destination x and y coordinate:
2 2
Enter remaining x and y coordinates, one pair per line:
0 1
1 1
2 1
1 2

 (0 0) (0 1) (1 1) (2 1) (2 2)
 (0 0) (0 1) (1 1) (1 2) (2 2)
All possible paths have been displayed

ただし、これを大きなもので試さないでください。非常に長い時間がかかる可能性があります。しかし、その質問は、最適なソリューションであることについては何も言及していません。

于 2010-07-16T20:52:36.093 に答える