■巡回セールスマン問題とハノイの塔(その6)
4次元以上の高次元についてのイメージはあまり働かないのがふつうである.結局,ある高次元図形を網羅的に描きたいならば,多面体の頂点の座標をすべて求めそれらを正しく結ぶしかない.
===================================
【1】多面体のすべての頂点を求めること
多面体は連立1次不等式
Σaijxj≦bi
を満たす点の集合であるから,シンプレックス法を用いてすべての頂点を探索する必要がある.
[参]フバータル「線形計画法」啓学出版
にしたがって,多面体のすべての頂点を求めることを考えると,
[1]理論的には計算量が多すぎる.
[2]ほぼ同内容のことは「線形不等式」(岩波基礎数学講座)にも記載があるようだ.(ただし,専門用語が全然違うが・・・)
[3]VertexEnum.mというパッケージでは,フバータルの本と同等またはそれより合理的な方法をとっている様である.
[4]VectEnum.mにより高速化が実現された.フバータルの方法だとn=11のとき4時間ぐらい.VectEnum.mだと数分でとけた.n=8ぐらいまでは両者の実行時間はたいして変わらない.
[5]フタバールの本は「近傍」云々の手順が煩雑な気がする.あの本がでてからかなり時間がたっているので,良い方法が見つかったのかも.(フーリエ・モツキン法の可能性あり.)
===================================