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

質問

説明が曖昧かもしれませんが、よろしくお願いします。

まず座標(X,Y)上の(0,0)に点□を置きます。
次に置ける点の候補は(0,0)の上(0,1)下(0-1)左(-1,0)右(1,0)の
点□に接する4箇所でランダムに選びます。ここでは右(0,1)に■を置きます。

□■

次に置ける点の候補は、なるべく全体が塊（円）になるように□の上か下、
■の上か下になります。つまり□■■や■□■このようには置けません。
ここでは黒の上(1,1)がランダムで選ばれました。

　 ■
□■

次に置ける点の候補は1箇所（円になるように置くため）で□の上(0,1)です。

■■
□■

次に置ける点の候補は三角で示した場所です。
　△△
△■■△
△□■△
　△△
その候補を全部置き終えたら次のような候補になります
△■■△
■■■■
■□■■
△■■△

このようにして基本ランダムで選ばれた点が全体が塊（円）になるように置く
プログラムはどのような感じになるのでしょうか？

回答No.6

sgwjn · ベストアンサー

#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刻みを前提に書いています。

このコードはアルゴリズムを説明するためだけに適当に書いたものですので、考え方としてはこんな感じという程度にご覧ください。

お礼

ご返答ありがとうございます。
試してみてできました。
理想とする結果になり満足しています。ありがとうございます。

回答No.5

sgwjn

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

※初めの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]
　　 ↑ ↑　↑ ↑　インデックスをランダムに選択

学生の頃に考えたアルゴリズムですので、効率はあまり考慮していません。よろしければ参考まで。

お礼

ご返答ありがとうございます。
あまり理解できないのですが、
＞取りうる座標の候補リスト（リスト3）を作成（周りの8点）
とあるのですが、具体的にプログラムではどのように書けば良いのでしょうか？
始めの8点ぐらいまでなら頭の中で考えてリストを用意すればいいのでしょうが、、、増えてきますし、、
つまり仰っているのは決まった形のプログラムだと思いますが、それが分からないです。

回答No.4

noname#48699

＞（次の）次に置ける点の候補は、なるべく全体が塊（円）になるように□
＞の上か下、■の上か下になります。つまり□■■や■□■このようには置
＞けません。

［確認］
２番目の■は、「□の上か下、１番目の■の上か下」はよくて、「□の左（■□）」はダメということは、１番目の■に制約（左右→上下、上下→左右）を受けている、ということですよね。
それが、質問文中で初めて現れる△マークの所（４番目の点の候補）では、無制約です。

ｎ番目の■は、(n-1)番目の★★★制約を受けない★★★ということですね(n>3)。

＞あくまで上下左右にくっつける形で増やしていきたいです。

この制約を受けていたら５点（？）で終了しませんか？。
また、質問文中の初めて現れる△マークの所と矛盾していませんか？。
また、次の所では、候補が半減してます（８→４→？）。

＞このようにして基本ランダムで選ばれた点が全体が塊（円）になるように
＞置くプログラムはどのような感じになるのでしょうか？

「制約を受けない」ということでしたら、
全座標の《原点からの距離による＝円》マスクデータを作り、原点からの距離が小さい順に（同値はランダムで）置いていけばいいのでは・・・。

お礼

ご返答ありがとうございます。
すいません、説明が矛盾していました。
自分が言いたかったのは、とにかく塊（円というより）にして
増やしていきたいということでした。
例えば、これもちょっと分かり難いのですが、

　 ■
　 ■■　
■■■■■
■■■■
　 ■■　
　 ■

よりも

■■■■
■■■■
■■■■
■■■　

の方が塊っぽいですよね？（こういう説明の仕方が良くないというのは
承知しているのですが、これしか思い浮かばないので・・・）
なので

　 ■■
■■■■
■■■■
　 ■■　

こうなった後は角を埋めていくということになります。

回答No.3

επιστημη（@episteme）

> では(0,0)の斜め上(1,1)などは隣接する範囲に入ってますか？
> もし入ってるなら、それだと望むような処理ではないのです。

だから、入らないようにコード書けばえぇですよ。

＞for ( すべての隣接点(x,y)について ) {
＞ここに具体的な数字をいれてもらえないでしょうか？

/* 効率悪くてごめんなさい */
for ( x について ) {
　for ( y について ) {
　　if ( (x,y)にハコがなく、上下左右にハコがあるなら ) {
　　　...
　　}
　}
}

お礼

ご返答ありがとうございます。
今試してみたのですが、仰っていることができました。
ありがとうございます。
もうランダムに拘らなくて、これでいいのかもしれませんね（今頃気づいたんですが、ランダムしようがしまいがそんなに変わらないですし）

回答No.2

επιστημη（@episteme）

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

アルゴリズムに忠実にコードを書けばいい。

int X, Y;
int n = とても大きな値;
for ( すべての隣接点(x,y)について ) {
　int r = (x,y)から原点までの距離
　if ( r < n ) { n = r; X = x; Y = y; }
}
(X,Y)に置く

お礼

ご返答ありがとうございます。
すいません、いまいちこのイメージが掴めないのですが（なので質問立てました）
まず＞隣接する座標を列挙し、という隣接する範囲が具体的に分からないのです・・・
□(0,0)を基準として上(0,1)下(0,-1)左(-1,0)右(1,0)は隣接する範囲ですよね？
では(0,0)の斜め上(1,1)などは隣接する範囲に入ってますか？
もし入ってるなら、それだと望むような処理ではないのです。
あくまで上下左右にくっつける形で増やしていきたいです。
できれば
＞for ( すべての隣接点(x,y)について ) {
ここに具体的な数字をいれてもらえないでしょうか？

回答No.1

επιστημη（@episteme）

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

お礼

ご返答ありがとうございます。
たしかにその方法でも似たようなことなのでいいと思います。
そのやり方はどのようになるんですか？