Эвристические методы разработки алгоритмов

Под эвристическими понимаются методы, правильность которых не доказана. Они выглядят правдоподобными, кажется, что в большинстве случаев они должны давать верное решение. Иногда не удается построить контрпример, демонстрирующий ошибочность или неуниверсальность метода. Но не удается доказать математическими средствами и правильность метода. Тем не менее практика использования эвристических методов дает положительные результаты.

Динамическое программирование

В наиболее общей форме так называют процесс пошагового решения задач, когда на каждом шаге выбирается одно значение из множества допустимых на этом шаге, причем такое, которое оптимизирует заданную цель.

Часто не удается разбить задачу на небольшое число подзадач, объединенное решение которых позволяет получить решение искомых задач. Можно попытаться разделить задачу на столько задач, сколько необходимо, затем каждую на еще более мелкие и т.д. Иногда проще создать таблицу решения всех подзадач, независимо от того, нужна она или нет. Заполнение таблиц — решение подзадач для получения решения определенной задачи — в теории алгоритмов получило название динамического программирования. Формы алгоритмов динамического программирования могут быть разными, общими могут быть лишь заполненные таблицы и порядок заполнения их элементов.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >