チャレラン」というパズルを解いたという記事を紹介しました。Qiitaただ、この記事では、解き方の詳細までは記述していませんでした。今後の備忘録を兼ねて、それをまとめてみようと思います。※下記に連ねる「枝刈り」などの高速化のコツは他のパズルにも応用が効くと思います※代表的な高速化手段の一つであるビットボードについては、次の記事をご覧ください(ペーパーチャレランでは結局使用しませんでした。Qiita2017/12/27追記:種々の枝刈りを取り込んだ、最新のプログラムのソースコードを配布します。https://github.com/YSRKEN/challerunF2017/12/26追記:「枝刈りその4:見込みのない経路を途中で打ち切る」を実装したので取り急ぎ報告まで。計算迷路チャレランとは?参考→http://www.challeran.jp/crland/pe-cha/paper-challeran/0705/setumei.htmlスタート地点から格子の辺を伝い、ゴール地点を目指します格子の交点と交点を結ぶ辺の上に、「+3」や「×2」などの「演算」が書かれています(実際の問題では、演算子は+と-と×(*)の3種類、それにくっついた数字は1桁)スタート始点での持ち点は1点。辺を通過すると、そこに書いてある「演算」を持ち点に施します同じ辺を二度通ることはできません。同じ交点を二度通っても構いませんゴール地点に着いた際、より持ち点が大きい方が勝ちです例として、次のような問題があったとします。仮にス→A→D→G→H→I→ゴと進むと、(1+4)×3-4+1=12点となります。→A→B→C→F→E→D→G→H→I→ゴと進むと、((1+1+2+1)×2+3)×3-4+1=36点となります。点数を増やしたいので、この場合は後者を採用すべきです(ちなみにこの問題の最適解は36点)。同じ交点を二度通っても構いませんので、ス→A→B→E→D→G→H→E→F→I→ゴと進んでも、ス→A→B→E→H→D→G→D→E→F→I→ゴと進んでも構いません。前述したように、演算は通った辺の順に適用されますので、交点の通り方が変われば点数も変化するのです。問題の解き方について説明の前に、各種枝刈りがどの程度効くのかを、適当な問題を例に表として纏めました。枝刈り1の時点で計算時間が半減していますが、枝刈り2・枝刈り3でそれぞれ1割ほど改善していますし、枝刈り4に至っては最大で4倍近くも高速化されていることが分かります。55.808深さ優先探索(DFS)「選択した経路を奥に奥に進む」といった、非常にシンプルな手法です。この問題特有のポイントもありますので、使用したアルゴリズムを擬似コードで示します。ことに注意)既に通ったことのある辺は通過できないので、現実的には「辺に番号を振って通過の有無を管理する」といったことが必要になります。「現在の交点→次の交点の辺が『現在の経路』で通った辺に含まれるか」をチェックするのは高コストですので......枝刈りその1:ゴールが角にあるか否か深さ優先探索で探索する系のプログラムにつきものなのが、計算量爆発にどう対処するかです。かの有名な動画『フカシギの数え方』より、同じ盤面規模でも遥かに探索量が多くなるこの問題では、少しでも計算量を削っておきたいところです。そこでまず思いつくのが、「ゴールの交点が角にあるか否か」で再帰する関数を分ける方法です。上記画像のIマスが「ゴールの交点」だとします。すると、HマスからIマスに進んだ際、そこからFマスに進むことはもはや許されません。「ゴールの交点」がHマスのような壁際や、Eマスのような宙ぶらりんの位置にあった場合、そのマスを通過したところで、再びゴールする可能性が存在します。ゆえに、「ゴールの交点が角にある」と始めから分かっている場合、次の擬似コードでも問題なく解を探すことができます。}}枝刈りその2:入ったら出てこれる交点かそれぞれの交点に注目してみましょう。「交点に入った数=交点から出た数」となります。交点を通過する度に、その交点に隣接する「通過可能な辺」の数は2つづつ減っていきます。ゆえに、「通過可能な辺」が残り1つしかない交点は、それが「スタートの交点」「ゴールの交点」以外である場合、入ると出てこれない交点となります。要するに「探索時に進まなくてもいい交点」となるのです。このことを擬似コードで表現すると次のようになります。//★変更ポイント★}枝刈りその3:交点を2色に塗り分け(カラーリング)上記までの擬似コードでは、辺を1つ通過する度に「ゴールの交点における判定」や「次の交点に移動する処理」を行ってきました。一度に2つの辺を移動できれば、再帰関数を呼ぶ回数を減らすことができます。(辺を1つづつ通過すると「行って戻る」といった意味のないムーヴも一応参照してしまうが、それが無くせるということ)また、このアイディアを実装する前に、交点を交互に色分け(カラーリング)してみます。すると、「一度に2つの辺を移動」した際は、必ず同じ色の交点にしか行かない(白→白→白→......など)のです。次のようなアルゴリズムになります。当初、上記のような色分けを行った後に、次のようなアルゴリズムを実装していました。これで「ゴールしたかの判定」の処理を呼び出す量を半分ほど削減できていたのですが、「2辺移動」のインパクトには劣りますね......。(再帰関数A内では再帰関数Bを呼び、再帰関数B内では再帰関数Aを呼びます)「スタートの交点(Sマス)」と「ゴールの交点(Gマス)」の「色」を、剰余演算などで判定するSマスとGマスの「色」が異なる場合は、「ゴールしたかの判定を行わない」再帰関数Aを使用するSマスとGマスの「色」が同じ場合は、「ゴールしたかの判定を行なう」再帰関数Bを使用する※補足2:カラーリングは3色以上行うケースもある上記のように「カラーリングによって得られる特徴を利用する」戦略は、2色塗り分けだけとは限りません。数値シミュレーションの分野では、要素を色分けすることによって、「CPUを複数動かして作業を分担させる」並列演算に利用することがよくあります。/proc/cpuinfoその際には、2色に塗り分ける他に、4色や8色に塗り分ける方式もあるそうです。参考資料→新ベンチマークプログラム:HPCGの概要と「京」における性能(画像は参考資料より引用)枝刈りその4:見込みのない経路を途中で打ち切る「到底最高得点になりえないようなルートを進んでいたケース」を枝刈りによって排除することができれば、探索時間を大幅に節約できるでしょう。そこで、「探索途中の経路・盤面から最高得点の上界を予測する」ことにより、それが既に得られている最高得点より低かった際に打ち切る......といったアイディアが考えられます。方式1:探索開始時の状況を元に算出する(精度は低いが計算量は少ない)方式2:再帰関数の冒頭で毎回算出する(精度は高いが計算量は多い)と一長一短になります。3=5364$となります(最初の1は初期得点)。方式1だと「現在の得点が1未満である」ケースしか枝刈りされませんが、方式2だと例えば「現在の最高得点が3000で『*』辺が余っておらず、現在の得点が2800点しかない」といったケースも枝刈りされます。方式2にしても、毎回盤面全体の「どの辺が使用可能か」を洗い出すのはコストが大きすぎると予想されますので、実装に注意が必要でしょう。注意して実装しました。ポイントを擬似コードで示します。}}ちなみに枝刈りを行う際は、「*」の記号が問題盤面に少ないほうがいいです。「*」の記号が多い=上界が大きくなる=打ち切りが行われない確率が大きいからです。問題を小問題に分割→並列演算させる際は、上記の「最高の得点」部分をグローバル変数にするなどして共有し、std::mutexなどで調停しながら同期させた方がいいです。することにより、「他スレッドが解いた小問題によって打ち切りの精度が上がる」からです。軽く実験したところ、数割ほど計算時間を削減する効果がありました。その他高速化のためのアイディア主なものを箇条書きで示します。基本なことばかりですが、なまじ再帰回数が多くなるのでその効果が大きいです。データをなるべくコピーしない(参照・メンバ変数など)関数の引数を利用する演算時の判定文を無くす・積和演算に置き換えるプロファイリングで処理が重い箇所を見つける高速化のためにコードを変更した際は、速くなったかどうかを統計的に確かめる(t検定など)並列化を行う際は慎重に。Progsch様のスレッドプールライブラリを利用しつつ、並列化に使用するスレッド数×100程度の小問題を幅優先探索で作成して分担させるといった単純な手法によって並列化に成功しました。upLoginユーザーは見つかりませんでした。