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