2015-07-14
399
Задачи интеллектуального характера, в том числе задачи принятия решений, могут рассматриваться как поисково-переборные задачи. Основанием к этому служат 2 факта:
1. неточный, неопределенный характер обрабатываемых данных.
2. алгоритм решения может не существовать или же его реализация невозможна на некоторых заданных ресурсах. В этом случае говорят, что задача будет иметь недетерминированное решение. Общим подходом для решения таких задач является организация процедуры поиска. Процесс решения будет описываться в виде некоторого графа. Состояние графа определяют обрабатываемые данные. Дуги в графе между вершинами описывают применяемые правила.
Поисковая процедура генерирует варианты решений, и шаг за шагом постепенно их модифицирует. Отличие поиска от вычислений можно определить так: при вычислении на каждом шаге вид и количество срабатываемых правил известны и определены заранее. При поиске вид и количество применяемых правил заранее неизвестны. Вследствие этого в условие применимости правила должно быть заложено само правило. При этом желательно иметь унифицированное условие применимости правила, а еще лучше единственное условие.
|
|
|
Задача поиска формально определяется следующим образом:
{S, F, P, Q},
где S – начальное состояние,
F – конечное состояние (финишное)
P – множество правил, носящих недетерминированный смысл исполнений.
Q – множество ограничений.
| А 1 |
| D 4 |
| B 2 |
| C 3 |
| E 5 |
| F 6 |
| G 7 |
| H 8 |
| I 9 |
| K |
| L |
| M |
| N |
| P |
| O |
Рис. 33.
Характеристики графа состояний, формируемых при поиске
1. глубина поиска
а) кратчайший путь в графе
б) наидлиннейший путь в графе
2. ширина поиска
а) максимальный коэффициент ветвления
б) средний коэффициент ветвления по графу
3. общее количество состояний в графе
4. коэффициент сужения
При организации поиска может возникать неоднозначность выбора пути для некоторого общего решения.
Например, для вершины L существуют пути:
A → B → E → L
A → D → L
С точки зрения конечного результата ценность представляет только один путь, желательно кратчайший. Все остальные пути, ведущие в общую вершину, следует признать неэффективными или холостыми, поэтому аналитическая оценка коэффициента сужения является достаточно мощным средством ускорения поиска.
