「最短最長ルート問題」の版間の差分
ナビゲーションに移動
検索に移動
(新しいページ: ''''【さいたんさいちょうるーともんだい (shortest-longest route problem)】''' いわゆる最短ルート問題ではルート上の数値の総和を動的計...') |
細 ("最短最長ルート問題" を保護しました。 [edit=sysop:move=sysop]) |
(相違点なし)
| |
2007年7月20日 (金) 10:27時点における版
【さいたんさいちょうるーともんだい (shortest-longest route problem)】
いわゆる最短ルート問題ではルート上の数値の総和を動的計画法によって最小にしている. しかし, 負値を許した数値の積(負値乗法型)で評価するときなどは, 単に最短部分ルート問題だけを考えるだけでは, いわゆる再帰式は成立しない. このとき, 最長部分ルート問題までも考慮した問題を最短最長ルート問題という. これは両的計画法による両帰式で解ける.