2
5
Б С
 |
 |
2 1
Д
Е
Стратегия равных цен
Стратегия равных цен применяется в тех случаях, когда дерево вариантов содержит часто повторяющиеся ситуации. Эта стратегия относится к задачам затратного типа. Поиск осуществляется на основе перебора в ширину, причем все достигнутые вершины получают оценки в виде суммарного частичного пути, пройденного до соответствующей вершины. Всякий раз, когда ситуация повторяется, запоминается кротчайший путь до неё. Продемонстрируем следующем рисунком(из А в Ф):
1 4
1
1 2 1
Прямой и обратный поиск
По направлению поиск делится на прямой и обратный. При прямом поиске шаги поиска делаются от начальной ситуации к конечной. При обратном поиске от конечной ситуации к начальной.
Сокращение числа просматриваемых вариантов возможно при использовании комбинированного встречного поиска.
ИГРОВЫЕ СТРАТЕГИИ ПОИСКА РЕШЕНИЯ
Эти стратегии рассматриваются на неоднородных деревьев вариантов. Поскольку в этом случае в предметной области существует несколько активных объектов, изменяющих ситуацию, то их принято называть игроками, а действия игроков по изменению ситуации ходами. В случае с двумя игроками, совершающими ходы по очереди можно использовать минимаксный подход.
Минимаксный подход
В этом случае оценочная функция используется для одного игрока со знаком «+», а для другого со знаком «-», или же говорят, что один игрок стремиться максимизировать оценочную функцию, а другой минимизировать эту же оценочную функцию. Соответственно игроки называются МАКС и МИН. В минимаксном подходе оценка ситуаций рассчитывается на основе частичного перебора на несколько ходов в глубину. При этом оцениваются последние полученные ситуации и от них пересчет ситуаций осуществляется к отцовской вершине, исходя из того что игрок МАКС выбирается ход с максимальной оценкой, а игрок МИН с минимальной. За счет сделанных предположений о том, что каждый игрок выбирает лучший для себя ход, существует возможность сокращения перебора методом локально углубленного поиска. Для этого оценивается сначала минимаксный способом N ходов в глубину, выбирается наиболее вероятное продолжение и от него делается уточнение оценки еще на M ходов в глубину. Если оценка не становится хуже, делается ход в реальной предметной области. В противном случае реализуется возврат к вариантам, оцененным ранее как мене предпочтительными.
Метод α\β отсечений
Метод заключается в отказе от рассмотрения ходов, на которые противник может дать заведомо более сильный ответ, чем на ранее рассмотренные собственные ходы. α отсечение используется обоими соперниками для МАКС игрока, если какой из вариантов приписывает отцовской вершине оценку заведомо меньшую, чем лучшая оценка предыдущих отцовский вершин. β отсечение используется обоими соперниками для МИН игрока, если какой то из вариантов приписывает отцовской вершине оценку заведомо большую, чем оценка предыдущих отцовских вершин.
Программная реализация интеллектуальных решателей задач
Циклическая и рекурсивная реализации
При циклической реализации в программе выделяется один главный цикл, в котором параметром цикла является номер уровня (хода) в дереве вариантов. При выполнении очередного хода делается очередной цикл, и номер уровня увеличивается на единицу. При возврате к порождающим вершинам номер уровня уменьшается на два и вновь делается очередной цикл. В теле цикла осуществляются проверки:
1. На наличие целевой ситуации.
2. На наличие тупика.
3. На исчерпание возможных ходов.
В соответствии с результатами этих проверок выполняются действия либо по выдачи результата, либо по совершению очередного хода, либо по возврату назад. Достоинством этого метода является относительная гибкость в управлении алгоритмом поиска, а недостатком то, что действия по заказу и освобождению оперативной памяти под новые ситуации необходимо выполнять вручную.
Рекурсивный алгоритм менее гибок, но более прост, так как заказ и освобождение памяти производится в нем автоматически. Рекурсивная процедура в своем теле содержит те же проверки, что и циклическая процедура, но вместо очередного цикла просто снова рекурсивно вызывается так же самая процедура.
Продукционный подход к реализации поиска решения
Под продукцией понимается дуга ориентированного графа, представляющего собой запись какого либо алгоритма и состоящая из пары условия -> действия. Считается, что если условие на дуге истинное, то выполняется соответствующее действие.
Оценка эффективности поиска
Оценки эффективности анализируют следующие характеристики:
1. Время поиска.
2. Объем оперативной памяти, занятой программой.
3. Активизированная поддерево вариантов - это дерево, построено имплицитно в процессе решения задач.
Базовые характеристики поиска рассчитываются на основе активизированного поддерева.
1. Глубина поиска D: максимальное число вершин, порожденных до целевой или тупиковой вершины в дереве вариантов.
2. Длина пути решения L: это число вершин лежащих на минимальном из найденных путей решений.
3. Общее число порожденных вершин N.
Производные характеристики поиска рассчитываются на основе базовых.
4. Разветвленность поиска R=N/L.
5. Направленность поиска W=N1/L.
6. Максимальное хранимое поддерево поиска M. Это максимальное число вершин, хранение которых необходимо в оперативной памяти одновременно для реализации метода.
7. Эффективность просмотра вершин tc=T/N, где Т – время работы программы.
8. Емкость поиска Vs = Vb*M, где Vb – объем оперативной памяти, занимаемой моделью ситуации в байтах.
Эффективные характеристики поиска
Если рассмотренные ранее характеристики разделить на время поиска, то можно получить характеристики, которые называются эффективными.
Перечисленные характеристики используются для сравнения новых методов полученных современными авторами с ранее известными методами. Для того чтобы достоверно протестировать новый метод нужно с его помощью решить множество задач. При определении тестирующего множества для задач варьируют следующие параметры:
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.