最短最長ルート問題
ナビゲーションに移動
検索に移動
【さいたんさいちょうるーともんだい (shortest-longest route problem)】
いわゆる最短ルート問題ではルート上の数値の総和を動的計画法によって最小にしている. しかし, 負値を許した数値の積(負値乗法型)で評価するときなどは, 単に最短部分ルート問題だけを考えるだけでは, いわゆる再帰式は成立しない. このとき, 最長部分ルート問題までも考慮した問題を最短最長ルート問題という. これは両的計画法による両帰式で解ける.