掲示板システム
ホーム
アクセス解析
カテゴリ
ログアウト
初歩的なグラフの問題 (ID:72926)
名前
ホームページ(ブログ、Twitterなど)のURL (省略可)
本文
グラフの問題です。 飲食店が点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 ですがこの問題、ケーキ屋の数が増えた場合のとき方をいくら考えても思いつきません。 この問題に対してどんな考え方があるのでしょうか？ 私はプログラマとしてはまだまだ初心者レベル。 グラフ理論も詳しくないので大雑把な概念や考え方からご教示いただけたらありがたいです。
←解決時は質問者本人がここをチェックしてください。
更新する
戻る
掲示板システム
Copyright 2021 Takeshi Okamoto All Rights Reserved.