Содержание | <<< | >>>

Оценка поиска

Иногда бывает очень сложно оценить, насколько эффективен метод поиска. Фактически оценка методов поиска и составляет значительную часть искусственного интеллекта. Впрочем, для нас наиболее важными являются два критерия: 1) насколько быстро при поиске находится решение; 2) насколько хорошим является найденное решение.

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

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

Необходимо понимать разницу между нахождением хорошего и оптимального решения. Чтобы найти оптимальное решение, может потребоваться исчерпывающий поиск, так как иногда именно он является единственным способом проверки того, что было найдено наилучшее решение. А найти хорошее решение — это означает найти такое решение, которое удовлетворяет набору ограничений; при этом не важно, имеется ли решение, которое еще лучше.

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

Теперь давайте проанализируем задачу, для решения которой воспользуемся разными методами поиска. Представьте, что вы транспортный агент, а какой-то довольно придирчивый клиент хочет заказать у вас билет от Нью-Йорка до Лос-Анджелеса, причем на самолет именно компании XYZ Airlines. Вы пытаетесь объяснить клиенту, что у этой компании беспересадочных авиарейсов из Нью-Йорка в Лос-Анджелес нет, но он хочет лететь только на самолетах компании XYZ Airlines. Самолеты компании XYZ Airlines по расписанию совершают следующие авиарейсы:

АвиарейсРасстояние, в милях
Нью-Йорк — Чикаго1000
Чикаго — Денвер1000
Нью-Йорк — Торонто800
Нью-Йорк — Денвер1900
Торонто — Калгари1500
Торонто — Лос-Анджелес1800
Торонто — Чикаго500
Денвер — Урбана1000
Денвер — Хьюстон1500
Хьюстон — Лос-Анджелес1500
Денвер — Лос-Анджелес1000

Вы быстро понимаете, что из Нью-Йорка в Лос-Анджелес добраться самолетами компании XYZ Airlines можно только в том случае, если заказать билеты на несколько промежуточных авиарейсов, что вы и делаете.

Ваша задача состоит в том, чтобы написать несколько С-программ, которые будут выбирать маршрут лучше, чем это получается у вас.


Содержание | <<< | >>>