ハノイの塔とは３本の柱Ａ，Ｂ，Ｃがあり，柱Ａにある何枚かの円盤を１枚ずつ柱Ｂを中継点にして柱Ｃに移動させるものですが，柱が３本のとき→４本のとき→ｎ本のときに一般化するのはもっと難しい問題になります．

　　［参］ハノイの塔，「離散数学のすすめ」第１０章，現代数学社

にｋ本ハノイの塔問題の詳細がありますが，驚くべきことに，ｋ≧４のときのｋ本ハノイの塔問題はいまだ解明されていません．

　フレイム・スチュワートのアルゴリズムの移動回数Ｍ（ｎ，ｋ）は実験的にｎ＝３０程度まで調べられており，その範囲では実際に最小となることが確認されています．そのため，ＦＳアルゴリズムが最小解を与えると信じられていますが，厳密な証明はされていないのです．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

　巡回セールスマンの問題などは、まともなアルゴリズム（表現が不適切）では計算量が指数関数的に増加する。しかし、このような問題は，大抵ヒューリスティック（発見的方法ともよばれる）により計算量が減らせる。

　ハノイの塔は、このようなヒューリスティックな方法が全くないという絶望的なサンプルである。

　私見としては、棒が3本以上の時はヒューリスティックな方法はあるととおもうのだが、貴兄のHPを見ると私もまた不明な人間のうちにはいることになる。

　しかし、本当にヒューリスティックな方法でもっと計算量をへらせることは

できないものだろうか？　　（阪本ひろむ）

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝