Рис. 25.2. Комбинаторный взрыв, происходящий с факториалами
Сейчас вы, возможно, думаете, что поиск решения в данном случае не представляет особого труда — надо лишь методично искать с самого начала и до конца. В этом крайне простом случае с потерянными ключами это не такой уж и плохой метод. Но в процессе поиска решения большинства задач складывается совсем другая ситуация. Обычно компьютер используется для решения задач, в которых количество вершин в области поиска очень большое, а по мере роста области поиска растет и число возможных путей к цели. Проблема состоит в том, что при добавлении новой вершины в области поиска появляется больше чем один новый путь. Значит, количество потенциальных цепочек, ведущих к решению (т.е. путей к цели), растет быстрее, чем количество вершин.
Например, проанализируем количество способов расположения трех объектов: А, Б и В. Вот шесть возможных перестановок:
А Б В А В Б Б В А Б А В В Б А В А Б
Вы можете легко убедиться, что это все перестановки множества из трех объектов А, Б и В. Однако чтобы подсчитать число перестановок, не обязательно выписывать их, достаточно вспомнить математику, точнее одну из первых теорем комбинаторики; в комбинаторике, как вы помните, изучаются конечные множества. В самом начале комбинаторики доказывается, что число перестановок множества из N элементов равняется N!(N факториал). Факториал числа — это произведение всех натуральных чисел, расположенных между самим этим числом и 1. Например, 3! равен 3 х 2 х 1, то есть 6. Число перестановок четырехэлементного множества равно 4!, т.е. 24. Для множества из пяти элементов это число равняется 120, а для множества из шести элементов — уже 720. Количество перестановок 1000 элементов равно:
4023872600770937735437024339230039857193748642107146325437999104\
2993851239862902059204420848696940480047998861019719605863\
1666872994808558901323829669944590997424504087073759918823\
6277271887325197795059509952761208749754624970436014182780\
9464649629105639388743788648733711918104582578364784997701\
2476632889835955735432513185323958463075557409114262417474\
3493475534286465766116677973966688202912073791438537195882\
4980812686783837455973174613608537953452422158659320192809\
0878297308431392844403281231558611036976801357304216168747\
6096758713483120254785893207671691324484262361314125087802\
0800026168315102734182797770478463586817016436502415369139\
8281264810213092761244896359928705114964975419909342221566\
8325720808213331861168115536158365469840467089756029009505\
3761647584772842188967964624494516076535340819890138544248\
7984959953319101723355556602139450399736280750137837615307\
1277619268490343526252000158885351473316117021039681759215\
1090778801939317811419454525722386554146106289218796022383\
8971476088506276862967146674697562911234082439208160153780\
8898939645182632436716167621791689097799119037540312746222\
8998800519544441428201218736174599264295658174662830295557\
0299024324153181617210465832036786906117260158783520751516\
2842255402651704833042261439742869330616908979684825901254\
5832716822645806652676995865268227280707578139185817888965\
2208164348344825993266043367660176999612831860788386150279\
4659551311565520360939881806121385586003014356945272242063\
4463179746059468257310379008402443243846565724501440282188\
5252470935190620929023136493273497565513958720559654228749\
7740114133469627154228458623773875382304838656889764619273\
8381490014076731044664025989949022222176590433990188601856\
6526485061799702356193897017860040811889729918311021171229\
8459016419210688843871218556461249607987229085192968193723\
8864261483965738229112312502418664935314397013742853192664\
9875337218940694281434118520158014123344828015051399694290\
1534830776445690990731524332782882698646027898643211390835\
0621709500259738986355427719674282224875758676575234422020\
7573630569498825087968928162753848863396909959826280956121\
4509948717012445164612603790293091208890869420285106401821\
5439945715680594187274899809425474217358240106367740459574\
1785160829230135358081840096996372524230560855903700624271\
2434169090041536901059339838357779394109700277534720000000\
0000000000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000000000000\
0000000000
Поистине колоссально!
|
График на рис. 25.2 дает возможность получить наглядное представление о том, что исследователи искусственного интеллекта называют комбинаторным взрывом. И как только количество объектов превысит какое-то сравнительно небольшое число, рост количества комбинаторных объектов (например, путей в графе), перебираемых в процессе решения, становится поистине неудержимым; трудности могут возникнуть даже не при проверке такого огромного количества объектов, а гораздо раньше — при пересчете. Ведь каждая дополнительная вершина в области поиска увеличивает число возможных решений не на 1, а на число, значительно большее 1. Поэтому после достижения некоторого критического количества объектов, добавление еще одного объекта к исходным данным, например, новой вершины, приводит к тому, что возможных "кандидатов в решение" становится так много, что проверить их за обозримое время практически невозможно. Именно из-за того, что количество возможностей растет столь быстро, лишь в самых простых задачах можно применять такую "роскошь", как исчерпывающий поиск. Исчерпывающим называется поиск, при котором проверяются все вершины; этот вид поиска можно считать приемом "грубой силы". Хотя прием "грубой силы" теоретически применим всегда, на практике он часто требует слишком много времени или слишком много компьютерных ресурсов, или того и другого вместе. Поэтому исследователи разработали другие методы поиска.