Искусственный интеллект

6.2.7. Сравнение стратегий поиска Характеристики шести рассмотренных стратегий, где / — степень ветвления, к — глубина поиска, d— максимальная глубина дерева поиска, г — ограничение на глубину поиска, сведены в табл. 6.2. Таблица 6.2 Критерии Поиск В ширину Монотонный в ширину В глубину Ограни-ченный в глубину Итера-тивный в глубину Двуна-правлен-ный Время р р t Р Память р р ? ^ Р Оптималь-ность Да Да Нет Нет Да Да Полнота Да Да Нет Да, если г ? к Да Да 145 6. Стратегии поиска 6.3. Направленный поиск Как было показано в предыдущем разделе, все стратегии слепого поиска обладают экспоненциальными оценками сложности по времени поиска, а некоторые и по памяти, и, вследствие этого, пригодны для решения сравнительно небольших задач. В стратегиях слепого поиска знания, используемые при выборе очередной вершины, определяют только общий порядок выбора и никак не учитывают качество выбора, например, по сложности поиска целевой вершины. В стратегиях направленного поиска знания, используемые для выбора очередной вершины, более глубокие и используют специальные функции, называемые критериями. Если для каждой вершины Ь, участвующей в поиске, критерий может быть вычислен, а множество всех вершин упорядочивается по этому критерию, то выбор очередной вершины производится в соответствии со значением этого критерия. Чем лучше значение критерия (например, выше или ниже), тем предпочтительнее выбор. Иными словами, из множества альтернативных вершин выбирается та, для которой критерий имеет наилучшее значение. Поэтому стратегии выбора подобного типа называются стратегиями выбора по наилучшему критерию. Критерии обычно выбираются таким образом, чтобы оптимизировать сложность поиска, найти оптимальное решение или достичь того и другого. В настоящем разделе рассмотрим некоторые стратегии направленного поиска, при котором используются дополнительные, знания о среде, позволяющие понизить сложность поиска. Рассмотрим, как осуществляется направленный поиск при решении оптимизационных задач.