Назад | Содержание| Вперёд 11. 4. Замечания относительно поиска вграфах, оп...

порожденное программой поиска в ширину.

длин - самые короткие решения идут первыми. Этоявляется важным обстоятельством, если намнеобходима оптимальность (в отношении длинырешения). Стратегия поиска в ширину гарантируетполучение кратчайшего решения первым.Разумеется, это неверно для поиска в глубину.

Наши программы, однако, не учитывают стоимости,приписанные дугам в пространстве состояний. Есликритерием оптимальности является минимумстоимости решающего пути (а не его длина), то вэтом случае поиска в ширину недостаточно. Поиск спредпочтением из гл. 12 будет направлен наоптимизацию стоимости.

Еще одна типичная проблема, связаннаяс задачей поиска, - это проблема комбинаторнойсложности. Для нетривиальных предметныхобластей число альтернатив столь велико, чтопроблема сложности часто принимает критическийхарактер. Легко понять, почему это происходит:если каждая вершина имеет  b  преемников, точисло путей длины  l,  ведущих из стартовойвершины, равно  b^l  ( в предположении,что циклов нет). Таким образом, вместе сувеличением длин путей наблюдается экспоненциальныйрост объема множествапутей-кандидатов, что приводит к ситуации,называемой комбинаторным взрывом.Стратегии поиска в глубину и ширину недостаточно"умны" для борьбы с такой степеньюкомбинаторной сложности: отсутствиеселективности приводит к тому, что все путирассматриваются как одинаково перспективные.

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

Резюме

Пространство состояний есть формализм для представления задач.

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

Оптимизационные задачи моделируются приписыванием каждой дуге пространства состояний некоторой стоимости.

Имеются две основных стратегии поиска в пространстве состояний - поиск в глубину и поиск в ширину.

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

Реализация поиска в ширину более сложна, поскольку требуется сохранять множество кандидатов. Это множество может быть с легкостью представлено списком списков, но более экономное представление - в виде дерева.

Поиск в ширину всегда первым обнаруживает самое короткое решение, что не верно в отношении стратегии поиска в глубину.

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

В этой главе были введены следующие понятия: