RUS  ENG
Полная версия
СЕМИНАРЫ

Семинар отдела управляемых систем
28 мая 2015 г. 12:00, г. Екатеринбург, ул. С. Ковалевской, 16, комн. 322


Метод ветвей и границ в динамическом программировании

Я. В. Салий

Аннотация: Вероятно, многим из применявших динамическое программирование в задачах дискретной оптимизации приходила в голову идея отбрасывать часть состояний (позиций) как бесперспективные на по возможности раннем этапе построения функции Беллмана — ведь так можно сэкономить и память и вычисления. Оказывается, в 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


© МИАН, 2024