ポイント（都市）で「マップ」を生成するプログラムを作成しようとしています。ランダムな都市 (グラフで表される) のみを生成することは問題ではありませんが、それらの間に最小距離を設定する必要があります (たとえば、都市間の距離は 5 以上です)。約3000都市なので、効果的な解決策を探しています。
解決方法が思い浮かびませんので、どなたかご教授いただければ幸いです。
1088 次
3 に答える
1
マップを 10x10 の正方形のグリッドに分割すると、特定のポイントから 5 単位以内にあるポイントは、必ず (x +/- 5, y +/- 5) で定義される 4 つの正方形のいずれかに収まります。10x10 の正方形に最大 8 つのポイントが含まれる可能性がありますが、新しい各ポイントをそれぞれ最大 8 つのポイントを持つ 4 つの正方形に対してチェックする方が、他の何千ものポイントに対してチェックするよりも高速である可能性があります。
このアプローチで注意する必要がある最大のことは、整数除算演算子の浮動小数点から整数への変換演算子の負の数の動作が、プログラマーにとって有用ではなく、プロセッサにとって簡単になるように選択されているため、注意する必要があることです。一部の座標が正で一部が負の場合の異常。たとえば、xが でありint、 one が を計算する場合、-9 から +9 までの x 値に対して はゼロint col = x/10;にcolなります (つまり、点 (0,0) を含むボックスは、各次元で本来あるべきサイズのほぼ 2 倍の大きさになります)。座標が負になる可能性がある場合は、除算を実行する前に正になるように調整する必要があります。
于 2013-10-30T20:51:45.167 に答える
0
約 3,000 の都市の場合、それらをマップにドロップして、最小距離の基準を確認することはおそらくそれほど不合理ではありません。チェック時間は O(n) のように長くなり、マップ上にすでに多くのポイントがあるほど、「衝突」が発生する可能性が高くなります。
どのくらい「ランダム」が必要ですか？マップを 5x5 の正方形のグリッドに分割し、ボックスの中央 2.5x2.5 にランダムに 1 つの点を配置すればうまくいくでしょうか? それは高速であり、衝突は発生しません。
都市の位置にどれだけのランダム性が必要かを実際に調べることは価値があるかもしれません.
于 2013-10-30T20:17:52.677 に答える