Иногда бывает очень сложно оценить, насколько эффективен метод поиска. Фактически оценка методов поиска и составляет значительную часть искусственного интеллекта. Впрочем, для нас наиболее важными являются два критерия: 1) насколько быстро при поиске находится решение; 2) насколько хорошим является найденное решение.
Имеется несколько видов задач, в процессе решения которых особенно важным является первый из двух критериев, т.е. главным аспектом здесь является то, чтобы решение, возможно, даже любое из решений, было найдено с минимальными усилиями. Однако в других ситуациях решение обязательно должно быть хорошим, возможно, даже оптимальным.
Быстрота поиска определяется как длиной пути решения, так и количеством вершин, через которые фактически приходится пройти в процессе поиска решения. Следует помнить, что при возврате из тупика усилия на самом деле оказываются потраченными впустую. Поэтому необходимо выработать такую стратегию поиска, благодаря которой к минимуму сводится возможность попадания в тупик.
Необходимо понимать разницу между нахождением хорошего и оптимального решения. Чтобы найти оптимальное решение, может потребоваться исчерпывающий поиск, так как иногда именно он является единственным способом проверки того, что было найдено наилучшее решение. А найти хорошее решение — это означает найти такое решение, которое удовлетворяет набору ограничений; при этом не важно, имеется ли решение, которое еще лучше.
Как будет видно из дальнейшего изложения, методы поиска, описанные в этой главе, не во всех ситуациях работают одинаково хорошо. Поэтому трудно сказать, всегда ли какой-либо метод лучше другого. Впрочем, «в среднем» некоторые методы, будут более приемлемыми, чем остальные. Кроме того, иногда сам способ постановки задачи подсказывает подходящий метод поиска.
Теперь давайте проанализируем задачу, для решения которой воспользуемся разными методами поиска. Представьте, что вы транспортный агент, а какой-то довольно придирчивый клиент хочет заказать у вас билет от Нью-Йорка до Лос-Анджелеса, причем на самолет именно компании XYZ Airlines. Вы пытаетесь объяснить клиенту, что у этой компании беспересадочных авиарейсов из Нью-Йорка в Лос-Анджелес нет, но он хочет лететь только на самолетах компании XYZ Airlines. Самолеты компании XYZ Airlines по расписанию совершают следующие авиарейсы:
| Авиарейс | Расстояние, в милях |
|---|---|
| Нью-Йорк — Чикаго | 1000 |
| Чикаго — Денвер | 1000 |
| Нью-Йорк — Торонто | 800 |
| Нью-Йорк — Денвер | 1900 |
| Торонто — Калгари | 1500 |
| Торонто — Лос-Анджелес | 1800 |
| Торонто — Чикаго | 500 |
| Денвер — Урбана | 1000 |
| Денвер — Хьюстон | 1500 |
| Хьюстон — Лос-Анджелес | 1500 |
| Денвер — Лос-Анджелес | 1000 |
Вы быстро понимаете, что из Нью-Йорка в Лос-Анджелес добраться самолетами компании XYZ Airlines можно только в том случае, если заказать билеты на несколько промежуточных авиарейсов, что вы и делаете.
Ваша задача состоит в том, чтобы написать несколько С-программ, которые будут выбирать маршрут лучше, чем это получается у вас.