 |
|
Недетерминированность выводов. Средства, используемые в системах, обладающих этим свойством.
Наиболее распространенным способом учета недетерминированности вывода является метод перебора с возвратами, называемый также методом проб и ошибок.
Суть данного метода заключается в следующем (рис.3.1). Все пространство поиска можно представить в виде дерева, узлами которого являются частичные или итоговые решения задачи (необязательно верные). По мере поиска решения, удовлетворяющего условиям (требованиям, ограничениям), постепенно строится это дерево (выполняется обход узлов). Если в листьях (узлах последнего уровня) решение удовлетворяет требуемым условиям, то оно и есть результат поиска. В общем случае, решений может быть несколько (узлы 4 и 5). Если при обходе дерева система попадает в узел, решение в котором не удовлетворяет (противоречит) условиям задачи, тогда система возвращается к предыдущему узлу и продолжает поиск в альтернативном направлении.
Рис.3.1. Обход дерева при поиске решения
Условные обозначения:
- направление поиска из узлов, решение в которых удовлетворяет условиям;
- направление поиска из узлов, решение в которых не удовлетворяет условиям;
- маршрут обхода узлов;
- узел, в котором проверялись условия. Рядом с узлом стоит «И», если решение в нем удовлетворяет условиям, в противном случае стоит «Л»;
- узел, непопавший в маршрут обхода.
Описанный способ поиска решений используется в Prolog. В частном случае обход дерева может быть прерван при нахождении первого верного решения.
Ограничением использования метода является монотонность выводов. Т.е. если в каком-либо узле проверяемое условие ложно, то в узле следующего уровня оно не может стать истинным. Очевидно, что при большом количестве проверяемых условий и направлений поиска данный метод малоэффективен.
При решении ряда задач используют более сильные методы отбраковки, основанные на аппарате математического программирования. Это методы линейного, динамического и целочисленного программирования, программирования на сетях и т.д. Характерной особенностью данных методов является поиск оптимального решения (значения целевой функции, критерия) в условиях действия набора ограничений. Примерами подобного рода задач, служат составление оптимального плана перевозок, штатного расписания, распределение ресурсов, поиск оптимального маршрута и т.п.
При решении интеллектуальных задачах нашел широкое применение метод частичного (неявного) перебора. В этом методе (рис.3.2) в узлах помимо проверки допустимости (соответствия ограничениям) считается и проверяется значение выбранного критерия. Если значение этого критерия (при минимизации целевой функции) в некотором узле J больше, чем значение, полученное в другом итоговом узле I, то дальнейший поиск из узла J не ведется (т.к. значение критерия не станет лучше).
Рис.3.2. Обход дерева при поиске решения методом неявного перебора
(Кп – значение критерия в промежуточном узле; Ки – значение критерия в узле, соответствующем полному набору ограничений)
Оптимальным решение в рассмотренном примере является решение в узле 5. Поиск решения из узла 7 не выполнялся, т.к. решения в узлах 8 и 9 дадут заведомо худшее решение по сравнению с узлом 5.
Ограничением использования этого метода является как монотонность выводов, так и монотонность критерия (целевой функции). Т.е. значение критерия в узле, из которого ведется поиск, не может быть больше значения критерия в нижележащих узлах. В случаях, когда надо максимизировать целевую функцию, считают величину обратную критерию 1/К.
Другой, часто используемый метод поиска решений называется алгоритмом А*. Этот эвристический алгоритм используют в тех случаях, когда даже частичный обход полного дерева выполнить нереально. В нем для всех узлов, удовлетворяющих ограничениям и в которые можно попасть из корневого узла, вычисляется значение критерия. Дальнейший процесс поиска выполняется только из узла, в котором значение критерия максимально (минимально), остальные ветви поиска не рассматриваются.
Рис.3.3. Поиск решения с помощью алгоритма А*
Существенным недостатком данного алгоритма является возможный пропуск оптимального решения (в примере узел 10), но найденное итоговое решения очень часто является оптимальным или, по крайней мере, эффективным.
Очень важной областью применения эвристических алгоритмов поиска решений являются игровые задачи, особенно, игры с соперником. Игры для двух сторон более сложны, чем «простые» задачи из-за существования «враждебного» и, по существу, непредсказуемого противника. Как правило, ходы соперников чередуются и один из них пытается увеличить значение целевой функции (максимизировать свой выигрыш), а другой – уменьшить (минимизировать выигрыш или увеличить проигрыш соперника). Наиболее популярными методами поиска решений в играх с соперником являются прямой алгоритм минимакса и алгоритм альфа-бета-усечения.