Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow Информатика

Метод полного перебора

Берется некоторое подмножество исходных данных и непосредственной проверкой (решением задачи) проверяется, удовлетворяет ли это подмножество поставленному условию. Поскольку различных подмножеств имеется конечное число, то потенциально можно перебрать все подмножества и найти решение.

Сложность заключается в том, что с увеличением количества исходных данных (при переходе от к ) быстро увеличивается необходимое число проверок. Метод полного перебора применим в тех случаях, когда искомое решение принадлежит некоторой конечной области и может быть найдена простая функция quality (Y) для проверки правильности (или качества) выбранного решения. Тогда задача Р вычисления функции заменяется многократным решением задачи R вычисления функции quality (столько раз, сколько элементов имеется в области решений). Причем в общем случае просмотреть нужно всю область, и порядок, в котором просматриваются элементы, не важен.

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

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

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

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

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

 
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы