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

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

FOOL
POOL
POLL
POLE
PALE
SALE
SAGE

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

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

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