Re: Very close.

> А ведь эти персональные параллельные архитектуры адресуют ахиллесову пяту всех искусственноинтеллектуальных методов: слишком долгий счет. Увы, экспоненциально долгий. Но ведь и в начале экспоненты можно неплохо поразвлекаться. Полного перебора стараются избежать. И не мудрено, самый мощный петафлопный компьютер на Земле делает за год 365*24*3600*10^15 ~ 32*10^21 ~ 2^75 операций. Т.е. он за год "перебирает" пространство размером 75 бит :). Негусто. К счастью, многие практические задачи все же обычно решаются гораздо быстрее, но не гарантировано. Т.е. worst-time конечно экспонента. Например, современные алгоритмы позволяют решать SAT проблемы (выполнимость булевских формул в конъюктивной нормальной форме) размеров в миллионы переменных и подформул. Проблематика там примерно такая. Во многих случаях, зная значения некоторых переменных, можно вывести значения других без перебора. К примеру, если есть ограничение a|b|c= true, где а,b,c - булевы переменные, и если известно, что a=b=false, то из этого автоматом следует, что с = true. Это называется Unit Propagation. На практике, если таковых ограничений много, то один Unit Propagation может породить целую цепочку других таких Unit propagation'ов. Т.е. если правильно выбирать множество переменных для перебора, то можно перебор существенно сократить. К сожалению, заранее выбрать такие переменные в общем случае нельзя, нужно использовать эвристики. Также если выяснилось, что некоторые назначения переменных ведут к конфликтам, то можно эти комбинации запомнить и "вычеркнуть" из пространства поиска. К примеру, есть формулы a|b|c & ~c|d|e. Если a=b=d=e=false, то формула противоречива, т.е. из a|b|c следует что c=true, а из ~c|d|e - что с = false. Таким образом, компьютеры может выучить новую формулу, что a,b,d,e не могут быть false одновременно (a|b|d|e = true), и в дальнейшем выбора таких значений избегать. Это называется Learning, а выведенное утверждение - Лемма. Таким образом, чтобы это все дело эффективно распараллелить, параллельные потоки должны уметь обмениваться Леммами, а также нужно динамически распределять между ними пространство перебора. На GPU это пока плохо ложиться, ибо GPU расчитан на планомерное перепахивание более-менее однородных структур данных, а не на "шизофренические" метания, характерные для алгоритмов ИИ.