全国高等専門学校プログラミングコンテスト一関大会
(この本文は約 13,000 文字もあります)
第25回高専プロコン(一関大会)と同時開催された,第6回 NAPROCK 国際プロコンの競技部門に東京大学チームとして ioryz, mfumi2 と参加し,champion を頂きました.以下,自分たちが作成したプログラムについての解説記事になります.
ソースコードは https://github.com/natrium11321/procon2014_ut に公開しています.
目次
- NAPROCK とは
- 競技ルール
- 開発環境
- 基本的なアプローチ
- ジグソーパズル
- スライドパズル
- 高速化
- システム
- readable, sustainable なコード
- まとめ(現役生に言いたいこと)
NAPROCK とは
高専プロコンと NAPROCK を混同している人が多いので一応解説します.NAPROCK は 高専プロコンと同一のルールで同時開催されるものの,両者は別の大会として扱われます.高専プロコンにエントリーした高専生は自動的に NAPROCK にもエントリーしますが,ハノイ,大連などの国外の大学は NAPROCK にのみ参加するという形で行われます.国内の大学は今年度から(来年度もそうかは分かりませんが)NAPROCK に参加することが出来るようになりました.従って,NAPROCK としての優勝は東京大学ですが,高専プロコンとしての優勝は大阪府大高専となり,両者は区別されます.
競技ルール
http://www.procon.gr.jp/uploads/procon25/Apply25.pdf (PDF 注意)の 8 ページ以降を参照してください.
開発環境
以下の環境で開発を行いました.実質の開発期間は8月頭〜本戦までで約2ヶ月半,週三回程度集まりました.総行数約 20,000 行,508 コミットです.
- OS
- 言語:C++11*2
- コンパイラ
- ライブラリ
- boost(全般,画像処理(boost.gil),ネットワーク(boost.asio))
- Qt (UI)
- Intel TBB(スレッドライブラリ)
- TC Malloc(高速メモリ管理)
- sparsehash(高速ハッシュテーブル)
- ビルドツール:CMake
- エディタ・IDE:Sublime Text 3, vim, emacs, Qt Creator
- デバッガ:lldb, gdb
- バージョン管理:Git (on github)
基本的なアプローチ
今回の問題は,与えられた断片画像(以下,ピース)から元の画像を推定する問題(ジグソーパズル)と,選択・交換操作を繰り返して全てのピースを少ないコストで正しい位置へ運ぶ問題(スライドパズル)に分けられます.この二つのパズルの解法は,基本的に独立に考えることが出来ます.僕達のチームでは,mfumi2 がジグソーパズルを,僕と ioryz がスライドパズルをそれぞれ担当しました.
ジグソーパズル
ジグソーパズルについては,実はもう少し成果を昇華させて,何らかの形で発表出来ないかと考えています.従って,現段階におけるアルゴリズムの詳細やソースコードの公開は控えさせて頂きます.お見せ出来る形になるまでしばしお待ちください.
(以下,mfumi2 の文章を拝借しました)
写真画像のジグソーパズルというと一見簡単そうに見えますが,実は結構難しく,画像処理系の学会である CVPR にも 2009 年から地味に毎年 1 本ずつぐらい論文が投稿されています.最新のだと ECCV 2014 にあります.
いろいろと既存の手法を参考にしつつ,メンバーと話合いながら実装した結果,最新の ECCV のものにほぼ匹敵するというか,論文内で使用されているあるデータセットに対して 1% ほど精度が良く,かつ高速なものができました(精度97%).とはいっても問題によっては人間がぱっと見て明らかにおかしいものができる場合があり,まだまだ良い手法があるはずだと思います.せっかくなのでこの件についてはもう少し考えていきたいと思っています.
(一番代表的なアプローチ(かつ多分最初に思いつくの)はピース間に類似度というか距離を定義して,その距離の和が最小になる組み合わせを見つけるというものですが,本質的に巡回セールスマン問題の類題に帰着されるので厳密解を見つけるのが困難であり,またその問題の厳密解を見つけたとしてそれが本当の解であるという保障はどこにもありません.)
ちなみに,大会で出題された問題については,単純な貪欲的アプローチでも解くことが出来たようです.
スライドパズル
以下を実装することで,沖縄高専のみなさんが作ってくれた練習競技場の全てのタイトル*4において1位,または1位タイを取る事が出来ました.
基本的な方針は,他高専や他大学と同じでビームサーチです*5.
小さなサイズ用 (AI名: kurage)
主に 10×10 以下の小さなサイズの問題については,以下の二種類の操作を基本遷移としたビームサーチを用いました.
- 交換操作:上下左右の4通りの移動が行えます.但し,
- 選択セルが盤面の端や角にいる場合は,盤面からはみ出る方向には移動しません.
- 直前の遷移も交換操作だった場合は,直前の移動を打ち消す方向には移動しません.
- 選択操作:盤面のサイズ (H*W) と同じ通り数の選択が行えます.但し,
- 直前の遷移も選択操作だった場合は,選択操作を行いません.
- 現在選択しているピースと同じピースは選択しません.
- 最後の一回の選択操作の時,盤面の偶奇*6が完成状態の偶奇と一致するようなピースしか選択しません.
- 探索の高速化を図るため,既に正しい位置に存在するピースは選択しません.
- 探索の高速化を図るため,現在選択しているピースが,その正しい位置に近い位置(一致,又は条件によってはその一近傍)に存在する場合のみ,選択操作を行います.
評価関数
用いた評価関数は以下です.http://heuristicswiki.wikispaces.com/N+-+Puzzle を参考にしました.
- manhattan distance : 各ピースの現在の位置と正しい位置のマンハッタン距離の総和.
- linear conflict : 同一軸上にある2つのピースの対について、両ピースの完成位置も同一軸上にあって、かつそれぞれの正解位置の左右関係(または上下関係)と現在のピースの左右関係(または上下関係)が入れ替わっているものの数。
- variance : 正しいピースが存在しないマスの座標 (x, y) についての統計分散の和 ( + ).
- random : [0, 1] 上の一様乱数に (現在の manhattan distance)/(最初の manhattan distance) を掛けたもの.
- squared manhattan : 各ピースの現在の位置と正しい位置のマンハッタン距離の二乗の総和.
- weighted manhattan : 正しい位置が端の方に存在するピースについては大きな重みを,中央付近のピースについては軽い重みを付けた manhattan distance.
最終的な盤面の評価値は,上記の評価関数をある結合係数で線形結合した値を用います.この結合係数は ioryz に最適化して貰いました.練習競技場の問題番号 6 phycolow (8×8, 交換コスト3) に対して上記の評価関数を用いて解を計算すると,ビーム幅 4,000 で概ね以下の様な交換コストが得られました.
- manhattan distance のみ : 1700 ~ 1500
- 上記 + linear conflict : 1500 ~ 1400
- 上記 + variance : 1500 ~ 1350
- 上記 + random : 1450 ~ 1350
- 上記 + squared manhattan : 1250 ~ 1150
個人的には squared manhattan の発見が一つのブレイクスルーだったと思っています.遠いところにあるピースほど大きな重みをかけることで,最終的に遠い二つのピースが交換されたような状態に陥ってしまう,といった現象を防ぐことが出来ます.また,評価関数に乱数を加えると,万が一そのような状態に陥った場合に,その状態から脱出することが出来るようになります.
weighted manhattan は問題番号 13 沖縄高専 (3×16) のような縦横比の偏った問題に対して威力を発揮しました.
多様性の確保
ビームサーチを用いる際は,解の多様性を確保するのが大事だと言われています.これは,似たような盤面ばかりが候補に存在すると,せっかく複数の候補を持つ意味が失われ,互いの弱点を補うことが出来なくなってしまうためです.
そこで僕たちは,候補の多様性を確保するため,同一盤面の除去を行いました.実際に除去を行うと分かりますが,今回の問題でも意外と同一状態(各ピースの位置,選択しているピース,選択回数が一致している状態)は多く存在していました.同一性の判定には,zobrist hashing*7 を用いたハッシュテーブルを使いました.ハッシュテーブルには,google が公開している sparsehash を使いました.
また,多様性を確保するための別の方法として,選択回数によるビーム幅の分割を実装しました.これは,例えば最大選択回数が4, ビーム幅が 4,000 の時,選択回数別(1回〜4回)にそれぞれ 1,000 のビーム幅を振り分けるというものです.選択回数が少ないビーム内に存在する盤面状態は,選択操作を行うことで,それより選択回数の多い状態に遷移することが出来ますが,逆はありません.これにより,選択回数を使い切った状態で埋まってしまう,といった事態を防ぐと共に,多様性を向上させることが出来ます *8.加えて,常にビーム幅を等分割するのではなく,現在の解答の進行度合いに応じて動的に変更するようにしました.
大きなサイズ用 (AI名: dragon)
主に 10×10 よりも大きなサイズの問題に対するソルバーです.このソルバーは,以下の3種類のビームサーチを順に行います.
- 最初の一回以外選択操作を行わず,交換操作のみを遷移としたビームサーチ.(AI名: whale)
- ピースを端から1つずつ確実に埋めていく操作を遷移としたビームサーチ.(AI名: dolphin)
- 前述した小さなサイズ用のビームサーチ.(AI名: kurage)
whale は kurage とほとんど同じビームサーチですが,whale では選択操作を最初以外行わないところが違います.盤面の各ピースを全体的に正しい位置に近づけ,主に dolphin の手数を削減するのが目的です.これにより,マンハッタン距離の総和は,16×16の盤面だと 2700 程度から 800~200 程度まで下がります.
whale だけだとマンハッタン距離はいずれ下げ止まり,なかなか0にはなりません.そのため,次の AI である dolphin では,端から確実に埋めていくビームサーチを用います.これは,埋めるマスを指定し,交換操作のみでそのマスに正しいピースを運んでくる動作を一遷移としたビームサーチです.埋めることのできるマスは限られており,最初は四隅で,あるマスを埋めるとその一近傍を新たに埋めることが出来るようになります.また,実際に埋める部分のアルゴリズムは ioryz が実装しました.行や列の最後の2マスを埋めるときには逆にしないといけないなど,コーナーケースが無数にあり,かなり実装難易度の高い実装だったと思います.マスを埋めるアルゴリズムの内部では,始点と終点を指定して,ピースを運ぶ関数を用いています.これは僕が A* 探索を用いて実装しました.更にその内部では,選択中のピースを指定した点まで移動させる関数を用いています.こちらは幅優先探索を用いて実装しました.その内部でも,なるべくマンハッタン距離が上がらないような経路を選ぶなど,細かい最適化を幾つかかけています*9.評価関数としては,manhattan distance, linear conflict の他,揃ってない領域がどれだけ扁平でないかを表す値などを使いました.dolphin は,中央の 10×10 を除いた領域が完全に埋まるまで動作を続けます.
最後に,10×10 の領域について,前述した小さなサイズ用の AI を走らせておしまいです.以上をまとめると,大きなサイズの問題については
ビームサーチ(ビーム幅 4000) ↓ ビームサーチ(ビーム幅 200) → A* → 幅優先 ↓ ビームサーチ(ビーム幅 4000)
という三段構造の探索を行っている,ということになります.
参考のため,問題番号 9 草原 (16×16) をこの AI に解かせた動画を作成しました.この動画の最終的な交換回数は 4700 回程度です*10.ピースがその正しい位置から遠いと青っぽく,近づくと赤っぽくなり,正しい位置に揃うとオレンジになります.
- whale: 最初〜1:57
- dolphin: 1:57〜2:53
- kurage: 2:53〜最後
操作列の最適化
操作列の部分列を,それと等価でより短い部分列に変更する処理を行いました.例えば,操作列に「上へ移動」「下へ移動」という連続した二つの交換操作が含まれていたら,これは無駄な操作なので,共に消し去ることが出来ます.普通にビームサーチを組んでいたら発生しそうにないですが,今回のプログラムで言うと,前述の三段ビームサーチによる解答を接続した際に起こりえます.
また他にも,2×2 の領域における回転操作を短くすることが出来ます.「上右下左」で時計回りに一回転すると,選択しているピースは元の位置に戻ってきますが,選択ピースが通った3つのセルは,1つずつピースが入れ替わります.従って,同じ向きに3周すると,全てのピースの位置が最初の状態に戻ります*11.これを用いると,例えば時計回りに7回動かしている操作列は,反時計回りに5回動かすのと等価であることが分かるので,解答を短くすることができます.この最適化は地味に有効で,16×16 だと 20 手くらい削ることが出来ます.
高速化
今回の問題は,かなり時間のウェイトが重く,解答を高速に計算することが求められました.従って,以下の様なコードレベルの最適化を行いました.結果的に,16×16 でも交換回数 4,000 台後半の解答を安定して 5 秒で作成できるようになりました.
評価関数の差分計算
状態を遷移する毎に評価関数を毎回計算し直すのは無駄です.以前の計算結果を利用して,少しの計算量で評価関数を更新することが出来ます.簡単なように見えますが,実装は意外とややこしいです.
並列化と lock-free
ビームサーチはメタヒューリスティクスアルゴリズムの中でも並列化しやすい方だと思います.Intel TBB を用いて並列実装したところ,4コア8スレッドの CPU でシングルスレッドの 4 倍程度の実行速度が得られました.また,極限まで lock を掛けなければならない部分を削減し,lock がどうしても必要な場所でも spin lock を用いることで,高速な並列処理を実現しました.尚,並列処理が入った部分のデバッグは再現性が低いことも多く,かなりしんどいです.デバッガを活用しましょう.
解答復元
当然ですが,ビームサーチにおける探索では,各盤面における今までの操作の履歴を残しておかないといけません.メンバとして操作列を全ての盤面に動的配列として持たせておく実装も考えられますが,盤面のメモリ上のサイズが肥大化し,またヒープ領域の確保及び解放が頻発するため,好ましくありません.この問題に対処するため,最初,shared pointer が親を指しているリンク構造のツリーを作成しました.これは,子孫が途絶えたら先代に遡ってノードを根絶やしにする構造で,不要になったメモリをその場で開放できるため,メモリの使用効率は最も良いと思われます.しかしながら,確保と解放を動的に繰り返すため,セグメンテーションが起きやすい,という点と,shared pointer がそもそも重い(ポインタのデリファレンスが頻発する,データ競合が起きないことを保証するため,内部で atomic 操作を行っている,など)という点が存在し,暫くの間代替技術が望まれていました.本戦の一週間ほど前に,通常の動的配列をリンク構造として用いる実装に変更し,これらの欠点を克服しました.
テンプレートと branch
盤面の最大サイズは 16×16 であり,このサイズで固定長として確保してしまうと,例えば 4×4 の問題を解くときはメモリの無駄が多く発生します.メモリの無駄は容量を食うだけではなく,キャッシュ効率も落としてしまうため,忌むべき存在です.可変長として確保すると,今度はメモリの動的な確保・解放が増えてしまいます.唯一の解決策は,最小サイズの 2×2 から最大サイズの 16×16 まで,225 パターンすべての状態を静的に確保出来るよう,テンプレートを駆使することです.一応,テンプレートのパラメータ次第で 16×16 の固定長の一部を使う実装にも切り替えられるようにしました.branch.hpp にはこの二つの実装の橋渡しを行う関数が定義されており,大変なことになっています.尚,本プログラムはフルコンパイルに1時間程度かかるのですが,主な原因はコイツです.
速いマシン
やはり最後はマシンスペックです.僕が普段使用している 1kg 程度の MacBook Airに対し,感覚的に 2.5kg くらいある Ubuntu マシン(Intel Core i7-3630QM CPU @ 2.40GHz × 8,16GB RAM)は同じプログラムでも 2~2.5 倍程度の計算速度を誇っていました.開発環境と本番環境の PC が異なるのはこのためです.上記の 5 秒という計算時間は,この速いマシンにおける測定値であり,開発機だと 13 秒程度かかります.
システム
UI
UI は全て mfumi2 が Qt で書いてくれました.Qt はマルチプラットフォーム用の UI フレームワークなので,Mac で作成した UI がそのまま Ubuntu で動きました*12.確認していませんが恐らく Windows でも動くと思います.
UI の機能としては,ソルバーや後述する通信部分の設定の他,ジグソーパズルの結果が間違っていた時に手動で修正する事のできるインタフェースも付いています.
通信・分散処理
今回は 3 台の PC を同時に使えるため,分散処理を行いました.一台の PC でサーバを立ち上げ,それに他の二台の PC が接続する形です.まず,サーバ PC が運営のサーバから問題を取得し,ジグソーパズルを解きます(1秒以下で解けます).次に,サーバ PC がクライアント PC にジグソーパズルの結果を配信すると同時に,自分自身もスライドパズルを解き始めます.サーバ PC が使うスライドパズルのソルバーは1秒以下でそれなりの答えが出せる設定のものであり,サーバ PC はこれを運営サーバに送信することで,ジグソーパズルの解答の答え合わせを行います.
一方,サーバ PC からジグソーパズルの解答を受け取った二台のクライアント PC は,それぞれスライドパズルを解き始めます.二台の PC は微妙に設定の異なるソルバーを用いており,解答が出来次第,サーバ PC に送信します.サーバ PC は解答を受信した後,内部で持っている送信回数や以前の提出解答と照らし合わせ,運営サーバに送信すべきだと判断した時に解答を送信します.
コードは全て mfumi2 が boost.asio を使って書いてくれました.以上の通信・分散処理は自分が現役時代からあると良いなと思っていたもので,今回彼が実現してくれてとても嬉しく思っています.
しかし実際は,サーバのレスポンスがかなり遅く(意図的に遅くしていたらしい?),良い解答が送られるタイミングが後ろにずれ,結果的に時間コストを増大させてしまうという作戦ミスがありました.
readable, sustainable なコード
今回開発を行う上で,コードを極力「読みやすく,保守しやすい」状態を保つことに苦心しました.高専プロコンの競技部門は,長時間の開発であり,当然のことながら短時間でコードを書く TopCoder の Single Round Match や AtCoder の AtCoder Regular Contest などに比べて,高い保守性が要求されます.また,TopCoder の Marathon Match や CodeVS 等の類似した長距離系コンテストとは異なり,3人で暫くの間集団開発を行うことになります.従って,他のコンテスト以上に「読みやすい」ことが要求されます.
コードの可読性と保守性を担保するため,完全に作業領域が分離されていた mfumi2 を除いて,僕と ioryz は度々コードレビューを行いました.本番直前はさすがに時間的制約から突貫工事のパッチワークがコンタミしてしまいましたが,それでも二ヶ月半3人で共同開発を行う上で問題ないレベルの可読性・保守性を保つことが出来たと思っています.
プロジェクトの構成について言うと,今回コードの保守性が高かった理由として,CMake を使っていたというのが挙げられるかと思います.CMake はビルド設定に関する環境依存を吸収してくれるので,Mac で開発したコードを少しの修正で Ubuntu でも動作させることが出来ました*13.また,実行可能ファイル( main 関数を含むファイル)とソルバーの実装を分離し,更にソルバーの実装もジグソーパズルとスライドパズルで分けたのも功を奏したと思っています.モジュール間の関連性をなるべく減らすのは,保守性を高めるための基本ですが,意外とちゃんと実践出来たことがない人も多いのではないでしょうか.
まとめ(現役生に言いたいこと)
一部は繰り返しになってしまいますが,せっかくの機会なので,高専プロコン OB としての立場から,プロコンに取り組む現役生に向けて幾つか老害感溢れるメッセージを発信したいと思います.以下は競技部門の参加者を想定して書いていますが,多くは自由・課題にも共通して言えることだと思います.*印がついているものは,表彰台を狙うベテランチーム向けです.
役割分担を考える
今回僕達のプロジェクトがうまく回っていたのは,役割分担がうまくいったのが大きな理由の一つだと思っています.ジグソーパズルとスライドパズルで作業を分離しやすい問題でした.例年はここまで作業を大別できない出題も多いのですが,チームのリーダーは個々人の得意分野と能力を考え,メンバーに適切にタスクを振りましょう.全体のクラス構造などの設計は経験豊富な上級生が行って,後輩を指導すると良いと思います.
*事前調査をしっかり行う
先人の知恵は偉大です.関連する分野の技術調査を行いましょう.例えば,今年なら画像処理とパズル,去年なら通信・情報理論,一昨年なら機械学習と統計解析などです.また,先人は偉大ですが,得てしてその知識を理解・修得するのは難しいです.時には,高度な数学の知識が要求されることもあります.更に技術を追っていくと,すぐに日本語の文献は尽き,英語の web ページや書籍,最終的には英論文にたどり着きます.従って,技術的な英語の文章を読める必要も出てきます.海外のチームは読んでいます.これらは難しそうに見えますが,いずれ研究を行うときにも要求される能力です.プログラムを書くのは楽しいですが,学校の勉強もきちんとしましょう.
可読性,保守性の高いコードを書く*14
チームで統一するコーディング規約を作りましたか?命名規則は守られていますか?コードの要所に他人が見ても分かるコメントは書かれていますか? assert を入れていますか?変数の有効範囲は最小限に留めていますか?やたら長い関数はありませんか?ソースが1ファイルに 1000 行とか書かれていませんか?このやたら深いネストは何ですか?
バージョン管理を行う
git と github の使い方は最低限覚えましょう.昔は USB メモリでコードをやりとりした結果,どれが最新版なのか分からなくなったり,SVN で大量の編集競合に悩まされたりしたものですが,今は素晴らしい時代です.今年は github や bitbucket などでコードを管理・公開しているチームが多々あり,良い流れだと思っています.
*高速化は順序付けて行う
早まった高速化,過度な高速化は禁物です.まずは可読性を優先してコードを書きましょう.プログラムが遅いなと思い始めたら,コンパイラの最適化オプションを確かめましょう.それでも遅かったら,プロファイリングを行って,どの部分に時間がかかっているのかを計測しましょう.全体の2割のコードが8割の実行時間を占めていると言われます.時間がかかっていない所を高速化しても,暖簾に腕押しです.時間がかかっている所を特定できたら,ごく簡単に行える無駄な処理の消去などを行います.重い関数を複数回呼んでいたら,最初の計算結果を使い回せないか考えましょう.重いデータをコピー渡ししている関数があったら,参照渡しに変えます.リソースを保持するクラスは,適切に move を利用しましょう.この段階で大幅な書き換えを行っていはいけません.次に,それでもまだ遅かったら,本当に今その場所を最適化しなければならないのかを考えます.将来的にその部分が丸ごと別のプログラムに差し替えられる可能性があるのなら,今最適化したとしても時間の無駄であるどころか,差し替えをしたくなくなってしまう負の要因になります.どうしても今高速化が必要な場合は,まず計算量を下げられるアルゴリズムがないかを考えましょう.定数倍高速化は頑張っても 200 倍速程度ですが,アルゴリズムを変えてオーダを下げれば,時には 20,000 倍動作が速くなることもあり得ます*15.それでもダメなときは,ようやくコードレベルの最適化を行います.ワーキングメモリを削減したりループの順序を変えることで,キャッシュ効率の向上を狙うのは結構効果があり,変更も比較的容易です.次に,並列処理を考えましょう.並列化はなるべく外のループで行ったほうが効率が上がります.lock は重いので,極力かけないようにします.atomic 操作で済むところに lock を使ってはいけません.事前に計算できる部分はテーブルを作るのも手です.ベクトル演算できる処理は SSE や AVX などの採用も考えます.
高速化を進めるにつれ,次第に可読性が失われてしまうのは仕方のないことですが,それでも適切にコメントを残すなど,可能な限り可読性を保つ努力をしましょう.また,手を入れる前にテストコードを書き,随時単体テストを行いながら高速化を進めていくのが望ましいです.
前日はしっかり寝る
ウチもあまり寝てなかったので人のことは言えませんが,やはり夜はちゃんと寝たほうが良いです.せっかく全国のプログラミング好きな高専生が集まるのに,日中寝ぼけ眼でボーっと過ごしてしまうのは,大きな機会損失だと思います.
コーディングを楽しむ
一番大事だと思います.プログラムは苦しみながら書くものではないです.作品(アルゴリズム)をみんなでつくり上げる過程を楽しみましょう٩( ’ω’ )و
*1:本番前日に Yosemite へのアップデートが入りそうになってとても焦った.
*2:icc (Intel C++ Compiler) が C++14(1y) をサポートしていないので対応言語を C++11 に落とし,大量の constexpr を削除しました.
*3:icc の体験版を入れたけど gcc と実行速度がほとんど変わらなかったので,結局使わなかった.
*4:問題番号4の TATAMI だけはなぜか画像サイズが不正なので解けてないです.
*5:ビームサーチについては,http://spheresofa.net/blog/?p=1044 を見ると視覚的に分かりやすいと思いますが,簡単に説明します.まず,ある状態から次の状態への「遷移」を考えます.例えば,交換操作なら上下左右の4種類,選択操作なら盤面のサイズと同じ種類数の遷移が考えられます.必ずしも1回の交換・選択操作を1回の遷移に対応させる必要はなく,複数回の交換操作をまとめて1遷移として扱うことも出来ることに気をつけてください.最初の状態から可能なすべての遷移を試し,最も低いコストで完成状態にたどり着くことが出来れば,理論的には,スライドパズルの最適解を求めることが出来ます.しかしながら,ある状態の遷移数が n の時,二手先の状態数は n2,三手先は n3,…のように,遷移の組み合わせによって得られる盤面の状態数は指数関数的に爆発していくので,すぐにメモリも計算時間も足りなくなります.この爆発的に増加する状態のネットワークを潜り抜け,うまく目的の完成状態を探索する手法を,総称してメタヒューリスティクスと呼びます.ビームサーチはメタヒューリスティクスの一種で,盤面の良し悪しを定量的に評価する関数(評価関数と呼びます)を定義し,決められたある数(ビーム幅と呼びます)だけ,評価関数の値が良い方から盤面の状態を残していく手法です.この手法は,厳密に最も低いコストで完成状態に辿り着ける保証も,または有限回の遷移で完成状態に辿り着ける保証もありませんが,評価関数が盤面をうまく評価してくれれば,それなりに良い解を出すことが出来ます.ビームサーチは今回の問題のように,遷移に順序依存性がある(例えば,上→右 と動かすのと 右→上 と動かすのでは異なる結果になる)問題の場合に威力を発揮する手法として知られています.
*6:選択操作の行えないスライドパズルである古典的な N-Puzzle には偶奇性が存在し,これはいかなる遷移を行っても入れ替わらないことが知られています.http://www.geocities.jp/m_hiroi/puzzle/parity.html,現代数学2014年6月号,など.
*7:ハッシュ値の更新が差分計算で行える.http://en.wikipedia.org/wiki/Zobrist_hashing 参照.
*8:この手法による多様性の確保は,chokudaiサーチからインスピレーションを得たものです.chokudai 先生に感謝します.
*9:府立のコードに近いですが,このあたりの最適化は府立の方が頑張っています.
*10:練習競技場に出している 4100 回程度の解答は,小さなサイズ用のアルゴリズムを無理やり草原に適用したものです.25 秒程度時間がかかるので,時間コストまで考慮すると大きなサイズ用のアルゴリズムが適しています.
*12:でもなぜか仮名が文字化けした.
*13:Ubuntu では g++ を使ったので,現れるエラーの種類が clang と若干異なり,その点で修正を余儀なくされた部分はあります.
*14:但し,保守性を意識するあまり,コーディングが全く進まないようになるのなら話は別です.最初はプロトタイプとして書きなぐって,性能を確認して,後からきれいな形に整形するという流れも有効です.git などを使ってきちんとバージョン管理を行っているのなら,いつでも前の状態に戻れますので,コードが一時的に汚れることを恐れる必要はありません.