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

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