Метод перебора как наиболее универсальный метод поиска решений. Методы ускорения перебора
Как Вы уже знаете, существуют задачи, для которых доказано отсутствие общего алгоритма решения (например, задача о разрешимости Диофантова множества). В то же время можно сказать, что, если бы мы обладали бесконечным запасом времени и соответствующими ресурсами, то мы могли бы найти решение любой задачи. Здесь имеется в виду не конструирование нового знания на основании имеющегося (вывод новых теорем из аксиом и уже выведенных теорем), а, прежде всего, "тупой" перебор вариантов.
Еще в XVII столетии великий Лейбниц пытался раскрыть тайну "Всеобщего Искусства Изобретения". Он утверждал, что одной из двух частей этого искусства является комбинаторика— перебор постепенно усложняющихся комбинаций исходных данных. Второй частью является эвристика — свойство догадки человека. И сейчас вторая часть Искусства Изобретения все еще остается нераскрытой. На языке нашего времени эта часть — модель мышления человека, включающая в себя процессы генерации эвристик (догадок, изобретений, открытий).
Однако прежде чем перейти к рассмотрению улучшенных переборных алгоритмов (улучшенных потому, что для простого перебора у нас в запасе нет вечности), я бы отметил еще один универсальный метод ускорения перебора — быстрое отсечение ложных (или вероятно ложных, что и используется большинством алгоритмов) ветвей перебора.
