JR最長経路問題・厳密解

JR最長経路問題・厳密解 RSS1.0


5. JR最長経路問題・残る課題とその解決

・藩を整理し合併させることにより、おそらく1時間程度で計算出来るようになる気がします。 次回やってみようと思います。
・計算結果は、行き止まり経路を除く、通過できるすべての駅を通過しています。 JR最長経路の旅 福知山駅は通過していませんが、これは通過できない駅です。 したがって、JR定理1の適用が可能です。
・上では計算に2ヶ月必要だったと書きましたが、JR定理1「若井が必ず着駅だと分かったこと」を執筆の途中で発見したことにより、四国を含めた再計算では、それまで2ヶ月要していたものが、1ヶ月弱になりました。 更に、最新の計算では8日間に短縮されました。
・現状では多大な計算時間が必要です。 計算時間短縮のためには、整数計画法の採用が有効と思われますが、必ず解けると言うわけではないようです。 今回、ループ解は最長経路解となり得ないという証明ができましたので、この採用にある程度の見通しが出てきました。
・また、今回採用した全探索についても、 現状のプログラムでは、ループ解も求められるし、発駅、着駅はどこでも良いと言ったアルゴリズムを採用しています。 が、今回発見したJR定理1を前提としたアルゴリズム、たとえば発駅、着駅が固定できる場合の、連結グラフにおける迷路の解法を採用すれば、飛躍的に計算時間が短縮できると思います。 多分1日程度になるのもわりとすぐではないでしょうか。
 今回の追記:連結グラフにおける迷路の解法で今回解いてみましたが、予想と異なり逆に遅くなる結果となりました。 このあたり常識とは異なりますが、なぜそういう結果になるのかは、書き残しておくと後世のためになると思いますので、後で加筆します。



改訂履歴



謝辞

 執筆にあたり、次の方々に貴重なご助言をいただきました。 感謝いたします。 なお、敬称は省略させて頂きました。 また、肩書きは2006年当時のものです。


right22.jpg(1373 byte)前章を読む 

続きを読むright22.jpg(1373 byte)