最大効率経路問題とい - 数学＠ふたば保管庫

数学＠ふたば保管庫 [戻る]

最大効率経路問題というのを思いついたけど解き方が分からない

有向グラフの各辺にスコアと時間の正実数の組(s,t)が割り当てられている
ノードnとmを結ぶ辺(s1,t1),(s2,t2),...,(sk,tk)の「効率」をΣsi/Σti で定義する
(これは直感的に単位時間あたりにどれだけのスコアを稼げるかという指標になっている)
任意のノードnからmに至る経路で効率を最大化するパスをどうやって求めたらいいだろうか…

画像はダイクストラ法

効率が悪い経路でも
それが短時間で済むならば
ほとんど障害にならないっていう感じか

>効率が悪い経路でも
>それが短時間で済むならば
>ほとんど障害にならないっていう感じか
言いたいことはあってる
「効率」って語をスレで違う意味で定義しちゃったから
正しくは
>スコアの和が悪い経路でも
>それが短時間で済むならば

>効率が悪い経路が最大効率経路の部分に含まれていても
>それが短時間で済むならば
>ほとんど障害にならないっていう感じか
もしくはこういう意味かな

気づいたけど
効率がxの閉路が到達可能な場所にあったらそこを無限回繰り返し通ることで
任意のノード間の効率もxに限りなく近くできる
だから問題の本質は最大効率の"閉路"を求める事ですね…

こんなグラフですら経路決定は相当複雑に思える

最小費用流問題は参考にならんかね

たとえば

http://dopal.cs.uec.ac.jp/okamotoy/lect/2013/opt/handout13.pdf

アメーバ様にお願いする
http://wired.jp/2010/02/16/%E3%80%8C%E7%B2%98%E8%8F%8C%E3%81%AE%E7%9F%A5%E6%80%A7%E3%80%8D%E3%82%92%E8%A7%A3%E6%98%8E%EF%BC%9A%E8%A8%98%E6%86%B6%E3%82%84%E4%BA%88%E6%B8%AC%E3%82%82%E5%8F%AF%E8%83%BD%E3%81%AA%E3%83%8D%E3%83%83/

最大効率経路の部分経路が最大効率経路になってないからそのままじゃDPは使えない
とりあえず以下↓の性質を使ってどうにかするしかなさ気

・任意の正の実数 s,t,s',t'に対して
s/t < s'/t' ⇔ s/t < (s+s')/(t+t') < s'/t' が成立
・従ってグラフの中で最も大きな効率をもつ"辺"を(s,t)とすると、任意の"経路"の効率はs/t以下

シャボン玉作戦は?

UCBでモンテカルロすればいいんｼﾞｬﾈｰﾉ（適当

クラスNPなのかと思ったけれど
解が本当に解なのかを確かめるのも多項式時間じゃできなさそうだからNPよりも難しい問題なのかな

パソコンが嫌いな計算そう

スコア＝総得点

最短経路求めるなら駅スパート法でいいじゃないの？