GDD2011のDevQuizにチャレンジしたのでコード晒し （スライドパズル編）
GDD2011
先日「参加確定」のメール来ました！
「参加確定」ってとこにやや違和感あるものの、これで参加権を得たことになります。
ふー、一安心。
でも、なんで火曜なんやろ。。関西から日帰りってしんどいかな？
他に関西から参加される方いたら、どのようなスケジュールで行くかぜひ教えて下さい。
チャレンジクイズ
提出コード
前述の通り、コア部分のアルゴリズムは丸パクリなのでサラっと行きます。
参考にしたのはこちら。
‚P‚TƒpƒYƒ‹Ž©“®‰ð“šƒvƒƒOƒ‰ƒ€‚Ìì‚è•û
M.Hiroi's Home Page / Puzzle De Programming
M.Hiroi's Home Page / Puzzle De Programming
特にこちらの解説・コードを参考にしています。
Algorithms with Python / 幅優先探索と反復深化
「一人ゲーム」の時に要約勉強した「幅優先探索」「深さ優先探索」という言葉を覚えたとこですが、今回は「反復深化」で解を求めたいと思います。
枝刈りには「マンハッタン距離(MD)」を使用することにしました。
自分で実装したところと言えば、隣接リスト、マンハッタン距離、ボード、ゴールを可変にしたところや、壁の回避処理を付け加えたところくらいでしょうか。
完全には理解できていないとこもあるのでトライ＆エラーでチャレンジです。
ホント、何度でも回答提出して良いルールにも救われていますね。
# coding: utf-8 import os.path import time #カウンタ LC = 0 RC = 0 UC = 0 DC = 0 # 隣接リスト adjacent = [] # 距離 distance = [] # 距離を求める def get_distance(board): v = 0 for x in xrange(len(board)): p = board[x] if p == "0": continue if p == "=": continue #v += distance[p][x] v += distance[int(p)][x] return v # ゴールの局面 GOAL = [] # 盤面 board = [] # 動かした駒 move_piece = [None] * 200 move_history = [None] * 200 def convListToStr(array): arraybuf = [] arraybuf = filter((lambda x: x!=None), array) return "".join(map(str,arraybuf)) def checkLRUDcount(strAns): global LC global RC global UC global DC global LX global RX global UX global DX if strAns == "timeout": return True #文字列からLRUDカウント LC += strAns.count("L") RC += strAns.count("R") UC += strAns.count("U") DC += strAns.count("D") if LC > LX: return False elif RC > RX: return False elif UC > UX: return False elif DC > DX: return False return True # 下限値枝刈り法 def id_lower_search(limit, move, space, lower, w, h, s, tl): e = time.clock() if move == limit: if board == GOAL: global count count += 1 global result result = convListToStr(move_history) elif e - s > tl: count += 1 result = "timeout" else: for x in adjacent[space]: p = board[x] if p == "=": continue if move_piece[move] == p: continue # 駒を動かす board[space] = p board[x] = "0" move_piece[move + 1] = p move_distance = x - space if move_distance == -w: #上移動 move_history[move] = "U" elif move_distance == -1: #左移動 move_history[move] = "L" elif move_distance == 1: #右移動 move_history[move] = "R" elif move_distance == w: #下移動 move_history[move] = "D" new_lower = lower - distance[int(p)][x] + distance[int(p)][space] # 下限値枝刈り法 if new_lower + move <= limit: id_lower_search(limit, move + 1, x, new_lower, w, h, s, tl) # 元に戻す board[space] = "0" board[x] = p def get_board(w,h,b): new_board = [] for i in xrange(w*h): if b[i].isalpha(): #英数字 new_board.append(str(ord(b[i])-55)) else: new_board.append(b[i]) return new_board[:] def get_GOAL(w,h,b): new_GOAL = [] for i in xrange(w*h): if b[i] != "=": new_GOAL.append(str(i+1)) else: new_GOAL.append("=") new_GOAL[len(new_GOAL)-1] = "0" return new_GOAL[:] def setAdjacent(w,h): global adjacent adjacent = [] for i in xrange(w*h): buf = [] if i - w >= 0 and i - w < w*h: buf.append(i-w) if i - 1 >= 0 and i - 1 < w*h: if i % w != 0: #左端でなかったら buf.append(i-1) if i + 1 >= 0 and i + 1 < w*h: if i % w != w-1: #右端でなかったら buf.append(i+1) if i + w >= 0 and i + w < w*h: buf.append(i+w) adjacent.append(buf) def setDistance(w,h): global distance distance = [] for i in xrange(w*h): buf = [] if i != 0: for j in xrange(1,w*h+1): #距離計算 dx = (j-1)%w - (i-1)%w if (j-1)%w - (i-1)%w > 0 else -((j-1)%w - (i-1)%w) #横 dy = (j-1)/w - (i-1)/w if (j-1)/w - (i-1)/w > 0 else -((j-1)/w - (i-1)/w) #縦 #if dx < 0:dx = -dx buf.append(dx + dy) distance.append(buf) count = 0 result = "" def solve_slide(w, h, b, tl): s = time.clock() global board global GOAL board = get_board(w,h,b) GOAL = get_GOAL(w,h,b) setAdjacent(w,h) setDistance(w,h) n = get_distance(board) strAns = "" global result for x in xrange(n, 200): #print 'move ', x #print board id_lower_search(x, 0, board.index("0"), n, w, h, s, tl) if count > 0: break return result #メイン処理 LX = 0 RX = 0 UX = 0 DX = 0 N = 0 def main(start, end, min, max, tl, status): global LX global RX global UX global DX global N global count global move_piece global move_history #入力データ取得 inputfile = "input_status.data" if os.path.exists(inputfile): fi = open(inputfile, 'r') else: exit() #出力ファイル作成 outputfile = "output.data" fo = open(outputfile, 'w') #使うことができる L, R, U, D それぞれの総数 line = fi.readline().split(' ') LX = int(line[0]) RX = int(line[1]) UX = int(line[2]) DX = int(line[3]) N = int(fi.readline()) for i in xrange(N): print i+1 line = fi.readline().split(',') sta = line[0] w = int(line[1]) h = int(line[2]) b = line[3] if i + 1 < start: fo.write('\n') elif i + 1 > end: fo.write('\n') elif w * h < min: fo.write('\n') elif w * h > max: fo.write('\n') elif sta == status: # if b.find("=") == -1: strAns = solve_slide(w,h,b,tl) if checkLRUDcount(strAns) == True: fo.write(strAns + '\n') print strAns else: fo.write('\n') continue #fo.write(str(w) + "," + str(h) + "," + b + '\n') #グローバル変数初期化 count = 0 move_piece = [None] * 200 move_history = [None] * 200 # else: # fo.write('\n') else: fo.write('\n') fi.close() fo.close() if __name__ == "__main__": main(1,5000,0,99,300,"yet") #1問目から
実はアルゴリズムを変更しないままpython→cython→C言語と作り替えてみましたが、大した速度向上は見られず。
問題によっては速いこともあるかなー程度でした。
小手先ではなくアルゴリズムを工夫しろってことなんでしょうね。
経路探索アルゴリズム覚書
幅優先探索(breadth-first search、BFS)
幅優先探索 - Wikipedia
ある階層をすべて調べ、それが終わるとひとつ深い階層をすべて調べるということを繰り返す。
ある階層までの探索経路をキューに貯め、ひとつ深い階層の状態を追加していく。
○特徴
最適解(最短経路)が最初に見つかる。
メモリを大量消費する可能性がある。
devquizのスライドパズル
→マンハッタン距離で枝刈り
DevQuiz スライドパズル 解答 - saito’s blog
→枝刈りやマルチコア
Google DevQuiz 2011 解答例「スライドパズル」編 | ビットログ
→双方向・幅優先探索＋評価値
http://www.cattaka.net/sphpblog/index.php?entry=entry110912-211621
→幅優先＋枝刈り？答え合わせ大会の資料も。
yamablo » Google Developer Day Dev Quiz 〜スライドパズル〜
→幅優先＋パターン記録
深さ優先探索(depth-first search, DFS)
深さ優先探索 - Wikipedia
それ以上進めなくなるまで一つの経路を進み、進めなくなったら一手戻って別経路を調査する。
再起をつかって表現できる。
○特徴
最適解(最短経路)が最初に見つかるとは限らない
メモリ消費を抑えられる
反復深化深さ優先探索(iterative deepening depth-first search、IDDFS)
反復深化深さ優先探索 - Wikipedia
深さ優先探索の「深さ」に上限値を設定し、解が見つかるまで上限値を段階的に増やしていく。
深さ優先探索のメモリ効率と幅優先探索の完全性（分岐が有限の場合）を併せ持っている。
同じ経路探索を何度も行うことになるので、下限値枝刈りなどの工夫が必要となる。
○特徴
最適解(最短経路)が最初に見つかる。
メモリ消費を抑えられる
DevQuizのスライドパズルのひねた解法 — KaoriYa
GDD2011 DevQuiz スライドパズル - だらだらとだらだら
コンデンサの隣からひとこと
GDD2011 DevQuiz - 瓶詰堂日記
みなさん、双方向と組み合わせたり工夫しています。
双方向探索(bidirectional search)
双方向探索 - Wikipedia
同時に2つの方向から探索を行う。通常は初期状態と最終状態(ゴールした状態)から。
他の探索アルゴリズム(幅優先探索など)と組み合わせて使う。
↓このあたりからまだよく分かっていません。
ダイクストラ法
ダイクストラ法 - Wikipedia
ダイクストラ法（最短経路問題）
1. 初期化：スタートノードの値（最小コスト候補）を0，他のノードの値を未定義（または∞）に設定。
2. 確定ノードをピックアップすることができなくなるまで（＝変化がなくなるまで）以下のループを繰り返す：
2-1. まだ確定されていないノードのうち，最小の値を持つノードを見つけ，確定ノードとする（確定フラグを立てる）。
2-2. 確定ノードからの伸びているエッジをそれぞれチェックし，「確定ノードまでのコスト＋エッジのコスト」を計算し，そのノードの現在値よりも小さければ更新する （経路情報も必要であれば，「どこから来たのか」を表す変数が確定ノードを指すようにする）。
Google DevQuiz 回答アップ「スライドパズル編」 - from scratch
→ただし、距離を求める関数の中で。
ソルバー本体は幅優先＋枝刈り
A*（A-star, エースター）
A* - Wikipedia
Algorithms with Python / ヒューリスティック探索
4000問とかたくさん解いている人の中にはこれが多い気がする。
A*アルゴリズムについて復習した - Yoh Okunoの日記
→探索アルゴリズムは色々と関わりあっている。
GDD2011 DevQuiz のスライドパズルに挑戦してみました | blog.k11i.biz: GDD2011 DevQuiz のスライドパズルに挑戦してみました
→A*＋双方向探索
http://charites.info/archive/2011/09/16113910.php
→A*＋双方向探索
DevQuizの解答(ソースコード)晒し スライドパズル編 #gdd11jp | mzsm.me
その他参考
GDD2011 DevQuiz のスライドパズル晒し祭りをまとめてみた - Fire and Motion
探索 - Wikipedia
http://www.geocities.jp/m_hiroi/light/pyalgo05.html
Algorithms with Python / 幅優先探索と反復深化
GDD2011JP Sliding Puzzle
→5000問を168分で解くとかもう…
[GDD2011][DevQuiz]スライドパズルをPerlで解く｜キッズプレート、パスタおかわり
→Perlによる解答
[観] GDD2011 Japan の DevQuiz を解くために書いたコードを公開してみました
→パズルを手で解いて解答として出力
[Google] Google Developer Day 2011 DevQuiz - adakoda
→IDA*(反復深化A*)による解答
↓ここからアルゴリズム紹介・解説資料。大学などのプレゼン資料？
「ヒューリスティック探索」というのもひとつのキーワードだったかも。
2007年度 計算知能論A ヒューリスティクス探索
→アルゴリズム解説。A*やIDA*も
最適解を求める2 つの探索アルゴリズムのスーパーパズにおける性能比較について
知能処理アルゴリズム論 第2回 探索技法
