動的計画法による一般化ハノイの塔の最短手順導出と強化学習による求解

最終更新日:


強化学習はゲームやパズルを解く機械学習の手法であり、過去記事1にて、ハノイの塔を強化学習で解く方法を検証しました。
本記事では、ポールの数を3本から4本、5本、…と増やした一般化ハノイの塔について考察します。内容は、以下の2つです。
・動的計画法による最短手順の導出
・強化学習による求解
※ソースコードをGitHubに公開しています。 → https://github.com/akih1992/qiita/tree/master/rl/generalized_hanoi
一般化ハノイの塔について
ここでは、ポール数を増やしたハノイの塔を一般化ハノイの塔と呼ぶことにします。ポールが増えた場合、3本のときよりも短手順で求解できるのは明らかですが、最短手順はどうなるのでしょうか。本記事ではこの最短手順を考えます。
※導出方法を考えるにあたり、一般化ハノイの塔についてまとめているこのWebページ2を参考にしました。
動的計画法による最短手順の導出
動的計画法とは、小規模な部分問題の解をもとに大規模な問題の解を求めるアルゴリズムの一種です。漸化式を用いて初項から順番に数列の項を求めるようなイメージであり、最適化問題などに利用されています。(動的計画法について、この記事3に非常に詳しく書かれてあります。)
以後、ポールが$n$本、円盤が$m$枚のハノイの塔の最短手順を$a_{n, m}$を表記し、これを求める方法を考察します。
ポールが3本のハノイの塔
分かりやすいように、まずポールが3本のオリジナル版を考えます。この場合、$m$段のハノイの塔は以下の手順で解くことができます。
1.$m-1$段の塔を他の1本のポールに移動させる($a_{3, m-1}$ステップ)
2.$m$段目を残りの1本のポールに移動させる(1ステップ)
3.$m$段目の円盤の上に$m-1$段の塔を移動させる($a_{3, m-1}$ステップ)
よって、$a_{3, m} = 2a_{3, m-1} + 1$が成り立ちます。この漸化式と$a_{3,1}=1$より、$a_{3, m} = 2^m+1$が導出されます。
ポールが4本のハノイの塔
ポールが3本のときは単純な漸化式で記述できましたが、4本以上になると少しに複雑になります。4本目のポールを使う必要がないケースと、4本目のポールも使

サイト名: Qiita
2019年6月8日

無料メールマガジン登録

週1回、注目のAIニュースやイベント情報を
編集部がピックアップしてお届けしています。

こちらの規約にご同意のうえチェックしてください。

規約に同意する