Оценка производительности поиска, основанного на методах искусственного интеллекта, может оказаться сложной. К счастью, в этой главе нас ин-^Ресуют только два показателя. ^ Как быстро найдено решение? ^ Насколько удачно это решение?
ч0Ы можете быстро проверить, что эти шесть и есть единственно возможные комбинации объектов А, В и С. Это же число можно получить, воспользовавшись теоремой из раздела математики, именуемого комбинаторикой и изучающего способы комбинирования объектов. Возвращаясь к теореме, число возможных комбинаций N объектов равно N! (N факториал). Факториал числа равен произведению следующих целых чисел: числа, равного N, и затем всех целых чисел, меньших N, вплоть до единицы. Следовательно, 3! равно 3x2x1 или 6. Если у вас четыре объекта, то число их комбинаций равно 4! или 24. Для пяти объектов оно равно 120, а для шести — 720. Для 1000 объектов число возможных перестановок огромно! График на рис. 7.3 дает наглядное представление о том, что иногда называют комбинаторным взрывом. Как только вариантов становится больше, чем пальцев на руке, проверка (а на практике и просто подсчет) всех их комбинаций очень быстро превращается в трудное занятие.
Этот вид комбинаторного взрыва может проявиться и при поиске путей в пространствах поиска. Только простейшие задачи позволяют провести исчерпывающий поиск (exhaustive search). Исчерпывающий поиск означает полный перебор всех узлов. Следовательно, это способ решения "в лоб". Подобный метод работает всегда, но он не применяется при решении задач большого объема, так как потребляет слишком много времени или вычислительных ресурсов, а иногда и того, и другого вместе. Именно поэтому были разработаны методы с использованием искусственного интеллекта.
|
