Информатика в играх и задачах. 4 класс. В 2-х частях. Часть 1

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