グラフの問題です。
飲食店が点Ai、それをつなぐ道路Giが辺で現されたグラフ上を自転車旅行します。
飲食店Aiでは指定されたカロリーがCi摂取でき、道路Giでは移動にカロリーKiを消費するとします。
グラフのつながりとそれぞれのCi、Ki、出発点A、ゴールBが指定されるとき
自転車旅行で点から点へ移動して同じ点に二度とよらずに目的地へ向かうとき。
Ans＝途中の経路で摂取するCiの総計ー消費するKiの総計
Ansが最大になるような経路もしくはAnsの最大値のみを求める
アルゴリズムにどんなものがあるのでしょうか？
この質問を思いついた経緯
もともとは
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0224
地点ごとにあるケーキ屋でカロリー補給しながら役所へ向かう自転車移動をモチーフにした問題をといてるときに考え付きました。
リンク先ではカロリー摂取量０の地点がたくさんありカロリーが摂取できる
店が少ないということを利用して高校生でもとけるようにやさしくなっています。
高校生レベルの解法としてはこの問題はケーキ屋の数が少ないことを利用して解きます。
まずワーシャルフロイド法を少し改変して間にケーキ屋を含まない全ての地点間の最短距離を求めます。
最短距離を求めたら後はこのグラフを使って家から直接役所へ。
次にケーキ屋を一つ挟んで役所へ。
２つ挟んで役所へ、、、
という探索を深さ優先探索で求めます。
この問題を解くのに３日かかりました。
コードはリンク先の0224 Bicycle Dietという小タイトルがついた部分に掲載しています。
http://www14.atwiki.jp/c21coterie/pages/479.html
ですがこの問題、ケーキ屋の数が増えた場合のとき方をいくら考えても思いつきません。
この問題に対してどんな考え方があるのでしょうか？
私はプログラマとしてはまだまだ初心者レベル。
グラフ理論も詳しくないので大雑把な概念や考え方からご教示いただけたらありがたいです。
ケーキ屋A,Bでのカロリー消費量を-A, -B,
その二つをつなぐルートでのカロリー消費量をEとしたとき、
A→B と辿ったときのカロリー消費量は E-B
B→A と辿ったときのカロリー消費量は E-A
順路によって重みの異なるルートと考え
ケーキ屋でのカロリー消費量を0とすればなんかできそうな「気がする」。
とりあえずワーシャルフロイド法＋επιστημηさんのいう非対称な重み突きグラフとしてみれば結構いい線いけそうですね。
ありがとうございます。
幾つかの地点を一周して元の地点に戻るとき摂取カロリーのほうが多くなるような経路がある場合、そこを何週もしてしまうと答えが無限になる選択肢が出てきます。
ワーシャルフロイドを適用した結果このような閉路が影響する危険性は排除できるのでしょうか？
論理的な整合性やどうやったら同じ地点を一度以上通らないということを安全にルールに組み込めるか知りたいところです。
ほかの手法のほうが良いでしょうか？
→OP＝→OA＋ｔ→AB
ぷくぷくのように緩急をつける場合
→OP＝→OA＋ｆ（ｔ）→AB
まあどうでもいいですが。
ベクトル作った人って偉大ですよね。
うーんちょっと考えてみたのですが、ワーシャルフロイド法をそのままでは駄目でした。
ダイクストラ法はいわゆる負閉路に引っかかってしまうのでたぶん駄目。
ワーシャルフロイド法に2地点間を結ぶ最短経路全ての点を記録しておいて、これを使って制限を設ければ上手くいくような気もします。
3重ループの中で2点ABを中継点Cを介して結ぶとき、AC,CBを最短で結ぶ2つの経路に共通する部分があればABを辺でなげないという制限を設ければ同じ地点は2度通らないということは実現できそうな気もするのですが。
上手くいかなさそうな気もします。
答えはワーシャルフロイド法で検討するルートに制限をかけたサブセットだろうというイメージはあるのですがなかなか難しいです。
もしNP困難だとしたら最適解はあきらめるしかないですよね。
五目並べも挫折なら、コレも挫折だろう。
なにをやっても、かじりっぱなし（笑）
＾＿＾；
http://www.geocities.jp/sinapusu2002/suugaku/mozzikkoTest8.htm
ボールを動かせといわれたので、昔作ったボールを動かしたのがありました。
大昔に作ったスクリプトでIE6でしか試していませんが要望どうりボールを動かしています。
（１）「ダイクストラ 負」での検索結果みつけたもの：
http://coconut.sys.eng.shizuoka.ac.jp/gnB/06/handout9.pdf
大学の講義資料(PDF)のようですが，これではダメでしょうか
（私は全くまともに見てませんけど，なにやら負の経路に対応できるような感じ？）
あと「同一経路を通らない」ようにしたいなら単に探索した経路を覚えておけば良いと思うのですが，
そうしない（orできない）理由があるのでしょうか
（２）他所でも同一の質問をされていませんでしたか
そういう場合は，その旨に触れるほうがよいかも？
（３）これは個人的連絡になってしまいますが，
過去にメールを送ったつもりなのですが届いてませんでしょうか
＃あと，そろそろスルーを覚えませんか
>ゲームの追跡ミサイルのアルゴリズムと同じです。
それは違います。
文字列の座標を最初に全部求めて、その点を通る曲線をニュートン補完で求めているので逐次計算とは少し違います。
求めた経路を線形補完してますし。
http://coconut.sys.eng.shizuoka.ac.jp/gnB/06/handout9.pdf
かなり親切に書いてる感じですね。
参考になります。
計算量を考えると点の数が増えたとき単純な探索は不可能。
２点をもっとも高いカロリー量でつなぐ経路の保存は経路上の点一つを一ビットで保存してintの配列として保存しておけば計算量が落ちますね。
経路保存ですが、ワーシャルフロイド法の3重ループの一番内側のループで点を辺でつなげる場合、エネルギー量最大でつなげる経路に共通点があるかのチェックがBit演算になるので早くなります。
N^3Log(32,N)になる野はかなりうれしい感じです。
まあ私が前に書き込んだ方法でウマくいけばですが。
とりあえずベルマンフォード法勉強してみることにします。
よそでも質問しましたがまったく返答がないのでそちらはあきらめてます。
最近メールアドレス変えたときにちょうどパソが壊れまして修理中、それから借りたパソを使ってるのでメール届いてないかもしれません。
せっかく親切にしていただいたのにすいません。
前回書いたのですが計算量間違えてました。
(N^4)/32ですね。
ホウジョウウサギさんの返答で十分ありがたい返答だということを理解してないのはレオさんだけだと思いますけど？
それに普遍的なアルゴリズムを聞いて、普遍的な考え方を聞いてるだけなのに詳細なコードに立ち入らないと駄目なほうが不思議です。
こういう問題は瑣末な細部より普遍的な考え方のほうが重要です。
この板では抽象的なアルゴリズムの質問に答えられる人がホウジョウウサギさんだけなのでしょうか？
レオさんは相当コードがかけるようですね。
私のボールのやつ、15分でかけるというなら一つ書いてみていただけませんか？
私がミサイル追尾で作ろうとしたら、目標地点の周りでくるくる回って到達できず人文字が完成しないことになりそうなのでどんな風に作成されるのか興味があります。
勉強させていただけたらうれしいです。
ちなみに私の場合ｙ＝ｆ（ｘ）のニュートン補完の方法だけ本で調べて残りは何も読まずにコードを記述しました。
なのでDHTMLを解した簡易オブジェクト指向で自作する能力はあります。
クラスや継承や画面出力の記述をコードリーディングする能力くらいはあるので、ぜひ読んでみたいです。
やっぱり私のようなアマチュア低レベルプログラマからみたら想像もつかない短縮技法とかコードの流用とか色々参考にしたいです。
とりあえずコードを書いたほうがいいとのことでしたので、自分で考えた方法でコードを実装してみました。
まだコンパイルが通っただけで未テストです。
同じ地点を2度と通らないという条件で全2地点間を最短で結ぶコストを求めてみました。
まだプログラマとしては初心者レベルなのでコードがうまくいっているかどうかわからない状態です。
#include<stdio.h>
const int size=100;//グラフの最大サイズ、適当な値
const int max=1000000000;
const int memoSize=(size-1)/32+1;
int g[size][size];//グラフ
int rootMemo[size][size][memoSize];//グラフ間の2地点をつなぐ最大カロリー経路で通る地点を１bit単位で保存
bool connectOK(int k,int i,int j){
//点iとk kとｊを結ぶ最大カロリー経路に重複部分がないかチェック
for(int l=0;l<memoSize;l++){
if((rootMemo[i][k][l]&rootMemo[k][j][l])!=0) return false;
}
return true;
}
void connect(int k,int i,int j){
for(int l=0;l<memoSize;l++){
rootMemo[i][j][l]=rootMemo[i][k][l]|rootMemo[k][j][l];
}
rootMemo[i][j][k/32]|=(k%32);
}
void wf(int m){
//拡張ワーシャルフロイド法
int t;
for(int k=0;k<m;k++){
for(int i=0;i<m;i++){
if(g[i][k]==max)continue;
for(int j=0;j<m;j++){
if(g[k][j]==max)continue;
t=g[i][k]+g[k][j];
if(t<g[i][j] && connectOK(k,i,j)){
connect(k,i,j);
}
}
}
}
}
int main()
{
int n,m;//nはノードの数、ｍは点の数,点は０からｍ−１まで番号をつける
scanf("%d %d",&n,&m);
for(int i=0;i<m;i++){
for(int j=0;j<m;j++){
g[i][j]=max;
for(int k=0;k<memoSize;k++){
rootMemo[i][j][k]=0;//経路の初期化
}
}
}
int a,b,c;
for(int i=0;i<n;i++){
scanf("%d %d %d",&a,&b,&c);//ノードの重み、道路で消費するカロリー。
g[a][b]=g[b][a]=c;
}
for(int i=0;i<m;i++){
scanf("%d",&c);//点で得られる重み、店舗で摂取できるカロリー
for(int j=0;j<m;j++){
if(g[j][i]!=max)g[j][i]-=c;
}
g[i][i]=max;
}
wf(m);
//ここの時点で同じ地点を2度と通らず結んだ最短経路が配列ｇに出力されているはず
}
>>rootMemo[i][j][k/32]|=(k%32);
rootMemo[i][j][k/32]|=1<<(k%32);
でした。
ほかにも書き間違いがあるかもしれません。
根本的な考え方が間違ってる可能性もあるのでご指摘お願いします。
すいません書き間違いその２です。
>>全2地点間を最短で結ぶコストを求めてみました。
同じ地点は2度通らないという条件で最高カロリーを全2地点間で求めてみました。
こういう不注意はものすごく恥ずかしいです。
れお先生さん言ってることの意味が分からないのですが？
警察沙汰？
何の話です？
一応記述ミス追記。
if(t<g[i][j] && connectOK(k,i,j)){
connect(k,i,j);
g[i][j]=t;//ｇの更新を忘れていました。
}
道路と店舗でのカロリーの正負の符号の扱いも間違ってました。
今のままのコードだと、カロリー最低値の経路をｇに出力してしまいますね。
とりあえず短時間で一気呵成に書いただけのノーチェック、ノーテストのコードだとミスが見つかるものですね。
ちょっと時間を置いて自分で出来るだけコードをチェックしてみますがご指摘があればうれしいです。
前回掲載のコードぜんぜん駄目でした。
ベルマンフォード法も難しいけどがんばって読んでみました。
この手法も負の辺を許すだけで負閉路がある場合は無理なんですね。
負閉路がある場合、同じ辺を一度も通らないや同じ点を2度通らないという条件を加えると一気に問題が難しくなるようです。
Wikiで負閉路があるグラフの場合、同じ辺を通らないという条件で計算する方法があるとの記述を読みましたが詳細は載っていませんでした。
ただ手法を使えるというだけでなく大雑把な原理程度は理解したいところです、まずは手法の名前から知りたいところですが。
ベルマンフォード法は
負の閉路というのが点A→点Bのコストがー４で点B→点Aへのコストが３だとこれも2点の負の閉路になる。
と考えるのでしょうか？
グラフに負の閉路がなければ、ある点Aから出発してAに戻ってきたとき必ずコストが大きくなって帰ってくる。
これが全ての点で成り立つから、ベルマン法で求める最短経路に同じ点は2度と出てこない。
という理解でよいでしょうか？
数学で読むと難しそうでもコードになるとなんとなく理解できそうな気もします。
れお先生さん話が良く分かりませんがまあ何かが解決したのですね。
私の場合最近安いプロパイダに乗換えたのでお気になさらずに。
NTTがざるなんて知りませんでした。
KDDIとかのほうがましなんですか？
グラフなのですがベルマフォード法で、その地点への最高カロリー量になる経路を点ごとに保存しておいて、点の最大値を更新する前に通った点でないかチェックすれば同じ点を2度と通らずに上手くいくような気がしてきました。
素人の浅知恵なので上手くいかないかもしれませんが試してみようかと考えています。
逆に聞く形になってしまいますが，私が調べた感じ
ベルマンフォード法は以下のようなアルゴリズムという認識ですがこれでＯＫでしょうか？
（便宜上，処理単位を"Turn"と記し，ノード個数をNとする）
[開始処理]
・開始点への到達コストを0に（更新）する
・その他のノードの到達コストは∞としておく
・Turn=0
[各Turnでの処理]
・前Turnで到達コストが更新されたノード群について，隣接ノードへの到達コストを計算．
それが，既存の結果よりも小さいコストであれば，隣接ノードの到達コストを更新する
・Turn++
・if( Turn>=N )終了処理へ
else ループ
[終了処理]
・もし，未だに更新が可能な個所が残っているならば，
それは負の閉路に捕らわれた探索個所が残っているのであり，
”最短経路はない”が答えとなる．
・負の閉路が存在しないならば，この時点で答えが求まっている
アルゴリズムがこれで合っているならば，おっしゃる通り，
更新していく情報に「通ったノード群」を追加してやればいけそうに思います．
＃メール到達失敗の件は了解しました．
（ということは，現在，メールは使用不可ということなのかな？）
メールは使えません。
最近英語の勉強始めましてプログラムの勉強滞っています。
なので前回書いた方法まだアルゴリズム試していません。
書いて試すまでは一瞬なのですが、もしある程度ウマくいって本当にいかなる場合でもうまくいくかの検証をし始めると相当長くなりそうなのでなかなか食指が動かず。
>更新していく情報に「通ったノード群」を追加してやればいけそうに思います．
？
通った点でなく、ノードですか？
点では駄目そうな理由をお願いします。
いろいろあるのでしょうが，
問題を提起して意見を求めている側の立場から
そのようなことを言うのはいかがなものかと思いますが…
それならそれで
「忙しくなりこの問題に関われなくなったので一旦閉じます」
とかなんとか言って 打ち切るなりされるべきかなと存じます．
（他の質問も放置されているものが散見されますし，明らかな荒しに都度関わる等…
>この板では抽象的なアルゴリズムの質問に答えられる人がホウジョウウサギさんだけなのでしょうか？
等とおっしゃっておられますが，
質問内容が場とややマッチしていないのを差し引いても，レスがつかない理由が他にもあるとは思いませんか？
）
点を線で結んだものを「グラフ」と称して論じる際は
点→ノード
線→エッジ
と呼ぶものだと記憶していましたが…
本当ですね。
ノード＝点でした勘違いです。
うーん私としてはかなりの日数が過ぎたのに全く返答がつかないというのが疑問なのですが？
ただ単純に適したアルゴリズムの種類を聞いているだけなのでアルゴリズムの名前をピシリとお教えいただいて数回のレスで終わるものだとばかり思っていました。
ベルマンフォード法の拡張で100％うまくいくか検証する能力が私にないのであきらめます。
>ただ単純に適したアルゴリズムの種類を聞いているだけなのでアルゴリズムの名前をピシリとお教えいただいて数回のレスで終わるものだとばかり思っていました。
それは無理でしょう(vv;)。
ホウジョウウサギさんが暗に指摘しているように、
ここは「プログラム用」の掲示板であって、
「アルゴリズム用」の掲示板でないことをご確認ください。
また、一般的なプログラマは、名前が付いているような
ある程度以上に複雑なアルゴリズムを使用する機会は、
ほとんどないと断言しておきます(笑)。
オレの貼り付けURLが消えてるぞ。＾＾
フロチャートが書けなきゃ、プログラムを作れるわけないだろ。
まったく、人の善意を悪意に取るなよぉ〜。