Программирование на языке Пролог для искусственного интеллекта



              

Задача о ханойской башне



  Задача о ханойской башне



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

Применительно к нашей задаче это означает, что необходимо придерживаться следующей стратегии:

        Первой достигнуть цель "диск  с  - на колышек 3",
        а затем - все остальные.

Но первая цель не может быть достигнута сразу, так как в начальной ситуации диск  с   двигать нельзя. Следовательно, сначала мы должны подготовить этот ход, и наша стратегия принимает такой вид

    (1)        Обеспечить возможность перемещения диска  с  с 1 на 3.
    (2)        Переложить   с  с 1 на 3.
    (3)        Достигнуть остальные цели  (а  на 3 и  b  на 3).

Переложить  c  с 1 на 3 возможно только в том случае, если диск  а  и  b   оба надеты на колышек 2. Таким образом наша исходная задача перемещения  а,  b   и  с  с 1 на 3 сводится к следующим трем подзадачам:

Для того, чтобы переложить  a,  b   и  с  с 1 на 3, необходимо

    (1)        переложить   а  и  b  с 1 на 2,  и
    (2)        переложить   с  с 1 на 3,  и
    (1)        переложить   а  и  b  с 2 на 3.

Задача 2 тривиальна (она решается за один шаг). Остальные две подзадачи можно решать независимо от задачи 2, так как диски  а  и  b   можно двигать, не обращая внимание на положение диска  с.  Для решения задач 1 и 3 можно применить тот же самый принцип разбиения (на этот раз диск  b  будет самым "трудным"). В соответствии с этим принципом задача 1 сводится к трем тривиальным подзадачам:

Для того, чтобы переложить  а  и  b   с 1 на 2, необходимо:

    (1)        переложить   а  с 1 на 3, и
    (2)        переложить   b  с 1 на 2, и
    (1)        переложить   а  с 3 на 2.

    Формулировка игровых задач в терминах И / ИЛИ-графов
3.    Формулировка игровых задач в терминах И / ИЛИ-графов

Такие игры, как шахматы или шашки, естественно рассматривать как задачи, представленные И / ИЛИ-графами. Игры такого рода называются играми двух лиц с полной информацией. Будем считать, что существует только два возможных исхода игры: ВЫИГРЫШ и ПРОИГРЫШ. (Об играх с тремя возможными исходами -ВЫИГРЫШ, ПРОИГРЫШ и НИЧЬЯ, можно также говорить, что они имеют только два исхода: ВЫИГРЫШ и НЕВЫИГРЫШ). Так как участники игры ходят по очереди, мы имеем два вида позиций, в зависимости от того, чей ход. Давайте условимся называть участников игры "игрок" и "противник", тогда мы будем иметь следующие два вида позиций: позиция с ходом игрока ("позиция игрока") и позиция с ходом противника ("позиция противника"). Допустим также, что начальная позиция  Р  -   это позиция игрока. Каждый вариант хода игрока в этой позиции приводит к одной из позиций противника  Q1,  Q2,  Q3,   ...  (см. рис. 13.7). Далее каждый вариант хода противника в позиции  Q1  приводит к одной из позиций игрока  R11,  R12,   ... .  В  И / ИЛИ-дереве, показанном на рис. 13.7, вершины соответствуют позициям, а дуги - возможным ходам. Уровни позиций игрока чередуются в дереве с уровнями позиций противника. Для того, чтобы выиграть в позиции   Р,  нужно найти ход, переводящий  Р   в выигранную позицию  Qi.  (при некотором  i).  Таким образом, игрок выигрывает в позиции  Р,  если он выигрывает в  Q1,  или  Q2,   или  Q3,  или ... . Следовательно,  Р  - это ИЛИ-вершина. Для любого  i  позиция  Qi  -   это позиция противника, поэтому если в этой позиции выигрывает игрок, то он выигрывает и после каждого вариан-









Содержание  Назад  Вперед