Help us understand the problem. What is going on with this article?

その他

More than 5 years have passed since last update.

例によって例のごとくpoh5+を続けているが、最短ステップクリアが出来ていない。
CASE3と4がタイムアウトしてしまう。いろんな手法を試したが全然間に合わない。
なおC#の限界時間は4秒である。
ここで原因を考察する。

反復深化深さ優先探索

再起によりメモリ使用を抑えられるのが利点。
評価関数の調整で近いところまで行けるがCASE3が69、CASE5が60となり最短ステップにならない。
評価値による計算打ち切りは時間制限をクリアするために必須である。

A*(未実装)

メモリ使用量を推測するとオーバーするので却下。速度面も期待できない。

ハッシュと重複排除

64bitの完全ハッシュ化で排除しようとしたがメモリ不足で断念。メモリが足りる間はかなり高速化できる。

逆方向探索

終了局面から20手程度全パターンを手順とともに記録してその盤面が現れた時点で終了するようにする。
しかし、反復深化で評価値による打ち切りを入れると最短にならない可能性があるので失敗した。

幅優先探索(未実装)

メモリ不足。どう考えても足りない。

(反復深化)山登り法

CASE3は評価関数が悪くなる方に移動しないと最短になる手順を発見できないので逆効果ですらある。
そうでないCASE5なら最短を見つけられる。

IL_k
ソフトを作る人
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした