php - スパイラルアルゴリズムでソートする座標(x,y)リスト

Question

スパイラルアルゴリズムでソートする座標のリストがあります。私の必要性は、エリアの真ん中から始めて、任意の座標に「触れる」ことです。

これを簡略化するために、(並べ替えられていない) 座標のリスト (x、y は次の画像で「ドット」でマークされています) の表現です。

座標の CSV リストはこちらから入手できます。
X は左から右に
増加 Y は TOP から BOTTOM に増加

すべての座標は次の座標に隣接していませんが、代わりに 1 つまたは 2 つのサイコロ (場合によってはそれ以上) によって離れています。

領域の中心から始めて、らせん状の動きで任意の座標に触れる必要があります。

各座標を解析するために、私はこの PHP アルゴリズムを起草しました:

 //$missing is an associative array having as key the coordinate "x,y" to be touched
 $direction = 'top';
 $distance = 1;
 $next = '128,127';     //starting coordinate
 $sequence = array(
     $next;
 )
 unset($missing[$next]);
 reset($missing);
 $loopcount = 0;
 while ($missing) {
    for ($loop = 1; $loop <= 2; $loop++) {
        for ($d = 1; $d <= $distance; $d++) {
            list($x,$y) = explode(",", $next);
                if ($direction == 'top')    $next = ($x) . "," . ($y - 1);
            elseif ($direction == 'right')  $next = ($x + 1) . "," . ($y);
            elseif ($direction == 'bottom') $next = ($x) . "," . ($y + 1);
            elseif ($direction == 'left')   $next = ($x - 1) . "," . ($y);
            if ($missing[$next]) {
                unset($missing[$next]);     //missing is reduced every time that I pass over a coordinate to be touched
                $sequence[] = $next;
            }
        }
            if ($direction == 'top')    $direction = 'right';
        elseif ($direction == 'right')  $direction = 'bottom';
        elseif ($direction == 'bottom') $direction = 'left';
        elseif ($direction == 'left')   $direction = 'top';
    }
    $distance++;
 }

しかし、座標は互いに等距離ではないため、次の出力が得られます。

はっきりと見えるように、中央の動きは正しいのに対し、座標位置に応じて、特定の瞬間に各座標間のジャンプが一貫しなくなります。

代わりに、このようなアプローチを取得するためにコードを変更するにはどうすればよいですか?

問題を単純化/軽減するには: 上の画像のドットは、セールスマンが定期的に訪問しなければならない都市であると想像してください。エリアの真ん中にある「都市」から始めて、次に訪れる都市は、出発点に近い都市と、出発点の北、東、南、西にある都市です。セールスマンは、開始地点のラウンドで隣接するすべての都市を訪れていない限り、それ以上の都市を訪れることはできません。すべての都市は 1 回だけ訪れる必要があります。

Answer 1

アルゴリズム設計

まず心を解放し、スパイラルを考えないでください！:-) 次に、アルゴリズムの制約を定式化しましょう (セールスマンの視点を使用しましょう)。

私は現在都市にいて、次にどこへ行くかを探しています。私は都市を見つける必要があります:

• 今まで行ったことのない場所
• 可能な限り中心に近い（らせんを維持するため）
• それは私の現在の都市にできるだけ近い

ここで、これら 3 つの制約が与えられれば、スパイラルを作成する決定論的アルゴリズムを作成できます (少なくとも、与えられた例では、より多くの労力を必要とするケースを作成できる可能性があります)。

実装

まず、任意の方向に歩くことができるため、通常はユークリッド距離を使用して距離を計算します。

次に、次に訪れる都市を見つけます。

$nextCost = INF;
$nextCity = null;
foreach ($notVisited as $otherCity) {
    $cost = distance($current_city, $other_city) + distance($other_city, $centerCity);
    if ($cost < $nextCost) {
        $nextCost = $cost;
        $nextCity = $otherCity;
    }
}
// goto: $nextCity

訪問する都市がなくなるまで、これを繰り返します。

それがどのように機能するかを理解するには、次の図を検討してください。

私は現在黄色の円にいます。ここまでのスパイラルは正しいと仮定します。黄色、ピンク、青の線の長さを比較してみましょう。これらの線の長さは、基本的に距離関数を使用して計算したものです。どの場合でも、次の正しい都市の距離が最小であることがわかります (少なくとも、どこにでも同じ数の点がある限り、おそらく反例を簡単に思いつくことができます)。

これにより、問題の解決策の実装を開始できます。

(正しさ) 最適化

現在の設計では、反復ごとに現在の都市を残りのすべての都市と比較する必要があります。ただし、一部の都市は関心がなく、間違った方向に進んでいます。foreach上記のループに入る前に、いくつかの都市を検索スペースから除外することで、アルゴリズムの正確性をさらに最適化できます。この図を考えてみましょう:

あなたは今それらの都市に行きたくないでしょう（スパイラルを続けるために、あなたは後退すべきではありません）ので、それらの距離さえ考慮に入れるべきではありません. これを理解するのは少し複雑ですが、データポイントが提供された例のように均等に分散されていない場合、この最適化により、より乱れたデータセットに対して健全なスパイラルが提供されるはずです。

更新: 正しさ

今日、突然それが頭に浮かび、提案された解決策を再考しました。2 つのユークリッド距離に依存すると、望ましくない動作が発生する場合があることに気付きました。

青色の線が黄色の線よりも明らかに短く、優先されるケースを簡単に作成できます。しかし、それは螺旋運動を壊してしまう。このようなケースを排除するために、移動方向を利用できます。次の画像を考えてみましょう (手描きの角度で申し訳ありません)。

重要なアイデアは、以前の移動方向と新しい移動方向の間の角度を計算することです。私たちは現在黄色い点にいて、次にどこへ行くかを決める必要があります。前の点がわかれば、前の動きの方向を表すベクトルを取得できます (例: ピンクの線)。

次に、検討する各都市のベクトルを計算し、前の移動ベクトルに対する角度を計算します。そのベクトルが <= 180 度の場合 (画像のケース 1)、方向は OK ですが、そうでない場合 (画像のケース 2) は問題ありません。

// initially, you will need to set $prevCity manually
$prevCity = null;

$nextCost = INF;
$nextCity = null;
foreach ($notVisited as $otherCity) {
    // ensure correct travel direction
    $angle = angle(vectorBetween($prevCity, $currentCity), vectorBetween($currentCity, $otherCity));
    if ($angle > 180) {
        continue;
    }

    // find closest city
    $cost = distance($current_city, $other_city) + distance($other_city, $centerCity);
    if ($cost < $nextCost) {
        $nextCost = $cost;
        $nextCity = $otherCity;
    }
}
$prevCity = $currentCity;
// goto: $nextCity

角度とベクトルを正しく計算するように注意してください。それについてサポートが必要な場合は、さらに詳しく説明するか、単に新しい質問をすることができます.

Answer 2

問題は、座標をトラバースしない場合の if 条件にあるようです。つまり、角が丸くなっているためです。座標の前の計算を逆にしたelse条件は、それを修正します。