Комбинаторные взрывы

Содержание

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

Например, проанализируем количество способов расположения трех объектов: А, Б и В. Вот шесть возможных перестановок:

А     Б     В
А     В     Б
Б     В     А
Б     А     В
В     Б     А
В     А     Б

Вы можете легко убедиться, что это все перестановки множества из трех объектов А, Б и В. Однако чтобы подсчитать число перестановок, не обязательно выписывать их, достаточно вспомнить математику, точнее одну из первых теорем комбинаторики; в комбинаторике, как вы помните, изучаются конечные множества. В самом начале комбинаторики доказывается, что число перестановок множества из 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. Комбинаторный взрыв, происходящий с факториалами

График на рис. 25.2 дает возможность получить наглядное представление о том, что исследователи искусственного интеллекта называют комбинаторным взрывом. И как только количество объектов превысит какое-то сравнительно небольшое число, рост количества комбинаторных объектов (например, путей в графе), перебираемых в процессе решения, становится поистине неудержимым; трудности могут возникнуть даже не при проверке такого огромного количества объектов, а гораздо раньше — при пересчете. Ведь каждая дополнительная вершина в области поиска увеличивает число возможных решений не на 1, а на число, значительно большее 1. Поэтому после достижения некоторого критического количества объектов, добавление еще одного объекта к исходным данным, например, новой вершины, приводит к тому, что возможных «кандидатов в решение» становится так много, что проверить их за обозримое время практически невозможно. Именно из-за того, что количество возможностей растет столь быстро, лишь в самых простых задачах можно применять такую «роскошь», как исчерпывающий поиск. Исчерпывающим называется поиск, при котором проверяются все вершины; этот вид поиска можно считать приемом «грубой силы». Хотя прием «грубой силы» теоретически применим всегда, на практике он часто требует слишком много времени или слишком много компьютерных ресурсов, или того и другого вместе. Поэтому исследователи разработали другие методы поиска.