最終的に力技（マンパワー、パソコンパワー）で5000問分の回答を得ましたが、
他の#gdd11jpの方々と比べると、超非効率だったなと痛感しています。
計算時間もかなり使っており、かなり泥臭いですorz
ざっと他の方々の手法を読ませていただいて、
私独自だったかもしれない点を書かせていただきます。
（１） ３つの評価関数の上位いくつか ＋ 乱数でピックアップ
ステップ検索（ある程度計算し、閾値になったら評価関数の優等生を選抜、次のステップへ）
を使ったのですが、その評価関数を上記のように用意しました。
単一の評価関数だとローカルミニマムに落ちてそれ以上発展しない様子が良く見られたので、
評価関数を複数追加すれば、例えば、
評価関数Aの優等生 →閾値分進行→ Bの優等生が発生→進行→ Cの優等生が発生
というように、評価関数間上位を渡り歩くようなパスが生じるのではないかと考えたからです。
乱数でピックアップも同様の意図を持っています。
評価関数は、
・壁があったらその迂回分距離を足すマンハッタン距離
・マンハッタン距離に、上、もしくは、左にいけばいくほど重みを掛ける
・2方向しか移動出来ないパスにおける重み（後述）
とかを、人力（マンパワー）で適当に入れ替えたり、足し合わせたりしながら回してみました。
（２） 2方向しか移動出来ないパスにおける評価
これは、2方向しか移動出来ない場所が連続でつながるパスを判別し、
そのパス内の状態を評価関数で表現しました。
例えば、１－２－３－４－５ という2方向しか移動出来ないパス構造があった場合、
そのパス上で配置されたパネルの評価関数を、
以下の下に行けばいくほど大きくなるよう表現します。（実際はもうちょっと細かく数値化してます）
１－２－３－４－５ がパス上にある（完成） 評価値：０
＜１－２－３－４ or ２－３－４－５ （完成一歩手前） 評価値：１０
＜１－２－３ or ３－４－５ （完成2歩手前） 評価値：１００ ※自分で間違い発見・・・
＜１－２ or ４－５ 評価値：１０００
＜１ or ５ がパス上にある 評価値：１００００
＜１～５のどれもパス上にない 評価値：１０００００
マンハッタン距離にこの評価関数を加算すると、
最初（２）の評価関数を落とすようにまずは動き、（１００００→１０とか）
つまり、パス構造になっている部分を先に解き、
その後は普通にマンハッタン距離を落とすように評価値が動きます（数１０→０）。
これを使って、左上がL字形の一本道になっているような盤面を倒しました。
ただしこれは問題があり、
2箇所以上のパスが互いに影響及ぼしあっている場合には使えませんでした。
・Tの字型にパス3本が一箇所で接合している場合
・パスを挟んで最終的にループ構造をとっている場合（３つとか４つの島になっている盤面）
というより、そういう問題が10問？ほど残りましたorz
最後は残念ながら「マンパワー」で解きました。
勉強を兼ねて書いたことのなかったjavaを使ったり、
ぐんと解け出した時のわくわく感も感じられ、
寝不足になりましたがとても楽しかったです（・ω・）ノ
※
よく考えたら、例えば、（完成2歩手前） 「２－３－４」でも良いではないか・・・
あーなーだーらーけーだーΣ（￣Д￣;）
※2011/9/21追記
こういうひらめき（ソルバー３号）、かっこいいですねぇ（・ω・）
http://mnu-j.tumblr.com/post/10279560089/cattaka-devquiz
0 件のコメント:
コメントを投稿