最短・最長ルート問題

OR事典

最短最長ルート問題

読み方：さいたんさいちょうるーともんだい
【英】：shortest-longest route problem

いわゆる最短ルート問題ではルート上の数値の総和を動的計画法によって最小にしている. しかし, 負値を許した数値の積(負値乗法型)で評価するときなどは, 単に最短部分ルート問題だけを考えるだけでは, いわゆる再帰式は成立しない. このとき, 最長部分ルート問題までも考慮した問題を最短最長ルート問題という. これは両的計画法による両帰式で解ける.

「OR事典」の他の用語

動的・確率・多目的計画：

多重積分の解法  完全情報の期待価値  対話型解法  最短最長ルート問題  最適停止  最適性の原理  期待値最適化