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

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

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

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

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

このQ&Aに関連する最新のQ&A

A 回答 (4件)

最長路問題(longest path problem)ならば


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

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

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

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

さらに「枝の距離が負」であることを許すと
最短路と最長路の区別がなくなり(最長路=符号反転して最短路),
最短路問題に見えても実は最長路問題ということもあります.
    • good
    • 0
この回答へのお礼

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

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

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

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

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

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

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


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

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

参考URL:http://www.swa.gr.jp/lop/
    • good
    • 0
この回答へのお礼

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

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

むか~しの bit ですか?


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

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

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

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

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

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


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

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

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

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

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

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Qルービックキューブの解き方

ルービックキューブを、1分程度で元に戻す人をテレビなどで見ますが、私もやってみたいです。
ルービックキューブの解き方についてのコツが書いてある本などありませんか?

Aベストアンサー

http://aym.pekori.to/rubik/rubik1.html
これでばっちり。
わたしもこれでできるようになりました。

Qルートの中にルート

√(5-2√5)=x/(50-x)をx=の形にしたいのですが
やり方がまったく分からないので教えてください

Aベストアンサー

x=の形にするのであれば,ルートの中のルートなどは気にする必要はありません.

√(5-2√5) = x/(50-x)
(50-x)√(5-2√5) = x
50√(5-2√5) - x√(5-2√5) = x
50√(5-2√5) = x + x√(5-2√5)
50√(5-2√5) = x(1+√(5-2√5))
50√(5-2√5) / {(1+√(5-2√5))} = x

x = {50√(5-2√5)} / {(1+√(5-2√5))}

でどうでしょう.

Qルービックキューブの解き方を教えてください。

2X2のキューブです。どのHPを見てもこのタイプは出ていませんので、どなたか教えてください。私のレベルは1面作れる程度です。

Aベストアンサー

 いくつかのサイトをご紹介します。

 これらは3×3のキューブの解き方を解説していますが、2X2の場合は、このうち「四隅だけを揃える」ことと同じだと考えて下さい。

 以下のどのサイトをご覧になっても、できると思います。

http://www-itolab.ics.nitech.ac.jp/~water/cube/
http://aym.pekori.to/rubik/
http://www.analogmonkey.com/rubik.html

Qルートを外す:ルート1521=39

中2の息子の数学ですが、ルート1521=39というのがあります。

この39を簡単に出す方法はあるのでしょうか?グーグルで検索するときは、何の解き方とすれば出てくるのでしょうか?

よろしくお願いします。

Aベストアンサー

1521を因数分解してみると簡単にルートを外せます。
1521=3•3•13•13
ルートとはルートした数(ここでは39)を2回かけることによってルートをとる前の数(=1521)になるものの事をいうので、上の因数分解した式より13×3=39とわかります。

Q立体キューブの解き方教えてください!!

キティちゃんの立体キューブをもらいました。
2×2×2 のルービックキューブ(ミニ?)同様のものです。
これにかなり手こずっております。

いろいろサイト検索したのですが、3×3×3の通常のルービックキューブの
解き方しか見つけられませんでした。
同じように解けばいいのかな?と思ったのですが、自分の頭では無理でした...^ ^;)

すみませんが、解き方や、解説のあるページがありましたら教えてください。

Aベストアンサー

ここを見れば解ると思います。

参考URL:http://wakame.mtl.kyoto-u.ac.jp/shingu_ken/student/mori/rubik/rubik_c.html

Q複素数の質問です。 Z1=1+ルート3i Z2=ルート3+i この場合 Z1+Z2はどうなりますか?

複素数の質問です。
Z1=1+ルート3i
Z2=ルート3+i
この場合
Z1+Z2はどうなりますか?
Z1-Z2はどうなりますか?

テキストに、複素数の積と商のやり方は載っていたのですが、和と差のやり方がありませんでした。教えてください。お願いします。

Aベストアンサー

実数部どうし、虚数部どうしを足し算、引き算すればよいだけです。

>和と差のやり方がありませんでした。

よく探してください。一番最初に書いてあるでしょう?

Q「A地点とB地点にいる二人が同時に出発して接近した」この問題の解き方を教えてください

「A地点とB地点にいる二人が同時に出発して接近した」この問題の解き方を教えてください

問題
A地点にいるA君と、B地点にいるB君が同時に出発して接近した。
A君は時速4キロ、B君は時速8キロで移動した
A地点とB地点は10キロ離れている
さて二人が接触する地点の位置はどこで、出発時刻から何分後か?
道中は平坦な直線であり途中に坂や障害などはないとする

さてこの問題の解き方を教えてください

小学校算数での解き方、
中学校数学での解き方、
高校数学での解き方、
それぞれ教えてください

Aベストアンサー

A君は時速4キロ、B君は時速8キロで近づいているので、
合わせて時速12キロで近付いています。
2人が接触するのは10/12=50/60時間=50分です。

t分後に接触したとして、
A君は時速4キロで、4*t/60キロ移動しています。
B君は時速8キロで、8*t/60キロ移動しています。
二人は合計で10キロ移動したので、
4*t/60+8*t/60=10
12t=600
t=50分後です。

A君は時速4キロでxキロ、
B君は時速8キロでyキロ、
走った時に接触したとして、
x+y=10
x/4=y/8
なので、
x=2y
3y=10
y=10/3
10/3÷4=10/12時間=50分後です。

Qグラフ理論における最長パス

「連結グラフにおいて最長パスは必ず共通点を持つことを証明せよ」という問題を学校でだされたのですがどうしてもわかりません解き方をわかる方もしくはわかるサイトをお知りの方教えてください

Aベストアンサー

下記に証明があります。
(2章の9.を見てください)

http://coolee.at.infoseek.co.jp/graph_ensyuu_sol.html

Q問題の解き方をHPにのせるときの著作権について

はじめまして。
HPに学習ページをつくろうと思っています。
教科書の章末問題などでは、問題と答えだけしかのってないものがありますよね。
自分流に問題をといて、解き方をHP上にのせるのは
著作権の侵害になるのでしょうか?
「~~という本のP32の問1の解き方」とか書いたら侵害になるのでしょうか?
こういうタイトルをかかないで、問題と解き方だけを書いたほうがいいのでしょか?

Aベストアンサー

> 自分流に問題をといて、解き方をHP上にのせるのは
著作権の侵害になるのでしょうか?

なりません。

> 「~~という本のP32の問1の解き方」とか書いたら侵害になるのでしょうか?

もし、このURLに書いてみる内容と合致すれば、
問題ないのかも。
http://www.cric.or.jp/qa/sodan/sodan6_qa.html

私も法律家ではないので詳しくはないですが、
こちらを参考にされてみてはいかが?
http://www.cric.or.jp/

Qルービックキューブの最短で最長の回数

お世話になります。
先日、とある映画でルービックキューブを使ったシーンがあり、ふと疑問に思ったのですが、
一般的な3×3のルービックキューブ6面の色を最短で揃えるとして、最も長くかかる場合、
何回動かすことになるのでしょうか。
よろしくお願いします。

Aベストアンサー

追記。

言うまでもありませんが「今のところ26回」です。

「26回かかる組み合わせのどれか1つで、これ以上の短縮は不可能」ってのが証明されない限り、26回が最終的な答えにはなりません。

将来「26回かかる組み合わせのを全部調査したら、すべての組み合わせで短縮が可能で、実は25回だった」ってのが証明される可能性があります。


人気Q&Aランキング

おすすめ情報