Приложение: Описание проблем

I. Проблема Ханойской башни

Материал состоит из определенного числа дисков разных размеров (как правило, от трех до шести) и трех местоположений, отмеченных разными цветами, которые мы назовем А, В и С. Иногда используются диски с дырочкой посередине, и их можно надеть на три стержня, зафиксированных на планшетке.

<РИСУНОК В ЭЛЕКТРОННОМ ВИДЕ ОТСУТСТВУЕТ>

Рис. I. Пространство поиска для проблемы Ханойской башни из трех дисков.

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

При перемещении дисков необходимо соблюдать следующие запреты:

§   одновременно нельзя перемещать более одного диска;

§   можно перемещать только диск, находящийся сверху;

§   нельзя класть один диск на другой, меньшего размера;

В случае трех дисков эти запреты порождают пространство поиска (или пространство задачи), представленное на рис. 1. Там описаны разные состояния проблемы и возможные переходы между этими со-стояниями.