Никто не спорит, но
1. расход памяти
2. сложность по времени всё равно больше, чем у эвристик.
Хотя, соглашусь с Вами, динамическое программирование — очень и очень мощный аппарат.
Просмотр одного процента узлов — это ожидаемая эффективность метода ветвей и границ.
А скорость расчёта… Давайте пойдём от обратного. Предположим, что эта задача и правда решается за секунду. Это значит, что в секунду будет перебрано 3*10^16 узлов. Предположим также, что просмотр узла занимает один такт процессора. Получается, что Ваш компьютер работает на частоте 10 пета(!)герц? P.S. И нет, мне не смешно.
Не люблю заниматься арифметикой, но вы неправы:
Строго говоря, я тоже загнул насчёт миллионов лет, но 1100 лет это совсем не те доли секунд, о которых Вы говорите.
В этом и есть суть эвристик. Они почти никогда не дают глобально-оптимальный результат. Решение найденное с помощью эвристических алгоритмов гарантированно не худшее и с очень большой долей вероятности его можно назвать хорошим. Главный плюс этих алгоритмов в том, что они работают быстро и могут дать хоть какой-то результат в приемлемое время.
Быть может, каждый программист и обязан это знать, но 28 человек добавили этот топик в избранное, а значит, кому-то это всё-таки нужно, интересно, полезно.
1. расход памяти
2. сложность по времени всё равно больше, чем у эвристик.
Хотя, соглашусь с Вами, динамическое программирование — очень и очень мощный аппарат.
А скорость расчёта… Давайте пойдём от обратного. Предположим, что эта задача и правда решается за секунду. Это значит, что в секунду будет перебрано 3*10^16 узлов. Предположим также, что просмотр узла занимает один такт процессора. Получается, что Ваш компьютер работает на частоте 10 пета(!)герц? P.S. И нет, мне не смешно.
Строго говоря, я тоже загнул насчёт миллионов лет, но 1100 лет это совсем не те доли секунд, о которых Вы говорите.
h[1]:=31; h[2]:=15; h[3]:=7; h[4]:=3; h[5]:=1;