Существует несколько способов поиска решения. Перечислим четыре основных:
? поиск в глубину (depth first); О поиск в ширину (breadth first);
О метод "восхождения на гору" или поиска экстремума (hill-climbing);
О метод наименьшей стоимости (least cost).
Далее мы обсудим каждый из методов поиска более подробно.
Существует ряд задач, для которых достаточно просто найти решение, лю„ бое, потребовавшее минимума усилий. Для таких задач особенно существен первый показатель. В других ситуациях качество решения гораздо важнее. На скорость поиска оказывает влияние как размер пространства поиска, так и количество узлов, действительно пройденных в процессе поиска решения Поскольку возврат из тупиков — напрасно затраченное усилие, хотелось бы в ходе поиска как можно реже повторять эти шаги.
При поиске, основанном на методах искусственного интеллекта, есть раз-ница между лучшим и приемлемым решением. Получение лучшего решения (best solution) может потребовать исчерпывающего поиска, так как иногда это единственный путь для того, чтобы выяснить, что найдено лучшее решение. Поиск приемлемого решения (good solution) означает получение решения, лежащего в пределах заданных ограничений, при этом возможное существование лучшего решения не имеет значения.
Как вы увидите, методы поиска, описанные в этой главе, в одних ситуациях действуют лучше, чем в других. Трудно утверждать, что один способ поиска всегда предпочтительней остальных, но некоторые методы с большей вероятностью могут быть лучше в среднем. Кроме того, способ описания задачи иногда помогает выбрать подходящий способ поиска.
Постановка задачи
Рассмотрим задачу, для решения которой мы будем использовать разные методы поиска. Допустим, что вы — агент бюро путешествий, и довольно придирчивый клиент хочет заказать вам билет компании XYZ из Нью-Йорка в Лос-Анджелес. Вы пытаетесь объяснить, что XYZ не выполняет прямых рейсов из Нью-Йорка в Лос-Анджелес, но клиент настаивает и уверяет, что полетит только самолетом этой компании. Таким образом, вы вынуждены выбрать маршрут с пересадками между Нью-Йорком и Лос-Анджелесом и просматриваете расписание рейсов компании XYZ, приведенное в табл. 7.2.
Вы сразу увидите, что ваш клиент может долететь из Нью-Йорка в Лос-Анджелес с пересадками. Задача заключается в том, чтобы программы, написанные на С++, выполняли действия, которые вы проделали мысленно!
|
