Вы здесь : Главная

Эвристический поиск

Categories: | Author: Kirill Shurevich | Posted: 27.12.2009 | Views: 30266

В данной статье рассматриваются алгоритмы поиска A* , IDA*

Способы решения NP-полных задач

Демонстрационная программа IDA* PuzzleIDA_Star.rar
Демонстрационная программа A* PuzzleA_Star.rar

Источник SearchIDA.cs
Источник SearchBase.cs

Наиболее значимые проблемы , занимающие разработчиков ИИ, - это предсталение знаний и поиск решений.
Поиск – это метод решения проблемы , в котором просматривается пространство состояний задачи , т.е. альтернативных стадий для её решения и производится перебор в поиске окончательного ответа. Есть предположение что эта техника лежит в основе человеческого способа решения различных задач. Так например при игре в шахматы , шахматист анализирует возможные свои ходы и ответы противника , порой на несколько ходов вперёд , затем он выбирает на основании этого перебора свой ход , который с его точки зрения является наиболее удачным т.е. в конечном итоге приводящим к победе .
Исследования в области поиска производятся с давних времён , но сейчас с появлением компьютеров достаточной мощности мы можем визуально продемонстрировать работу некоторых из них .
Так в качестве примера задачи с которой мы будем исследовать алгоритмы поиска , мы возьмём задачу “15” или пятнашки . (см. Рис.1 с пояснением)
Представляет собой набор одинаковых квадратных костяшек с нанесёнными числами, заключённых в квадратную коробку. Длина стороны коробки в четыре раза больше длины стороны костяшек для набора из 15 элементов и в три раза больше для набора в 8 элементов, соответственно в коробке остаётся незаполненным одно квадратное поле. Цель игры — перемещая костяшки по коробке добиться упорядочивания их по номерам, желательно сделав как можно меньше перемещений.


Рис.1 Пятнашки в сборе

Стоит отмететь что настольные логические игры такие как шахматы , шашки , пятнашки - являются хорошим полем для исследования различных методик . Потому-что

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

Последний пункт особенно важен , как условие для исследования различных методик поиска в пространстве состояний .
Наша задача это рассмотреть различные варианты поиска кратчайшего пути к решению и выполнить программно два из самых популярных алгоритма: A* (читается как “А звёздочка”) и IDA* (читается как “итеррацинно заглубляющийся А звёздочка”).
Итак . Постановка задачи.

  1. Дано любое начальное состояние – A. (Рис.2)
  2. Есть правила, по которым мы можем изменять состояния, получая другие состояния. (Перемещение фишки на место пустышки)
  3. Есть конечное состояние – B. (Рис. 3)
  4. Требуется, применяя правила изменения состояния, найти кратчайший (оптимальный) путь из A в B.(Найти минимальное кол-во перемещений фишек )

Рис.2 – Начальное состояние Рис. 3 – целевое состояние

Данная задача имеет примерно 16!/2 = ~10.5 триллиона состояний , а если взять размерность 5 т.е. коробку с 24 фишками – то 10 в 25 степени , и т.д. .Прямой перебор всех возможных состояний , состовления из них путей и выбора минимального пути , может занять огромное время в зависимости от мощности компьютера (от дней до недель)
Так-же к примеру в шахматах возможно 10 в 120 степени возможных игровых путей , в шашках 10 в 40), прямой перебор в шахматах вообще не возможен , т.к. кол-во состояний сопоставимо с кол-вом молекул в исследованной вселенной.
В теории алгоритмов такие задачи наз-ся - NP-полные задачи - это задачи которые можно решить алгоритмом прямого перебора , но затраченное время при этом огромно ,не смотря ни накакие возможные усовершенствования компьютеров , так что гораздо разумнее и эффективнее заняться поиском достаточно точных приближенных алгоритмов для их решения.
Рассмотрим алгоритмы решений нашей задачи.
Для иллюстрации возьмём головоломку 8. Рис.4

Рис 4
На данном рисунке представлена 8-головоломка : её случайное начальное состояние , три возможных продолжения и целевое состояние.

Пример построений графа пространства состояний представлен на рисунке 5

Рис . 5 Данный рисунок представляет пример построения ориентированного графа

пространиства состояний 8-головоломки , каждое состояние – это узел графа , стрелки это дуги с направлением .
Итак , первый поиск который мы расмотрим это-
1. Поиск в ширину.
Начиная со начального состояния (узла), этот алгоритм сначала определяет все непосредственно соседние узлы, затем все узлы в двух шагах, затем в трех, и так далее, пока цель не достигнута.Такой поиск даёт оптимальное решение в случае его наличия. Но он даёт очень большое пространсво состояний.
Результат его работы представлен на рисунке 6

Рис. 6 Пример сгенерированного ориентированного графа пространства состояний при поиске в ширину , как видно построение графа будет завершено на 46 узле являющимся целевым состоянием , и путь это : 1,3,7,14,26,46

2. Поиск в глубину.
Этот поиск противоположен поиску в ширину. Вместо посещения вначале всех соседей, а потом их наследников, он сначала посещает всех наследников, а только затем переключается на соседей.
Результат его работы представлен на рисунке 7
На этом рисунке видно ,что мы ограничили глубину 5 уровнем , зная что решение находится на этом уровне , в действительности нам это неизвестно и это проблема поиска в глубину- выбор правильной глубины остановки. Если она будет слишком маленькой, то путь не будет найден; если слишком большой, то потенциально можно потратить много времени впустую, исследуя слишком глубоко, или найти путь не являющийся кратчайшим.

Рис. 7 Пример сгенерированного ориентированного графа пространства состояний при поиске в глубину ограниченный 5 уровнем , как видно построение графа будет завершено на 31 узле являющимся целевым состоянием , и путь это : 1,18,28,29,30,31

Итог:
Предидущие алгоритмы обладают следующими недостатками - или очень большим пространством поиска или неоптимальностью и негарантированностью результата.Алгоритмы которые решают эти проблемы это так называемые эвристические алгоритмы поиска.
Основа их это-. *Эвристика (греч. отыскиваю, открываю) — наука, изучающая творческую деятельность, методы, используемые в открытии нового и в обучении.
Эвристические методы (или Эвристики) которые позволяют ускорить процесс решения задачи.
Для начала рассмотрим ещё один метод поиска –это поиск экстремума.
Поиск по которому выбирается всегда только самое лучшее продолжение с точки зрения эвристической функции, или продолжение с минимальным отличием от цели (минимальной оценкой). Но опасность такого подхода заключается в том ,что мы можем остановится в точке так называемого локального максимума , т.е. когда все возможные продолжения являются ухудшающими (оценённые эвристической функцией как худшие) . Но цель( решение) не достигнуто. Пример такого локального максимума появляется в игре “15” . Часто для того , что-бы передвинуть фишку в нужную позицию , необходимо сдвинуть фишку находящуюся в наилучшей позиции.
Так как в этой стратегии данные о преидущих состояниях не сохраняются , то алгоритм не может быть востановлен из точки , которая привлекла к “неудачи” .
Методы поиска без механизма возврата , или других приёмов востановления не могут отличить локальный максимум от глобального.
Первый алгоритм который решает эту задачу а так-же значительно сужает пространство поиска и гарантирует оптимальный результат в случае его существования, это так называемый Алгоритм A* (алгоритм A звёздочка).

Эти проблемы решаются следующим алгоритмом.

3. Алгоритм А*
Этот эвристический поиск сортирует все узлы по приближению наилучшего маршрута, идущего через этот узел. Типичная формула эвристики выражается в виде:
f(n) = g(n) + h(n) где: f(n) функция оценки, назначенная узлу n
g(n) функция наименьшой стоимости прибытия в узел n из точки старта
и основная h(n) функция эвристической оценки стоимости пути к цели от узла n
Рассмотрим эффективность нескольких функций эвристической оценки для 8-головоломки.
Самая простая эвристика подсчитывает кол-во фишек стоящих не на своих местах.
Однако эта эвристика не использует всю имеющуюся информацию , например расстояния на которые фишки должны быть перемещены для достижения целевого (так называемое Манхеттенское расстояние).Но и эти две эвристики можно критиковать за то что они не учитывают трудности при перестановке фишек.
Эвристика принимающая во внимание и этот факт должна увеличивать эвристическое значение на малое число .
На Рис. 8 показан результат применения оценивающих функций.

Рис. 8

Но так-же следует помнить , если эвристика будет ошибочной если даст большую оценку нежели имеется на самом деле (т.е. недопустимой ), то алгоритм будет работать неправильно.
Так например в шахматах можно ввести следующую, на первый взгляд удачную эвристику – стараться как можно больше завладеть фигур противника и как можно больше сохранить своих фигур. Но , главная цель игры это поставить мат королю противника и известно множество эффектных побед именно благодаря так называемым “жертвам” качества. Т.е. данная эвристика потенциально способна упустить правильное решение.
Данные примеры показует насколько трудно найти хорошую эвристику.
Результат применения поиска по алгоритму A* с применеием допустимой эвристики
Манхеттенского расстояния представлен на рисунке 9.

Рис. 9 Пространство состояний , сгенерированное при эвристическом поиске на графе игры в “пятнашки” для 8-ми головоломки

Пример вычисления функции f(n) = g(n)+h(n) на графе пространства состояний., где h(n) - функция эвристической оценки- Манхеттенское расстояние “Сумма расстояний до целевого состояния для фишек находящихся не на своих местах”
Работа данного алгоритма может быть прелставлена следующим псевдокодом: Псевдокод алгоритма A*
 

Begin 
Open := [Start];
@инициализация
Closed := [];
While Open != [] do
Begin
Удалить первое состояние X из списка Open;
If X==goal , return путьот Start к X
Else
Begin
Сгенерировать потомок X;
For каждого потомка X do
Case
Потомок не содержится в списках Open и Closed
Begin
Присвоить потомку эвристическое значение;
Добавить потомок в список Open;
End;
Потомок уже содержится в списке Open;
If потомок был достигнут по кратчайшему пути
Then записать это состояние в список Open
Потомок уже содержится в списке Closed;
If потомок был достигнут по кратчайшему пути Then
Begin
Удалить состояние из списка Closed;
Добавить потомок в список Open
End;
End;
Поместить X в список Closed;
Переупорядочить состояния в списке Open в соответствии с эвристикой (лучшие слева)
End;
ReturnFAIL;
End.

Данный алгоритм поиска использует списки сохранённых состояний : Список Open отслеживает текущее состояние поиска , а в Closed записываются уже проверенные состояния . На рисунке 10 представлен вид списков Open и Closed после третьей итерации эвристического поиска.

Рис.10 Вид списков Open и Closed после третьей итерации эвристического поиска.
На каждом щаге алгоритм записывает в список Open состояние с учётом некоторой эвристической оценки h(n) , его близости к цели . Таким образом на каждой итерации расматриваются наиболее перспективные состояния из списка Open .

Каждое состояние сохраняет информацию о предшевствующем состоянии, что-бы в последствии востановить его и позволить алгоритму найти кратчайший путь к решению.
Если первый элемент в списке Open не является решением ,то алгоритм генерирует все возможные потомки данного элемента , если потомок уже находится в списке Open или Closed , то алгоритм выбирает кратчайший из двух возможных путей достижения этого состояния.Затем алгоритм вычисляет эвристическую оценку состояний в списке Open и сортирует спискок в соостветвии с этими эвристическими значениями . При этом “лучшие” состояния ставяться в начало списка .
A* имеет множество интересных свойств. Он гарантированно находит кратчайший путь, до тех пор пока эвристическое приближение h(n) является допустимым, то есть он никогда не превышает действительного оставшегося расстояния до цели. Этот алгоритм наилучшим образом использует эвристику: ни один другой алгоритм не раскроет меньшее число узлов, не учитывая узлов с одинаковой стоимостью.
Анализ псевдокода A* для программной реализации:
Для начало оценим времязатратные операции, которые нам надо реализовать для работы этого алгоритма.
Как видно из псевдокода A* это поиск, удаление и добавление элементов в списках Open и Closed а также поиск элемента с минимальной оценкой из списка Open.
Списки Open и Closed мы будем хранить в так называемых АВЛ деревьев (сбалансированное по высоте двоичное дерево поиска), дающих очень высокую скорость поиска ( - не более O(log(n)) для любого положения ) ,удаления и вставки элементов.
Но решив проблему скорости мы не в состоянии решить проблему потребляемой памяти , потому-что как уже отмечалось мы должны сохранять все состояния решения данной задачи , потреблённая память для хранения сотен миллионов состояний огромна и может превышать 1-2 gb. , поэтому в демонстрационной программе введено ограничение на работу данного алгоритма по памяти , если кол-во узлов графа привысит 10 милионов , он будет остановлен , для демонстрации без завершения по ограничению приложено несколько начальных состояний дающих приемлемое кол-во узлов.
(Показать работу программы.)
Для решения этой проблемы был предложен-
4. Алгоритм IDA*(Iterative deepening A*) - итеративного заглубления A*
Основная идея состоит в том что-бы отказаться от использования списков Open и Closed ,
и используя начальное состояние , строить рекурсивные деревья порождения новых , на основании лучшей оценки ,с возвратам по цепочки рекурсивных вложений назад , в случае попадания в локальный максимум , фиксирования этого состояния и поиска выхода методом перебора всех возможных продолжений до состояния с которого опять можно начинать поиск наилучших продолжений, и как только будет достигнута цель , то рекурсивная вложенность перемещений и будет путём к этой цели , а допустимая эвристика оценки будет гарантировать оптимальность данного решения.
Или-же данный алгоритм можно представить себе как исследования подобные поиску узла в ширину с серией поисков в глубину ограниченных допустимой эвристической оценкой.
Псевдокод данного алгоритма представлен .
Си-образный Псевдокод IDA* (вариант псведокода используемый в демонстрационной программе игры 15)
 

List solution = null;
state = start;
Move = null;
algorithmIterativeDeepening
{
    if (IsFinalPosition(state))return; //начальное состояние является целью 
    if (!DistributeStep(Move,true))//Выполнить все возможные изменения состояния
    {
        //Если при этом все возможные изменения состояния являются ухудшаюшими
        //То это означает что алгоритм попал в точку локального максимума (ЛМ)     
        _nStepDepth = 0; //установим относительную глубину для поиска выхода из ЛМ
        while (!DistributeStep(Move,false))
     _nStepDepth++;// выхода из ЛМ не найден , увеличим глубину
    }
    return;//цель найденна , путь хранится в списке solution
}
bool DistributeStep(Move,edge)
{
//Для каждого перемещения от текущего состояния
//Если перемещение возможно и не является возвратным то сделаем его
foreach Movei from state do
      if (DoMakeStep(Movei,edge))
      {
        //данное перемещение привело к цели или является перемещением ведущим к цели ,
        //=> является одним из шагов найденного пути,добавим это перемещение к нашему списку 
           solution.Add(Move);return true;
       }
       return false; //Если Все 4 перемещения или невозможны или ухудшают состояние
}
// Проверяет не является ли данное перемещение ухудшающим
bool IsGoodMove(Move,state)
{
    //использую наиболее популярную эвристическую оценочную функцию,например Манхэттана –
    //Проверим является ли данное перемещение улучшающим
    if(Move is good) return true;//перемещениеулучшающее
    elsereturnfalse;//перемещение не улучшающее
}
// Функция перемещения
bool DoMakeStep(Move,edge)
{
    if (IsFinalPosition(state+Move))return true;новоеположениеячейкиприводиткцели
    if (IsGoodMove(Move,state))
    {
        //если изменение состояние является улучшающим ,то продолжим поиск
        state = stateMove;
        else if (DistributeStep(Move,edge))
        {
            //Если данное перемещение привело к цели или является перемещением которое ведёт
            //к цели , т.е. является одним из шагов найденного пути , вернём истину 
            return true;
        }
        else//все возможные состояния ухудшающии
           return false;
    }
    else if (!edge)//Находимся ли мы в состоянии поиска выхода из локального максимума - ЛМ
    {
        //Данное перемещение неудачно ,но мы исчерпали все варианты удачных перемещений
        //поэтому делаем данное перемещение (на данном гаризонте мы ищем выход из ЛМ )
        state = stateMove;
        --_nStepDepth;//уменьшаем глубину горизонта поиска выхода из ЛМ
 //, в случае ,если она не отрицательна ,
        //мы будем изучать все возможные продолжения в поиске выхода из ЛМ
        if (_nStepDepth >= 0
            ? DistributeStep(state,false)
            : DistributeStep(state,true))
        {
            //данное перемещение привело к цели или является перемещением которое ведёт
            //к цели , т.е. является одним из шагов найденного пути , вернём истину 
            return true;
        }
        //преидущая глубина поиска выхода из локального экстремума
    //не дала результата , увеличим глубину
        ++_nStepDepth;
        return false;
    }
    else //Мы не находимся в состояния выхода из ЛМ ,а данное перемещение ухудшающее
        return false;
}

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

Заключение.
Из исследований решения для игры 15, итерационно углубляющийся алгоритм IDA* является самым быстрым с практически отсутствием потребления ресурсов памяти . Он гарантированно найдет самый короткий путь решения, также, как поиск в ширину . Его пространственная сложность растет только линейно с глубиной поиска.

Однако нельзя указать одинаково эффективный алгоритм для всех случаев , так классический алгоритм A* наилучшим способом использует эвристику и предоставляет больщие возможности для её реализации , даже в данном конкретном случае возможно нахождение более лучшей её реализация ,что может поменять ситуацию и A* станет более эффективным. Так-же нельзя сказать что IDA* является лучшей оптимизацией , в будущем возможно нахождение более совершенных алгоритмов.

Автор Статьи: Шуревич Кирилл .

Источники:

  1. Джордж Ф. Люгер Искусственный интеллект. Стратегии и методы решения сложных проблем
    1. George F. Luger Artificial Intelligence: Structures and Strategies for Complex Problem-Solving ?
  2. Дональд Кнут Искусство программирования, том 3. Сортировка и поиск
     
  3. "Complete Solution of the Eight-Puzzle and the Benefit of Node Ordering in IDA*", Alexander Reinefeld или 93ijcai.pdf
  4. Реализации на C++ http://www.codeguru.com/cpp/misc/samples/games/article.php/c13607/
  5. http://www.ic-net.or.jp/home/takaken/e/15pz/index.html

Полезное:
 

  1. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — М.: МЦНМО, 2001.
  2. NP-Полнота
    1. http://www.edu.yar.ru/russian/pedbank/sor_prof/bondarenko/chast1.html
    2. http://rain.ifmo.ru/cat/view.php/theory/algorithm-analysis/np-completeness-2004
    3. http://ru.wikipedia.org/wiki/NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0
    4. http://ru.wikipedia.org/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%81_P
  3. Алгоритм A*
    1. http://homepages.compuserve.de/chasluebeck/alg_1_10.htm
    2. http://algolist.manual.ru/games/smartmove.php
    3. http://pmg.org.ru/ai/stout.htm
    4. http://en.wikipedia.org/wiki/A*
  4. Кук С.А. Сложность процедур вывода теорем. - Кибернетический сборник, новая серия.- 1975.- Вып.12.- С.5-15.
  5. Карп Р.М. Сводимость комбинаторных проблем.- Там же. С.16-38.
  6. Левин Л.А. Универсальные задачи перебора.- Проблемы передачи информации.- 1973.- Т.9, N 3.- С.115-116.
  7. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи.- М.:Мир.- 1982.- 416 с.
  8. Бинарные деревья (АВЛ Tree, Красно-чёрные деревья,…)
    1. http://ru.wikipedia.org/wiki/%D0%90%D0%92%D0%9B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE
    2. http://www.rsdn.ru/article/alg/bintree/avl.xml
    3. http://www.nist.gov/dads/HTML/avltree.html
    4. http://www.stanford.edu/~blp/avl/libavl.html/
    5. http://www.codeproject.com/KB/recipes/redblackcs.aspx  
Bookmark and Share

Возврат
Яндекс.Метрика