最長片道切符のOR

鉄道マニアで乗り鉄の方ならあこがれるJR最長片道切符。

このことに関して、とある学術誌にて、整数計画法を利用し稚内から肥前山口のルートを導いたという記述がありました。

この内容は面白い論文でしたが、ふとこの最長片道切符問題を他の分野で応用した使い方があるのかと思い、書き込みました。

最短ルートなら、いろいろな応用は利くにしても、最長ルートを求めることがどういう意味を持つのか疑問です。

趣味の世界といってはそれまでなのですが、なにかに使える、使われているということがあれば、教えてください。

No.1 回答者： Hyperion64 回答日時： 2009/05/19 18:51

最長経路というと応用できないイメージになってしまいますが、

すべての地点を出来るだけムダなく周遊する経路を見つけることなら
応用がきくのではないでしょうか。社長が全国の支店をもれなく視察するようなケースです（最短経路で廻ると言い換えもできてしまいますけど）
他方、グラフ理論でいうハミルトン経路はグラフの頂点をすべて廻る最長パスが存在するときに、そのパスをハミルトン経路というのだとか。

この回答へのお礼

ご意見どうもありがとうございます。

すべての地点を無駄なく周遊する経路の事に関しまして、
同雑誌に郵便配達人問題を利用した「乗りつぶしのOR」という
筑波大学のS教授の論文が記載されています。
社長の全国の支店の視察には、こちらのほうが近いものかと思いました。

参考となる資料を提示していないのに、
このような書き込みをするのも変なことではありますが。
失礼なリスポンスと感じたらすみません。

お礼日時：2009/05/19 22:23

No.2 回答者： Tacosan 回答日時： 2009/05/19 19:06

むか～しの bit ですか?

実用上の意味はないような気がするなぁ.
そもそもの発端が「真の最長経路を探そう」で, 既に現実から離れてますから. カンパが集まっちゃったので「実際に乗らざるを得なくなった」というオチもついてますね.
なお, 「ハミルトン経路」そのものには「最長」という条件は付きません＞#1. 定義上は「すべての点を通る」だけです.

この回答へのお礼

ご意見どうもありがとうございます。

参考としてみていたものは「bit」ではなく、
「オペレーションズリサーチ　経営の科学」です。
ただこの四国行きの落ちをしっているということは、
著者はまったく同じ人物なのではないのでしょうか？

やはり最長片道切符問題は、
趣味以外で生かされるものではないというものですかね？

お礼日時：2009/05/19 22:30

No.3 回答者： rinkun 回答日時： 2009/05/20 09:29

最長片道切符を整数計画法で求めるというのは

http://www.swa.gr.jp/lop/
の話ですか?

整数計画の応用例としてはおもしろいし、定式化の工夫点は応用が利くんじゃないかと思うけど、最長経路問題が直接応用できる分野は知りませんね。
スケジュール問題なんかで使えるかも知れないですけど。

参考URL：http://www.swa.gr.jp/lop/

この回答へのお礼

どうもありがとうございます。
まさにこのホームページの管理人、葛西隆也氏の論文に間違いありません。
整数計画は使えても、最長経路問題が役立つかは不明なんですね。

お礼日時：2009/05/20 13:40

No.4 ベストアンサー 回答者： PRFRD 回答日時： 2009/05/20 14:43

最長路問題（longest path problem）ならば

実用的にも理論的にも応用を多く持ちますが，
「最長片道切符問題」にすると，少し具体的すぎます．

(a) まず最長片道切符問題についてです．
一般に，最適化理論の研究には
　(1) 一般的なフレームワークの研究
　(2) 具体的な問題の研究
の２つがあり，最長路問題の研究は (1)，
最長片道切符問題の研究は (2) に属します．

(2) の研究では (1) の結果をベースにしつつ，
問題に応じたアイデアを作り出すことが重要視されますが，
そのようなアイデアは問題に強く依存するため，
別の問題に対しては，あまり有効には働かないのが普通です．
例えば，最長路問題に帰着される別の問題として
最長しりとり問題というものが知られていますが，
こちらに最長片道切符問題のアイデアを使うことはできません．

(b) 次に最長路問題についてです．
この問題は古くから研究されている問題で，
上記した最長片道切符，最長しりとり以外にも
・回路の遅延解析（回路の応答時間を見積もる）
・スケジューリング（作業工程の時間を見積もる）
・ゲノム解析（最適な対応を発見する）
などが代表的です．

さらに「枝の距離が負」であることを許すと
最短路と最長路の区別がなくなり（最長路＝符号反転して最短路），
最短路問題に見えても実は最長路問題ということもあります．

この回答へのお礼

どうもありがとうございます。

最長路問題と考えた場合、数々の応用が利くのですね。
複数の価値のある意見を参考にさせていただきます。

そもそもごく単純な思い付きからの投稿だったのですが、
私もそれから何かに使えないかと考えていました。
そこで考えたものですが、複数の機械が存在する工場で、
いかに交差点をなくし、ラインを組み立てるかという問題。
これなら最長路問題を使えるのではないかと思いました。

といっても、この分野をしっかり勉強しているわけではないので、
深く掘り下げた突っ込みはちょっとということですが（笑）

重ねて、貴重なご意見、ありがとうございました。

お礼日時：2009/05/26 22:37