,ВЫ можете быстро проверить, что эти шесть и есть единственно возможные ,сомбинации объектов А, В и С. Это же число можно получить, воспользовавшись теоремой из раздела математики, именуемого комбинаторикой и изучающего способы комбинирования объектов. Возвращаясь к теореме, число возможных комбинаций N объектов равно N! (N факториал). Факториал числа равен произведению следующих целых чисел: числа, равного N, Л затем всех целых чисел, меньших N, вплоть до единицы. Следовательно, 3! равно 3x2x1 или 6. Если у вас четыре объекта, то число их комбинаций равно 4! или 24. Для пяти объектов оно равно 120, а для шести - 720. Для 1000 объектов число возможных перестановок огромно! График на рис. 7.3 дает наглядное представление о том, что иногда называют комбинаторным взрывом. Как только вариантов становится больше, чем пальцев на руке, проверка (а на практике и просто подсчет) всех их комбинаций очень быстро превращается в трудное занятие.

Этот вид комбинаторного взрыва может проявиться и при поиске путей в пространствах поиска. Только простейшие задачи позволяют провести исчерпывающий поиск (exhaustive search). Исчерпывающий поиск означает полный перебор всех узлов. Следовательно, это способ решения в лоб . Подобный метод работает всегда, но он не применяется при решении задач большого объема, так как потребляет слишком много времени или вычислительных ресурсов, а иногда и того, и другого вместе. Именно поэтому были разработаны методы с использованием искусственного интеллекта.

Методы поиска

Существует несколько способов поиска решения. Перечислим четыре основных:

□ поиск в глубину (depth first); О поиск в ширину (breadth first);

О метод восхождения на гору или поиска экстремума (hill-climbing);

О метод наименьшей стоимости (least cost).

Далее мы обсудим каждый из методов поиска более подробно.

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

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

Как быстро найдено решение? Насколько удачно это решение?

250 Гоаеа?

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

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

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

Постановка задачи

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

Таблица 7.2. Расписание рейсов компании XYZ

Рейс Расстояние

Нью-Йорк - Чикаго 900 миль

Чикаго - Денвер 10ОО миль

Нью-Йорк - Торонто 500 миль

Нью-Йорк - Денвер 1800 миль

Торонто - Калгари 1700 миль

Таблица 7.2 (окончание)

рейс

Торонто - Лос-Анджелес Торонто - Чикаго Денвер-Эрбана Денвер - Хьюстон Хьюстон - Лос-Анджелес Денвер - Лос-Анджелес

Расстояние

2500 миль 500 миль 1000 миль 1000 миль 1500 миль 1000 миль

Вы сразу увидите, что ваш клиент может долететь из Нью-Йорка в Лос-Анджелес с пересадками. Задача заключается в том, чтобы программы, написанные на С++, выполняли действия, которые вы проделали мысленно!

Графическое представление

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

1*ис. 7.4. Направленный граф, отображающий расписание полетов компании XYZ