Пример. Поиск в ширину

Задача построения слова из трех букв ТСА — это головоломка. Она решена, если получена одна из комбинаций «САТ» или «АСТ».

Для решения этой задачи используется простой поисковый алгоритм generate-and-test (генерация нового состояния из исходного и проверка — не получены ли целевые слова «САТ» или «АСТ»).

Поисковый алгоритм отстоит из двух шагов:

1. Сгенерировать новое состояние, модифицируя предыдущее - с помощью добавления только одной буквы.

2. Проверить, не является ли образовавшееся состояние конечным (целевым).

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