ВУЗ:
Составители:
Рубрика:
69
поиска в глубину и в ширину недостаточно «умны» для борьбы с такой
ситуацией, так как все пути рассматриваются как одинаково перспективные.
По-видимому, процедуры поиска должны использовать какую-либо
информацию, отражающую специфику данной задачи, с тем, чтобы на
каждой стадии поиска принимать решения о наиболее перспективных путях
поиска. В результате
процесс будет продвигаться к целевой вершине, обходя
бесполезные пути. Информация, относящаяся к конкретной решаемой задаче
и используемая для управления поиском, называется эвристикой. Алгоритмы
поиска, использующие эвристики, называют эвристическими алгоритмами.
Одним из эвристических алгоритмов решения задач является алгоритм
А*, который является усовершенствованным алгоритмом поиска в ширину.
Это, так называемый, алгоритм поиска
по заданному критерию. Для каждого
возможного перехода за один шаг определяется эвристическая оценка и для
продолжения поиска решающего пути выбирается наилучшая в соответствии
с данной оценкой вершина.
Предполагается, что для всех дуг в пространстве состояний определена
функция стоимости перемещения от вершины к вершинам-преемникам.
Допустим, для эвристической оценки применяется функция f(n)
такая, что
для каждой вершины n она служит для оценки «сложности достижения n».
Соответственно наиболее перспективной является та вершина, для которой
значение функции f(n) является минимальным. Рассмотрим алгоритм А* на
примере решения задачи «игра в восемь».
На следующем рисунке представлена задача «игра в восемь» в виде
задачи поиска пути в пространстве
состояний. В головоломке используется
восемь перемещаемых фишек, пронумерованных цифрами от 1 до 8. Фишки
располагаются в девяти ячейках, образующих матрицу 3х3. Одна из ячеек
всегда пуста, любая смежная с ней фишка может быть передвинута в эту
ячейку. Конечная ситуация – это некоторая заранее заданная конфигурация
фишек.
Страницы
- « первая
- ‹ предыдущая
- …
- 67
- 68
- 69
- 70
- 71
- …
- следующая ›
- последняя »
