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




Задача о ханойской башне - часть 2


        Первой достигнуть цель "диск  с  - на колышек 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.




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