|
Журнал «Компьютерра» 2007 № 27-28 (695-696) 24 июля 2007 годаПростые, можно даже сказать, элегантные правила вершина айсберга. В глубине сложная математическая теория. Поэтому нет ничего удивительного, что игрой заинтересовались ученые. Наверное, несчастный кладовщик Вася очень бы удивился, если б узнал, что его действия можно изучать с точки зрения теории вычислительной сложности. Задача решения этой головоломки относится к так называемым NP-трудным задачам, как часть более общего класса задач планирования движения (в общем случае Вася будет иметь право не только толкать, но и тянуть, и не один, а сразу несколько ящиков). Сокобан представляет интерес и для исследователей искусственного интеллекта: хорошо бы построить такого робота, который выполнял бы задачу Васи и, перемещая ящики по лабиринту, ставил их на определенные места. При этом нужно, чтобы он выполнял свою задачу в оптимально короткие сроки за минимальное количество шагов. Трудность прохождения сокобана заключается не только в уровне ветвления дерева вариантов ходов (многие исследователи сравнивают эту игру по сложности с шахматами), но и в огромной глубине поиска по этому дереву ...» |
Код для вставки книги в блог HTML
phpBB
текст
|
|