Пример. Метод поиска решения «в глубину»

АЛГОРИТМ (обозначения)

dfs (goal, current, pending) – функция трех аргументов

goal – объект поиска (цель)

current – текущий узел на графе, в самом начале узел исходного состояния (одна буква)

pending – список узлов, претендующих на обработку (в самом начале пустой)

ОБОЗНАЧЕНИЯ:

• Символ «:=» – присвоение;
• Функция “ expand ” формирует узлы, следующие за аргументом этой функции;
• Знак «+» – слияние двух списков, т.е.;
  (abc)+(def)=(abcdef);
• () – означает пустой список;
• first и rest – функции, выделяющие начало и оставшуюся часть списка;
  first(abc)=a
  rest(abc)=(bc).

АЛГОРИТМ

Dfs(goal, current, pending)

{

if current=goal, then succes;

Else

{

pending:=expand(current)+pending;

if pending=() then fail;

else dfs(goal, first(pending), rest(pending));

}

}

ЗАДАНИЕ 1. Найти все «производные» слова от слова AEROPORT (язык русский, алфавит латинский)

Вариант 1: goal = RAPORT

Вариант 2: goal = (ORT ROT PAT PORT TORT RAPORT AEROPORT)

Критерий выч. затрат – число шагов на графе.

ЗАДАНИЕ 2. Разработать аналогичный алгоритм для поиска в ширину.

Указание: нужно изменить только одно выражение в функции dfs.

Рассмотрим процесс поиска на конкретном примере. Пусть имеем карту дорог (рис. 2), по которой мы хотим изучить маршрут движения из одного конкретного города в другой.

Система, построенная на основе знаний об этой карте дорог, должна поработать с картой и спланировать наше путешествие, например из города «А» в город «F».

При решении представленной задачи компьютер преобразует исходную карту и представит ее в виде дерева поиска, которое без учета циклов будет иметь вид рис. 3.

Рис. 2. Карта дорог

Дерево поиска показывает все возможные варианты выбора при движении из «А» (начальное состояние), а также и все варианты выбора в каждом из промежуточных пунктов (состояний).

Место, откуда начинается поиск, находится в вершине дерева поиска.

Все дороги, начинаясь в «А», либо приводят в тупик, либо заканчиваются в «F».

Рис.3. Дерево поиска

Задача компьютера состоит в том, чтобы найти подходящую дорогу из вершины дерева к конечному состоянию (цели) в его нижней части.

Человек при взгляде на дерево поиска сразу же выберет подходящую дорогу, но компьютер на это не способен. Какую стратегию поиска применит компьютер?

Рассмотрим пример, который заставит нас думать как компьютер.

Мы находимся в темной комнате, на стене которой дерево поиска, а у нас фонарик, который освещает всего два соседних пункта.

Нам известно, где расположена вершина дерева, откуда надо начать поиск. Как наиболее эффективно перемещать луч фонарика, чтобы найти маршрут до «F»?

При отсутствии какой-либо дополнительной информации компьютер для поиска использует стратегию «грубой силы». При этом программа поиска осуществляет поиск цели, идя от состояния к состоянию, и систематически исследуя все возможные пути.

Для определения каждого последующего шага применяется некая простая механическая стратегия, которая имеет две разновидности: поиск в глубину и поиск в ширину.