「最短最長ルート問題」の版間の差分
ナビゲーションに移動
検索に移動
細 ("最短最長ルート問題" を保護しました。 [edit=sysop:move=sysop]) |
Albeit-Kun (トーク | 投稿記録) |
||
| 2行目: | 2行目: | ||
いわゆる最短ルート問題ではルート上の数値の総和を動的計画法によって最小にしている. しかし, 負値を許した数値の積(負値乗法型)で評価するときなどは, 単に最短部分ルート問題だけを考えるだけでは, いわゆる再帰式は成立しない. このとき, 最長部分ルート問題までも考慮した問題を最短最長ルート問題という. これは両的計画法による両帰式で解ける. | いわゆる最短ルート問題ではルート上の数値の総和を動的計画法によって最小にしている. しかし, 負値を許した数値の積(負値乗法型)で評価するときなどは, 単に最短部分ルート問題だけを考えるだけでは, いわゆる再帰式は成立しない. このとき, 最長部分ルート問題までも考慮した問題を最短最長ルート問題という. これは両的計画法による両帰式で解ける. | ||
| + | |||
| + | [[Category:動的・確率・多目的計画|さいたんさいちょうるーともんだい]] | ||
2008年11月9日 (日) 17:58時点における最新版
【さいたんさいちょうるーともんだい (shortest-longest route problem)】
いわゆる最短ルート問題ではルート上の数値の総和を動的計画法によって最小にしている. しかし, 負値を許した数値の積(負値乗法型)で評価するときなどは, 単に最短部分ルート問題だけを考えるだけでは, いわゆる再帰式は成立しない. このとき, 最長部分ルート問題までも考慮した問題を最短最長ルート問題という. これは両的計画法による両帰式で解ける.