グラフの最長経路問題

質問

グラフにおいて，最長経路を求める問題があります．

　最*短*経路問題なら，「一番早くたどり着ける道順を探す」ということで理解できるのですが，最長の経路を求めて何かメリットがあるのでしょうか? 応用が分かりません．

　そこに何か利点があるのでしょうか? 理論的な興味だけなのでしょうか?

回答No.2

bender · ベストアンサー

いくつもの作業工程がある仕事の、もっとも短い工期を求めるときに利用できるようです（参考URL）。

参考URL：

http://www.asahi-net.or.jp/~zy9h-fjkw/TOC_index5.htm,http://www.agri-ed.org/shiken/sekou/moji/text/t52.html

回答No.3

graphaffine

単なる疑問点の表明だけで、背景や知りたい理由が何も書いていないので、あっさりとしか答えることができませんが。といっても私は素人なので、鵜呑みにしないように。

計算量理論の有名な未解決問題に「PvsNP問題」があります。クレイ研究所から１億円の賞金がかかっていることでも有名ですね。

最短経路問題はNP問題ですが、最長経路問題は
問題としてはNP問題よりも難しい問題に分類されます。

多分現状は
＞そこに何か利点があるのでしょうか? 理論的な興味だけなのでしょうか?
と尋ねられたら、「そのとおりです。」という回答になると思います。

そもそも、数学とは数学的な構造を研究するものですが、あくまでその構造は理論上のものですから、その構造が実生活上にどう役立つかを示すのは数学者でなく、工学研究者の役割のような気もしますね。

回答No.1

BLUEPIXY

工程管理などで、最大限かかってもどれくらいとかの見積もりができるとかでしょうか