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

    На этом шаге мы рассмотрим эвристические методы разработки алгоритмов.

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

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

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

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

    На следующем шаге мы введем понятие динамического программирования.




Предыдущий шаг Содержание Следующий шаг