Задача о словесной лестнице

В начале изучения алгоритмов для графов, давайте рассмотрим следующую головоломку, которая называется “словесная лестница”. Требуется преобразовать слово “FOOL” в слово “SAGE”. Изменения должны происходить постепенно, по букве за раз. На каждом шаге вы должны трансформировать слово в другое слово, а не в бессмыслицу. “Словесная лестница” была изобретена в 1878 году Льюисом Кэрролом - автором Алисы в Стране Чудес. Следующая последовательность слов показывает одно из возможных решений поставленной выше задачи.

FOOL
POOL
POLL
POLE
PALE
SALE
SAGE

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

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

Next Section - Построение графа для “словесной лестницы”