Гпавау

flights[i].to == f.to) flights[i].skip = false;

Для тестирования поиска в ширину замените функцию findrouteO в листинге 7.1 и добавьте функцию resetskipo. Далее приведен вывод решения, найденного программой поиска в ширину.

From? New York То? Los Angeles

New York to Toronto to Los Angeles Distance is 3000

Анализ поиска в ширину

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

Денвер (Лос-Анджелес) Чикаго Калгари Лос-Анджелес Первое решение

Лос-Анджелес Хьюстон Эрбана

▼

Лос-Анджелес

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

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

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

Эвристические возможности

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

Эвристика - это набор правил, которые увеличивают вероятность того, что поиск движется в нужном направлении. Представьте, что вы заблудились в лесу и вас мучит жажда. Лес настолько густой, что не видно просвета, а деревья слишком большие для того, чтобы залезть на них и осмотреться. Но вы знаете, что реки, ручьи и пруды вероятнее всего находятся в низинах, что звери часто прокладывают пути к водопою, что, находясь недалеко от воды, можно ее найти по запаху или услышать ее шум. Итак, вы начинаете двигаться к подножью холма, потому что вода вряд ли будет на вершине. Далее вы наталкиваетесь на оленью тропу, которая тоже ведет к подножью. Зная, что она может привести к воде, вы идете по этой тропе. Затем вы начинаете различать слева легкое журчание. Полагая, что это может быть шум воды, вы движетесь в этом направлении. По мере движения вы начинаете ощущать увеличение влажности воздуха и запах воды. В конце концов, вы находите ручей и утоляете жажду. В этой ситуации эвристическая информация, используемая для поиска воды, не гарантировала удачи, но действительно увеличивала вероятность быстрого достижения успеха. Обычно эвристика повышает шансы быстрого обнаружения цели.

Чаще всего методы эвристического поиска основываются на максимизации Или минимизации некоторого ограничивающего условия. В задаче формирования маршрута из Нью-Йорка в Лос-Анджелес есть два возможных параметра, которые пассажир захочет свести к минимуму: во-первых, количество необходимых пересадок и, во-вторых, длина маршрута. Основой обоих описываемых далее эвристических вариантов поиска служит поиск в глубину.

272 rjay

Поиск методом восхождения на гору

Алгоритм поиска, который пытается найти маршрут с минимальным числом пересадок, использует эвристику, утверждающую, что чем больше длина очередного рейса, тем выше вероятность того, что пассажир стал ближе к пункту назначения; следовательно, количество пересадок минимизируется. На языке искусственного интеллекта это пример поиска экстремума (НЩ climbing).

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

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

Версия поиска методом восхождения на гору .

При заданном from находит самый длинный рейс.

Возврашает true, если он найден,

и false - в противном случае.

bool Search::find(string from, Flightlnfo &f)

int pos = -1; int dist = 0;

for(unsighed i=0; i < flights.size(); i++) {

if(flights[i].from == from && !flights[i].skip) { Использует самый длинный рейс, if(flights[i].distance > dist) { pos = i;

dist = flights[i].distance;

if(pos != -1) {