巡回セールスマン問題（ＴＳＰ）とはｎ頂点の完全グラフＫnのすべての頂点を回って戻ってくる最短ハミルトン経路を問う問題である．

　　［参］クック「驚きの数学巡回セールスマン問題」青土社

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

【１】巡回セールスマン多面体

　置換行列が完全２部グラフＫn,nと対応するのに対して，巡回セールスマン多面体は完全グラフＫnに対応している．

　この多面体は（ｎ−１）！／２個の頂点をもつnＣ2−ｎ＝ｎ（ｎ−３）／２次元の多面体である．

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

【２】ハノイの塔

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

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

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

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

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

【３】比較

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

　ハノイの塔は，このようなヒューリスティックな方法が全くないという絶望的なサンプルである．しかしながら，棒が４本以上の時はヒューリスティックな方法はあるとと思われる．本当にヒューリスティックな方法でもっと計算量を減らすことはできないものだろうか？

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