No.4ベストアンサー
- 回答日時:
最長路問題(longest path problem)ならば
実用的にも理論的にも応用を多く持ちますが,
「最長片道切符問題」にすると,少し具体的すぎます.
(a) まず最長片道切符問題についてです.
一般に,最適化理論の研究には
(1) 一般的なフレームワークの研究
(2) 具体的な問題の研究
の2つがあり,最長路問題の研究は (1),
最長片道切符問題の研究は (2) に属します.
(2) の研究では (1) の結果をベースにしつつ,
問題に応じたアイデアを作り出すことが重要視されますが,
そのようなアイデアは問題に強く依存するため,
別の問題に対しては,あまり有効には働かないのが普通です.
例えば,最長路問題に帰着される別の問題として
最長しりとり問題というものが知られていますが,
こちらに最長片道切符問題のアイデアを使うことはできません.
(b) 次に最長路問題についてです.
この問題は古くから研究されている問題で,
上記した最長片道切符,最長しりとり以外にも
・回路の遅延解析(回路の応答時間を見積もる)
・スケジューリング(作業工程の時間を見積もる)
・ゲノム解析(最適な対応を発見する)
などが代表的です.
さらに「枝の距離が負」であることを許すと
最短路と最長路の区別がなくなり(最長路=符号反転して最短路),
最短路問題に見えても実は最長路問題ということもあります.
どうもありがとうございます。
最長路問題と考えた場合、数々の応用が利くのですね。
複数の価値のある意見を参考にさせていただきます。
そもそもごく単純な思い付きからの投稿だったのですが、
私もそれから何かに使えないかと考えていました。
そこで考えたものですが、複数の機械が存在する工場で、
いかに交差点をなくし、ラインを組み立てるかという問題。
これなら最長路問題を使えるのではないかと思いました。
といっても、この分野をしっかり勉強しているわけではないので、
深く掘り下げた突っ込みはちょっとということですが(笑)
重ねて、貴重なご意見、ありがとうございました。
No.3
- 回答日時:
最長片道切符を整数計画法で求めるというのは
http://www.swa.gr.jp/lop/
の話ですか?
整数計画の応用例としてはおもしろいし、定式化の工夫点は応用が利くんじゃないかと思うけど、最長経路問題が直接応用できる分野は知りませんね。
スケジュール問題なんかで使えるかも知れないですけど。
参考URL:http://www.swa.gr.jp/lop/
どうもありがとうございます。
まさにこのホームページの管理人、葛西隆也氏の論文に間違いありません。
整数計画は使えても、最長経路問題が役立つかは不明なんですね。
No.2
- 回答日時:
むか~しの bit ですか?
実用上の意味はないような気がするなぁ.
そもそもの発端が「真の最長経路を探そう」で, 既に現実から離れてますから. カンパが集まっちゃったので「実際に乗らざるを得なくなった」というオチもついてますね.
なお, 「ハミルトン経路」そのものには「最長」という条件は付きません>#1. 定義上は「すべての点を通る」だけです.
ご意見どうもありがとうございます。
参考としてみていたものは「bit」ではなく、
「オペレーションズリサーチ 経営の科学」です。
ただこの四国行きの落ちをしっているということは、
著者はまったく同じ人物なのではないのでしょうか?
やはり最長片道切符問題は、
趣味以外で生かされるものではないというものですかね?
No.1
- 回答日時:
最長経路というと応用できないイメージになってしまいますが、
すべての地点を出来るだけムダなく周遊する経路を見つけることなら
応用がきくのではないでしょうか。社長が全国の支店をもれなく視察するようなケースです(最短経路で廻ると言い換えもできてしまいますけど)
他方、グラフ理論でいうハミルトン経路はグラフの頂点をすべて廻る最長パスが存在するときに、そのパスをハミルトン経路というのだとか。
ご意見どうもありがとうございます。
すべての地点を無駄なく周遊する経路の事に関しまして、
同雑誌に郵便配達人問題を利用した「乗りつぶしのOR」という
筑波大学のS教授の論文が記載されています。
社長の全国の支店の視察には、こちらのほうが近いものかと思いました。
参考となる資料を提示していないのに、
このような書き込みをするのも変なことではありますが。
失礼なリスポンスと感じたらすみません。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
research onと research in
-
バイオインフォの需要、勉強法
-
開発研究?研究開発?
-
「本学」「本学部」「本専攻」...
-
言語学はなぜ人文科学に分類さ...
-
卒業論文のテーマについて
-
心理学と哲学の違い
-
major inの後ろって・・・
-
日本の量子技術は今どんな感じ...
-
会社は「御社」、研究所は?呼...
-
研究所に応募するときは、「御...
-
大学教授職の方と結婚された方...
-
筑波大学理工学部と早稲田大学...
-
大学院生で学会経験無し
-
理系の男性が「この人、俺に惚...
-
大学所属の研究者の方に聞きた...
-
理系の大学院生かつ就活中って...
-
独立行政法人の呼び方をお教え...
-
大学学内における学生の夜間残...
-
学会などの懇親会にできれば参...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
おすすめ情報