Аннотация:
Вероятно, многим из применявших динамическое программирование в задачах дискретной оптимизации приходила в голову идея отбрасывать часть состояний (позиций) как бесперспективные на по возможности раннем этапе построения функции Беллмана — ведь так можно сэкономить и память и вычисления. Оказывается, в 1976 году эта идея была строго оформлена Мориным и Марстеном в применении к задаче коммивояжера и нелинейной задаче о рюкзаке.
Судя по цитированиям статьи, никто не успел применить этот метод к задаче курьера, между тем, он кажется достаточно интересным, ведь нижние границы можно получать через Конкорд.
Оригинальная статья:
Branch-And-Bound Strategies for Dynamic Programming / Th.L.Morin, R.E.Marsten // Operations Research. – Vol. 24 – No. 4 (Jul. - Aug. 1976), pp. 611–627
|
