HSPポータル
サイトマップ お問い合わせ


HSPTV!掲示板


未解決 解決 停止 削除要請

2016
0116
青葉HSPでの、幅優先探索のプログラムの作り方8未解決


青葉

リンク

2016/1/16(Sat) 23:48:57|NO.74155

ttp://blog.higashisanmyaku.jp/?eid=22
(hは抜いてあります)
上記のサイトにある8パズルのプログラムを用いて
幅優先探索を用いて、自動で解答を作成するプログラムを作成したいのですが
HSPでの幅優先探索のプログラムがわからないため
ご教示賜りますようよろしくお願いいたします



この記事に返信する


スペース

リンク

2016/1/17(Sun) 00:47:36|NO.74156

正確性は保証できないけどざっと計算した限り、25手先で7000万に分岐します。
この方式でやるのは無理があるのではないでしょうか?

幅優先探索自体詳しくは知らないのですがwiki見た限りだと、
樹の枝のようにどんどん分岐していく感じですか・・・

探索範囲=10//手 sdim パターン,100000,探索範囲 分岐=4 repeat 探索範囲 ct=cnt repeat 分岐 パターン.ct + ""+cnt\4+"" loop pos 0,cnt*40:mes ""+分岐+""+パターン.cnt+"" 分岐*4 loop
このプログラムを実行してみればわかりますが、たった10手先でも膨大な数です。
とりあえずパッと思いついたデータの管理方法としては配列変数を探したい手数分用意し、各配列変数に各手の情報を並べて入れる・・・というものです。
二次配列で管理したほうが遥かに楽ですが、数も膨大になりますしメモリや速度的にはどっちが良いのかまではわかりません。



青葉

リンク

2016/1/17(Sun) 01:33:43|NO.74158

スペース様

回答有り難うございます。
プログラム初心者なので殆どわからないのですが、丁寧に回答頂きありがとうございました。

ttp://homepage3.nifty.com/aokura/html5/jscript/8puzzle.html
(はじめのhを抜いています)
上記のサイトようなものをHSPで作りたいと思ったのですが
HSPではこういったような自動解答プログラムを作成することは不可能なのでしょうか?



スペース

リンク

2016/1/17(Sun) 13:28:59|NO.74161

ちなみにHSP掲示版はhを抜く必要はありませんよ。
普通に貼って大丈夫です。

JavaScriptはあまり知らないのですが、HSPでできるか少し試してみます。



3k

リンク

2016/1/17(Sun) 14:25:30|NO.74162

確かにN手先でたどり着く盤面は”出した手の順番も考慮する”とナイーブに計算すると4^Nなので爆発的な数字になりますが、そもそもとりうる盤面が「9個の数字を並び替えたもの」なので9!=362880通り程度しかありません。
数値だけ見れば現実的な時間でHSPでも探索可能な空間ですし、出した手の順番を考慮しないで探索すれば出来そうです。

幅優先探索はアルゴリズムの問題なので言語問わず実装できますが、HSPだと配列をキューに見立てて扱うのが一番素直かと思います。
(ラボ/キュー http://wiki.hsp.moe/%E3%83%A9%E3%83%9C%EF%BC%8F%E3%82%AD%E3%83%A5%E3%83%BC.html

なんとなくこういうアルゴリズム系の話は自分で手を動かさないと全く分からないと思いますので、スクリプトは貼らないですが最も素直な(愚直な)処理としてはこんな感じかなーと。
幅優先探索で目的の盤面を見つけるだけの処理で、「何手かかるか」とか「どういった手で打てばこうなるか」とかの情報は保持しない版です。

1. キューを確保する:キューの中身は盤面の状態が保持される想定、最大数は上述の通り362,880個
 プログラム的には次のような感じ。

queueNum = 0; 今キューに入っている盤面の個数 dim queue, 362880, mr*mc; 盤面のキュー

2. 最初の盤面をキューに入れる

; 最初の盤面をキューに入れる repeat mr : y=cnt : repeat mc : x=cnt queue(queueNum, y*mc+x) = pmap(y*mc+x) loop : loop queueNum++

3. キューが空になるまで4を繰り返す

; いくつキューの中身をとったか、のカウンタ queueIteratingIdx = 0 repeat if ( queueIteratingIdx >= queueNum ) : break; キューの中身をすべて調べた=キューは空 // 4〜の処理がここに入る queueIteratingIdx++ loop

4. キューの最初のものを取り出し、それが目的の盤面(ゴール)か確認する
 目的の盤面だったら探索は終了
 そうでない場合、そこから1手先の盤面を全てキューに入れる、ただし既に調べたキューはスキップする

; 取り出した盤面 queue(queueIteratingIdx) が目的の盤面か確認する if ( check( queue(queueIteratingIdx) ) ) { break; 目的の盤面だったら探索はここで終了 } ; 取り出した盤面 queue(queueIteratingIdx) から、1手先の盤面を列挙する : ただし、既にキューに入っていたり調べたことがある盤面の場合はスキップ ; 取り出した盤面 queue(queueIteratingIdx) で空欄の場所を探す empty = xxx ; 空欄の場所の上にピースがある場合、それを空欄の場所に動かした盤面を考える ; その盤面がキューに入っておらず、かつ調べたことがない場合キューに入れる ; 空欄の場所の右にピースがある場合、それを空欄の場所に動かした盤面を考える ; その盤面がキューに入っておらず、かつ調べたことがない場合キューに入れる ; 以下空欄の場所の「下、左」についても同様

正直こういう系のプログラム書いたことがない場合難易度相当高めです。
「何で上記の処理でいいのか?」、「どうすれば最短の手が求められるか」といったところに注目して考えてみてください。
たぶん、上記で書いた処理+そこそこ書かないと、目的のプログラムにはならないかなーと思いますが…。



スペース

リンク

2016/1/17(Sun) 14:27:14|NO.74163

このページ見る限りだと25手先まで読む必要はなさそうですね。
http://www.ic-net.or.jp/home/takaken/nt/slide/solve15.html

ただ私の技術じゃ実装は無理そう・・・他の型に任せます(´・ω・`)
お役に立てず申し訳ない・・・



スペース

リンク

2016/1/17(Sun) 14:32:19|NO.74165

被ってしまった・・・
まさに3kさんの言う通り、25手先まで読む必要はなかった。



cats

リンク

2016/1/17(Sun) 22:02:12|NO.74178

とてつもなく汚く、遅いです。
pythonのコードを参考にしたので、HSPでは書けない部分が出てきて、遠回りになりました。
どこかミスをしたらしく、難しい形は何分経っても解けません。
さらに、初心者の方には難しいモジュール機能を使用しているため、参考になるかは分かりませんが、一応載せておきます。
命令などで分からない点があったら聞いてください。

#runtime "hsp3cl" /*----- 8パズル操作モジュール -----*/ #module puzzle_state panel, state, size // コンストラクタ #modinit array panel_, array state_, int size_ size = size_ dim panel, size*size ; dim state, size*size ; repeat size*size panel(cnt) = panel_(cnt) state(cnt) = state_(cnt) loop return // パズルを生成 #modfunc gen_panel // 空き場所を確認 space = puzzle_get(thismod, "space") // 行と列 col = space / size raw = space \ size return // 変数名からデータ取得 #modcfunc puzzle_get str name ret = 0 switch name case "size" : ret = size : swbreak case "panel" : ret = varptr(panel) : swbreak case "state" : ret = varptr(state) : swbreak case "space" // 空き場所(0) foreach panel if ( panel(cnt) == 0 ) { ret = cnt break } loop swbreak swend return ret #global /*----- 8パズル用キュー -----*/ #module puzzle_queue panel, state, size, index // コンストラクタ #modinit var puzzle_ // 各要素を仮に取得 size_ = puzzle_get(puzzle_, "size") dupptr panel_, puzzle_get(puzzle_, "panel"), 4*size_*size_, 4 dupptr state_, puzzle_get(puzzle_, "state"), 4*size_*size_, 4 // 初期化 index = 0 dim size, 181440 dim panel, size_*size_, 181440 dim state, size_*size_, 181440 // コピー size(index) = size_ repeat size_ * size_ panel(cnt, index) = panel_(cnt) state(cnt, index) = state_(cnt) loop // 追加済み index++ return // 取り出す #modfunc dequeue var puzzle_ // 一度破棄してから作成 if vartype(puzzle_) == 5 : delmod puzzle_ newmod puzzle_, puzzle_state, panel(0), state(0), size(0) index-- // キューをずらす mov = 0 repeat index mov = cnt repeat size(0) * size(0) panel(cnt, mov) = panel(cnt, mov+1) state(cnt, mov) = state(cnt, mov+1) loop loop return // 追加 #modfunc enqueue var puzzle_ // 初期化 size_ = puzzle_get(puzzle_, "size") dupptr panel_, puzzle_get(puzzle_, "panel"), 4*size_*size_, 4 dupptr state_, puzzle_get(puzzle_, "state"), 4*size_*size_, 4 // 追加 repeat size_*size_ panel(cnt, index) = panel_(cnt) state(cnt, index) = state_(cnt) loop index++ delmod puzzle_ return // 空か #modcfunc isEmpty if ( index == 0 ) : return 1 return 0 #global /*----- 8パズル探索モジュール -----*/ #module #define assign2(%1, %2, %3, %4, %5, %6) %1(%2, 0) = %3 : %1(%2, 1) = %4 : %1(%2, 2) = %5 : %1(%2, 3) = %6 // 隣接リスト(3x3固定) #deffunc bf_search_init dim adjacent, 9, 4 assign2 adjacent, 0, 1, 3, -1, -1 assign2 adjacent, 1, 0, 2, 4, -1 assign2 adjacent, 2, 1, 5, -1, -1 assign2 adjacent, 3, 0, 4, 6, -1 assign2 adjacent, 4, 1, 3, 5, 7 assign2 adjacent, 5, 2, 4, 8, -1 assign2 adjacent, 6, 3, 7, -1, -1 assign2 adjacent, 7, 4, 6, 8, -1 assign2 adjacent, 8, 5, 7, -1, -1 return // 探索 #deffunc bf_search int size, array goal, array panel // 新規パズル dim none, size*size newmod puzzle, puzzle_state, panel, none, size // キューを作成 newmod queue, puzzle_queue, puzzle // 探索済みフラグ sdim visited, 64, 181440 : visited_index = 0 // 探索開始 while( isEmpty(queue) != 1 ) dequeue queue, puzzle repeat space = puzzle_get(puzzle, "space") if ( cnt == length2(adjacent) ) : break ; 要素数 x = adjacent(space, cnt) if ( x == -1 ) : break ; 隣接面無し // コピー dupptr c_panel, puzzle_get(puzzle, "panel"), 4*size*size, 4 dim b, size*size repeat size*size b(cnt) = c_panel(cnt) loop // 移動 ;mes strf("%d <= %d", space, x); b(space) = b(x) b(x) = 0 ;/* t = "" repeat size*size t += str(b(cnt)) + " " loop mes t ;*/ // 探索済みか key = "" : v = 0 repeat length(b) key += str(b(cnt)) + ":" loop repeat visited_index if ( visited(cnt) == key ) { ;mes key v = 1 break } loop if ( v == 1 ) : continue // 探索していない dupptr c_prev, puzzle_get(puzzle, "panel"), 4*size*size, 4 dim prev, size*size repeat size*size prev(cnt) = c_prev(cnt) loop newmod c, puzzle_state, b, c_prev, size // 終了 f = 1 repeat size*size if ( b(cnt) != goal(cnt) ) { f = 0 break } loop if ( f == 1 ) : mes "done" : return // 次 enqueue queue, c visited(visited_index) = key visited_index++ loop wend mes "nothing found..." return #global size = 3 goal = 1, 2, 3, 4, 5, 6, 7, 8, 0 ;panel = 5, 4, 2, 6, 7, 0, 8, 1, 3 ; NO ;panel = 8, 6, 7, 2, 5, 4, 3, 0, 1 ; NO ;panel = 1, 2, 3, 4, 5, 6, 7, 0, 8 ; OK fast panel = 5, 3, 0, 2, 1, 6, 4, 7, 8 ; OK fast ;panel = 5, 3, 6, 0, 1, 8, 2, 4, 7 ; OK slow bf_search_init bf_search size, goal, panel mes "quit" stop

参考:
http://qiita.com/masashi127/items/63d4f5b52895af939fca
http://www.geocities.jp/m_hiroi/light/pyalgo27.html



cats

リンク

2016/1/17(Sun) 22:09:57|NO.74179

NO.74178のコードですが、gen_panelは不要なので、削除しても構いません。
(代わりに隣接リストを使用しました。)



ONION software Copyright 1997-2021(c) All rights reserved.