|
|
Семинар отдела управляемых систем
28 мая 2015 г. 12:00, г. Екатеринбург, ул. С. Ковалевской, 16, комн. 322
|
|
|
|
|
|
Метод ветвей и границ в динамическом программировании
Я. В. Салий |
Количество просмотров: |
Эта страница: | 123 |
|
Аннотация:
Вероятно, многим из применявших динамическое программирование в задачах дискретной оптимизации приходила в голову идея отбрасывать часть состояний (позиций) как бесперспективные на по возможности раннем этапе построения функции Беллмана — ведь так можно сэкономить и память и вычисления. Оказывается, в 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
|
|