| Тема 3. Методы решения задач.
Прежде чем рассмотреть различные методы поиска сама задача должна быть поставлена в рамках следующих подходов: Подход, основанный на пространство состояний; Подход, основанный на сведении задач на редукциях к подзадаче; Подход как, теорема подлежащая доказательству.
Лекция 7. Методы в пространстве состояний
Цель лекций. Выбор метода поиска решения. Краткие теоретические сведения о состояний, операторов задачи. Различные способы поиска. Структуры LIFO и FIFO. Механизм бектрекинга.
Содержание лекций. Одним из важных вопросов, возникающих при проектировании управляющей компоненты систем, основанных на знаниях, является, т.е. стратегии вывода. От выбранного метода поиска будет зависеть порядок применения и срабатывания правил. Процедура выбора сводится к определению направления поиска и способа его осуществления. Подход основанный на пространство состояний. Мы рассмотрим следующие способы используемые в подходе пространстве состояний: а) метод полного перебора; б) метод поиска в глубину; в) эвристический метод. Краткие теоретические сведения. Описание состояний. Чтобы построить описание задачи с использованием пространства состояний, мы должны иметь определенное представление о том, что такое состояние в этой задаче. Важным этапом построения какого-либо описания задачи с использованием пространства состояний является выбор некоторой конкретной формы описания состояний этой задачи. В сущности любая структура величин может быть использована для описания состояний. Это могут быть строки символов, векторы, двухмерные массивы, деревья и списки. Часто выбираемая форма описания имеет сходство с некоторым физическим свойством решаемой задачи. Так, в игре в пятнадцать естественной формой описания состояний может быть массив 4х4. Выбирая форму описания состояний, нужно позаботиться и о том, чтобы применение оператора, преобразующего одно описание в другое, оказалось бы достаточно легким. Для обсуждения методов поиска решения оказывается полезным введение понятий состояний и операторов для данной задачи. Для игры в пятнадцать состояние задачи- это просто некоторое конкретное расположение фишек. Начальные и целевые конфигурации представляют собой соответственно начальное и целевое состояния. Пространство состояний, достижимых из начального состояния, состоит из всех тех конфигураций фишек, которые могут быть образованны в результате допустимых правилами перемещений фишек. Многие задач имеют чрезвычайно большие (если не бесконечные) пространства состояний. Оператор преобразует одно состояние в другое. общем случае мы будем предполагать, что операторы- это вычисления, преобразующие одни описания состояний в другие. Основные понятия и термины. Таким образом, мы видим, что для полного представления задачи в пространстве состояний необходимо задать:а) форму описания состояний и, в частности, описание начального состояния; б) множество операторов и их воздействий на описания состояний; в) свойства описания целевого состояния [11]. Пространство состояний полезно представлять себе в виде направленного графа. Граф состоит из множества вершин. Некоторые пары вершин соединены с помощью дуг, и эти дуги направлены от одного члена этой пары к другому. Такие графы носят название направленных графов Процесс применения множества операторов к вершине графа называется раскрытием вершин. Рассмотрим первый из методов поиска в пространстве состояний. Поиск в глубину (Depth-first search, DFS). В методах перебора в глубину прежде всего раскрываются те вершины, которые были построены последними. Определим глубину вершины следующим образом: Глубина корня дерева равна нулю. Глубина любой последующей вершины равна единице плюс глубина вершины, которая непосредственно ей предшествует. Таким образом, вершиной, имеющей наибольшую глубину в дереве перебора, в данный момент служит та, которая должна в этот момент быть раскрыта. Такой подход может привести к процессу, разворачивающемуся вдоль некоторого бесполезного пути, поэтому нужно ввести некоторую процедуру возвращения. В качестве механизма реализаций или в качестве обработки списков для метода поиска в глубину в алгоритмах программирования выбран механизм «стек». Для списка open реализуется механизм как стек магазинного типа, или его называют структура LIFO «last-in-first-out» т.е. «последним пришел – первым обслужен». Состояния добавлются и удаляются с левого конца списка. К одним из классических алгоритмов поиска на графе пространства состояний служит метод поиска с возвратами бектрекинг (backtrack) [12]. Этот способ предлагает определенную организацию перебора всех возможных вариантов решения задачи, число которых может быть велико. Суть бектрекинга состоит в том, чтобы в каждой точке процесса решения задачи, где существует несколько априори равноправных альтернативных вариантов (путей) дальнейшего продолжения, выбрать один из них и следовать ему, предварительно запомнив другие альтернативы – для того, чтобы в случае неуспешности выбранного варианта-пути вернуться в точку выбора и выбрать для продолжения решения другой возможный вариант-путь. В общем случае в процессе решения возможно возникновение многих подобных точек выбора, называемых обычно точками бектрекинга или развилками; к каждой из таких точек может потребоваться возврат для выбора других вариантов решения. Методы полного перебора. Поиск в ширину. (BFS, Breadth-first search). В методе полного перебора вершины раскрываются в том порядке, в котором они строятся. В методе полного перебора непременно будет найден самый короткий путь к целевой вершине при условии, что такой путь вообще существует. Если такого пути нет, то в указанном методе будет объявлено о неуспехе в случае конечных графов, а в случае бесконечных графов алгоритм никогда не кончит свою работу. Если сделать резюме, то суть заключается в том, чтобы рассмотреть все вершины, связанные с текущей. Принцип выбора следующей вершины – выбирается та, которая была раньше рассмотрена. В качестве механизма реализаций или в качестве обработки списков для метода поиска в ширину в алгоритмах программирования выбран механизм «очередь». Для списка open реализуется механизм очередь, или его называют структура FIFO «first-in-first-out» т.е. «первым пришел – первым обслужен». Состояния добавлются в список справа, и удаляются с левого конца списка.
Достарыңызбен бөлісу: |
