このアルゴリズムは分かりますか？

Question

説明が曖昧かもしれませんが、よろしくお願いします。

まず座標(X,Y)上の(0,0)に点□を置きます。
次に置ける点の候補は(0,0)の上(0,1)下(0-1)左(-1,0)右(1,0)の
点□に接する4箇所でランダムに選びます。ここでは右(0,1)に■を置きます。

□■

次に置ける点の候補は、なるべく全体が塊（円）になるように□の上か下、
■の上か下になります。つまり□■■や■□■このようには置けません。
ここでは黒の上(1,1)がランダムで選ばれました。

　 ■
□■

次に置ける点の候補は1箇所（円になるように置くため）で□の上(0,1)です。

■■
□■

次に置ける点の候補は三角で示した場所です。
　△△
△■■△
△□■△
　△△
その候補を全部置き終えたら次のような候補になります
△■■△
■■■■
■□■■
△■■△

このようにして基本ランダムで選ばれた点が全体が塊（円）になるように置く
プログラムはどのような感じになるのでしょうか？

sgwjn · Accepted Answer

#5です。
リスト3以降のリストは、定形の処理で作成できると思います。
すでにN点は置き終えているとして、置いている点のX、Yの座標リストを以下すると、

used_x = [x0, x1, x2, x3, ..., xn]
used_y = [y0, y1, y2, y3, ..., yn]

置いている点の最大、最小座標は、

x_min = min(used_x)
x_max = max(used_x)
y_min = min(used_y)
y_max = max(used_y)

となり、次に置く際、新しく出現するX、Y座標は、上下左右に1ずつ拡張するわけですから、

new_x_min = x_min - 1
new_x_max = x_max + 1
new_y_min = y_min - 1
new_y_max = y_max + 1

となりますよね。
とすると、リスト3の
　△△　　　←ここ
△■■△
△□■△
　△△　　　←ここ
の部分は、

count = 0
for (y=new_y_min;;y=new_y_max)
{
　　for (i=x_min;i<=x_max;i++)　←四隅はリスト3には入れない
　　{
　　　　x_list3[count] = i
　　　　y_list3[count] = y
　　　　count++
　　}

　　if (y==new_y_max)
　　{
　　　　break
　　}
}

次に
　△△
△■■△
△□■△
　△△
↑　　　↑
ここ　　ここ
の部分は、

for (x=new_x_min;;x=new_x_max)
{
　　for (i=y_min;i<=y_max;i++)　←四隅はリスト3には入れない
　　{
　　　　y_list3[count] = i
　　　　x_list3[count] = x
　　　　count++
　　}

　　if (x==new_x_max)
　　{
　　　　break
　　}
}

という感じだと思います。
ついでにリスト4は、

x_list4 = [new_x_min, new_x_min, new_x_max, new_x_max]
y_list4 = [new_y_min, new_y_max, new_y_min, new_x_max]

でしょうか。必ず4点になりますよね？
あと、このサンプルは、座標は整数1刻みを前提に書いています。

このコードはアルゴリズムを説明するためだけに適当に書いたものですので、考え方としてはこんな感じという程度にご覧ください。

sgwjn · Answer

以前、私が同じようなプログラムを作った際に考えたアルゴリズムをこの問題に適用すると、

※初めの4点を置くまで
(1)原点を置く
(2)取りうる座標の候補リスト（リスト1）を作成（原点周りの4点）
(3)リスト1からランダムに1つ選択し、点を置く
(4)リスト1を破棄し、次に取りうる座標の候補リスト（リスト2）を作成（原点と(3)でおいた点の周辺4点）
(5)リスト2からランダムに1つ選択し、点を置く
(6)リスト2を破棄し、次点を置く（(5)をおいた時点で一意に決まるはず）

※以降の点を置く
(7)取りうる座標の候補リスト（リスト3）を作成（周りの8点）
(8)リスト3からランダムに1つ選択し、点を置く
(9)リスト3からおいた点の座標を削除
(10)リスト3の候補が無くなるまで(8)、(9)を繰り返す
(11)リスト3を破棄
(12)取りうる座標の候補リスト（リスト4）を作成（周りの4点）
…以降同様の手順を繰り返す

取りうる座標の候補は、その時点の点の置き方で判るはずです。
データ構造は、X座標、Y座標を別の1次元配列で保持し、インデックスをランダムに選択すれば良いかと思います。

x = [0,　0,　1,　1]
y = [0,　1,　0,　1]
　　 ↑ ↑　↑ ↑　インデックスをランダムに選択

学生の頃に考えたアルゴリズムですので、効率はあまり考慮していません。よろしければ参考まで。

noname#48699 · Answer

＞（次の）次に置ける点の候補は、なるべく全体が塊（円）になるように□
＞の上か下、■の上か下になります。つまり□■■や■□■このようには置
＞けません。

［確認］
２番目の■は、「□の上か下、１番目の■の上か下」はよくて、「□の左（■□）」はダメということは、１番目の■に制約（左右→上下、上下→左右）を受けている、ということですよね。
それが、質問文中で初めて現れる△マークの所（４番目の点の候補）では、無制約です。

ｎ番目の■は、(n-1)番目の★★★制約を受けない★★★ということですね(n>3)。

＞あくまで上下左右にくっつける形で増やしていきたいです。

この制約を受けていたら５点（？）で終了しませんか？。
また、質問文中の初めて現れる△マークの所と矛盾していませんか？。
また、次の所では、候補が半減してます（８→４→？）。

＞このようにして基本ランダムで選ばれた点が全体が塊（円）になるように
＞置くプログラムはどのような感じになるのでしょうか？

「制約を受けない」ということでしたら、
全座標の《原点からの距離による＝円》マスクデータを作り、原点からの距離が小さい順に（同値はランダムで）置いていけばいいのでは・・・。

episteme · Answer

> では(0,0)の斜め上(1,1)などは隣接する範囲に入ってますか？
> もし入ってるなら、それだと望むような処理ではないのです。

だから、入らないようにコード書けばえぇですよ。

＞for ( すべての隣接点(x,y)について ) {
＞ここに具体的な数字をいれてもらえないでしょうか？

/* 効率悪くてごめんなさい */
for ( x について ) {
　for ( y について ) {
　　if ( (x,y)にハコがなく、上下左右にハコがあるなら ) {
　　　...
　　}
　}
}

episteme · Answer

> そのやり方はどのようになるんですか？

アルゴリズムに忠実にコードを書けばいい。

int X, Y;
int n = とても大きな値;
for ( すべての隣接点(x,y)について ) {
　int r = (x,y)から原点までの距離
　if ( r < n ) { n = r; X = x; Y = y; }
}
(X,Y)に置く

episteme · Answer

「隣接する座標を列挙し、その中から"原点からの距離"が短いものを選ぶ」
ではダメですか?

このアルゴリズムは分かりますか？

#5です。

以前、私が同じようなプログラムを作った際に考えたアルゴリズムをこの問題に適用すると、

＞（次の）次に置ける点の候補は、なるべく全体が塊（円）になるように□

> では(0,0)の斜め上(1,1)などは隣接する範囲に入ってますか？

> そのやり方はどのようになるんですか？

「隣接する座標を列挙し、その中から"原点からの距離"が短いものを選ぶ」

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング