Читайте также:
|
сложность задачи поиска решений варьируется от простых задач малой размерности с неизменяемыми определенными данными и отсутствием ограничений на результат и способ его получения до сложных задач большой размерности с изменяемыми, ошибочными и неполными данными и произвольными ограничениями на результат и способ его получения. Таким образом, становится ясно, что каким-либо одним методом нельзя решить все задачи.
Стратегия интуитивного поиска основана на полном исследовании всех имеющихся вариантов. Очень трудоемкий метод поиска знаний, требующий последовательного перебора всех возможных решений.
Стратегия систематизированного поиска реализуется методами поиска в глубину и в ширину.
Метод поиска в глубину заключается в последовательном анализе одного варианта до изучения других вариантов. Поиск выполняется по следующей методике. Например, первой исследуется одна ветвь дерева решений. Когда процесс поиска заходит в тупик, то осуществляется возврат вверх в последний пункт выбора, где имеются неизученные альтернативные варианты решения, и затем осуществляется следующий вариант выбора.
При поиске в ширину, напротив, система предусматривает переход в первую очередь к вершинам, ближайшим к стартовой вершине (т.е. отстающим от нее на одну связь), затем к вершинам, отстающим на две связи, на три и т. д., пока не будет найдена целевая вершина. Программа поиска продвигается по дереву решений слева направо, расширяя каждый из маршрутов, и отбрасывая те из них, которые являются тупиковыми.
Наиболее эффективной является стратегия упорядоченного направленного поиска, которая основана на реализации механизма автоматизированного выбора наиболее подходящего варианта. В основе реализации данного механизма лежит принцип использования правил принятия решений, позволяющих уменьшить объем перебора.
Упорядоченный направленный поиск данных осуществляется следующим образом (рис. 2.9):
- если есть приемлемые варианты выбора, то выбирается наилучший из них, используя заданный критерий рассуждения (правило);
- если рассуждения попали в тупик, то происходит возврат в последнее место, где имеются альтернативные варианты выбора, и делается следующий наилучший выбор.
Дата добавления: 2015-07-10; просмотров: 73 | Нарушение авторских прав