МЕТОДЫ ПОИСКА В ПРОСТРАНСТВЕ СОСТОЯНИЙ

<

052914 1039 1 МЕТОДЫ ПОИСКА В ПРОСТРАНСТВЕ СОСТОЯНИЙФундаментальный вопрос, связанный с преобразованиями, которые основаны на оценке стоимости, заключается в том, приведут ли эти преобразования к комбинаторно быстрому росту альтернатив, которые необходимо оценивать, и обеспечат ли они баланс между стоимостью оптимизации и стоимостью выполнения.

Источник многочисленных альтернатив — сами разнообразные преобразования, а также множество объектов (например, блоки запроса, таблицы, ребра соединений, предикаты и т.д.), к которым каждое преобразование может применяться. Если есть N объектов, к которым может применяться преобразование T, то применением T потенциально можно образовать 2N возможных альтернативных комбинаций. В общем случае, если есть M преобразований T1, T2, …, TM, которые могут применяться к N объектам, то существует (1 + M)N возможных альтернативных комбинаций.

Например, для запроса Q1 нужно рассмотреть 4 альтернативы: без устранения вложенности, с устранением вложенности только первого подзапроса (QS1), с устранением вложенности только второго подзапроса (QS2) или с устранением вложенности обоих подзапросов. Мы обозначаем состояние как массив бит, где n-ый бит показывает, является ли n-ый объект (например, подзапрос) преобразованным (значение 1) или нет (значение 0). Например, состояние (0,1) говорит об устранении вложенности только второго подзапроса. Если есть M преобразований, применяемых к N объектам, состояние представляется матрицей из M×N бит.

Чтобы справиться с проблемой комбинаторно быстрого роста в случае перестановок соединения, было предложено использовать рандомизированные алгоритмы, такие как имитация отжига (Simulated Annealing), генетический поиск (Genetic Search), итерационное уточнение (Iterative Improvement), поиск с запретами (Tabu Search)

Общая идея всех этих стратегий заключается в выполнении квазислучайных блужданий в пространстве поиска, начиная с исходного состояния и пытаясь достичь локального минимума низкой стоимости. Конечно, эти стратегии не гарантируют, что может быть достигнут глобальный минимум — наилучшее преобразование, так как во время блужданий посещается только малая часть пространства состояний. Тем не менее, они имеют практическую значимость, так как качество решения обычно улучшается с длительностью поиска.

Сложность преобразований, основанных на оценке стоимости, определяется количеством альтернативных комбинаций или пространством состояний, которое экспоненциально растет с количеством преобразуемых объектов. Если количество преобразуемых объектов мало, может стать осуществимой техника полного перебора преобразований с исчерпывающим поиском в пространстве состояний. Для ограничения потенциального роста времени оптимизации мы используем несколько различных методов перебора пространства состояний.

Исчерпывающий поиск (Exhaustive Search). При исчерпывающем поиске рассматриваются все возможные 2N состояний пространства состояний N объектов. Например, в запросе Q1 мы рассматриваем 4 состояния: (0,0), (0,1), (1,0) и (1,1). Этот поиск гарантирует нахождение наилучшего решения.

Итерационное уточнение (Iterative Improvement). Метод итерационного уточнения используется для сокращения пространства поиска. Главная идея этого метода состоит в том, что мы начинаем с некоторого исходного состояния и продвигаемся к следующему соседнему состоянию, используя некоторый метод, направленный на поиск локального минимума за счет постоянного выбора нисходящего направления движения; мы повторяем этот поиск локального минимума, начиная с другого исходного состояния в следующей итерации. Алгоритм останавливается, если новые состояния более не находятся, или было достигнуто некоторое условие завершения (например, максимальное количество состояний). Количество состояний, перебираемых этой техникой, лежит в пределах от N до 2N.

Линейный поиск (Linear Search). Основная идея этого метода поиска основана на подходе динамического программирования, в котором предполагается, что для запроса, состоящего из нескольких объектов, достаточно проанализировать на предмет преобразования только некоторый поднабор этих объектов, а затем расширить это дополнительными преобразованиями других объектов. Другими словами, если стоимость (1,0) меньше, чем стоимость (0,0), и стоимость (1,1) меньше, чем стоимость (1,0), то можно надежно предположить, что стоимость (1,1) — самая низкая для всевозможных преобразований, и, следовательно, нет необходимости оценивать стоимость (0,1). Как можно видеть, это может существенно сократить пространство поиска. Этот метод анализирует N + 1 состояний. Линейный поиск работает лучше всего, если преобразования различных элементов независимы одно от другого.

Двухпроходной поиск (Two-pass Search). Двухпроходный поиск — самый дешевый метод поиска, в котором анализируется 2 состояния. Сравниваем стоимость плана выполнения полностью непреобразованного запроса (т.е. состояние (0,0,…)) со стоимостью плана запроса, в котором преобразованы все объекты (т.е. состояние (1,1,…)).

Инфраструктура преобразований, основанных на оценке стоимости, автоматически решает, какой метод поиска следует использовать, основываясь на количестве объектов, которые преобразуются в блоке запроса, характеристиках преобразований и общей сложности запроса. Например, если в блоке запроса содержится небольшое число подзапросов, мы используем для устранения вложенности подзапросов исчерпывающий поиск, а если число подзапросов превышает некоторое фиксированное пороговое значение, мы используем линейный поиск. Если общее число элементов в запросе, подлежащих преобразованию (например, представлений с group-by, подзапросов, вложенность которых можно устранить) превышает некоторое пороговое значение, то мы используем для всех преобразований запроса двухпроходный поиск.

 

 

2. МЕТОДЫ ПЕРЕБОРА

 

В методе полного перебора вершины раскрываются в том порядке, в котором они строятся. Простой алгоритм полного перебора на дереве состоит из следующей последовательности шагов:

1) Поместить вершину в список, называемый ОТКРЫТ.

2) Если список ОТКРЫТ пуст, то на выход подается сигнал о неудаче поиска, в противном случае переходить к следующему шагу.

3) Взять первую вершину из списка ОТКРЫТ и перенести ее в список ЗАКРЫТ; назовем эту вершину n.

<

4) Раскрыть вершину n, образовав все вершины, непосредственно следующие за n. Если непосредственно следующих вершин нет, то переходить сразу же к шагу (2). Поместить имеющиеся непосредственно следующие за n вершины в конец списка ОТКРЫТ и построить указатели, ведущие от них назад к вершине n.

5) Если какие-нибудь из этих непосредственно следующих за n вершин являются целевыми вершинами, то на выход выдать решение, получающееся просмотром вдоль указателей; в противном случае переходить к шагу (2).

В этом алгоритме предполагается, что начальная вершина не удовлетворяет поставленной цели, хотя нетрудно ввести этап проверки такой возможности. Блок- схема алгоритма показана на рис. 1. Вершины и указатели, построенные в процессе перебора, образуют поддерево всего неявно определенного дерева пространства состояний. Будем называть такое поддерево деревом перебора.

В методе полного перебора непременно будет найден самый короткий путь к целевой вершине при условии, что такой путь вообще существует. (Если такого пути нет, то в указанном методе будет объявлено о неуспехе в случае конечных графов, а в случае бесконечных графов алгоритм никогда не кончит свою работу.)

На рис. 1 приведена блок- схема программы алгоритма полного перебора для дерева.

Метод равных цен. Могут встретится задачи, в которых решению предъявляются какие-то иные требования, отличные от требования получения наикратчайшей последовательности операторов. Присваивание дугам деревьев определенных цен (с последующим нахождением решающего пути, имеющего минимальную стоимость) соответствует многим из таких обещанных критериев. Более общий вариант метода полного перебора, называемый методом равных цен, позволяет во всех случаях найти некоторый путь от начальной вершины к целевой, стоимость которого минимальна. В то время как в выше описанном алгоритме распространяются линии равной длины пути от начальной вершины, в более общем алгоритме, который будет описан ниже, распространяются линии равной стоимости пути. Предполагается, что нам задана функция стоимости c(ni,nj), дающая стоимость перехода от вершины ni к некоторой следующей за ней вершине nj.

В методе равных цен для каждой вершины n в дереве перебора нам нужно помнить стоимость пути, построенного от начальной вершины s к вершине n. Пусть g(n)- стоимость от вершины s к вершине n в дереве перебора. В случае деревьев перебора мы можем быть уверены, что g(n) является к тому же стоимостью того пути, который имеет минимальную стоимость (т.к. этот путь единственный).

В методе равных цен вершины раскрываются в порядке возрастания стоимости g(n). Этот метод характеризуется такой последовательностью шагов:

1) Поместить начальную вершину s в список, называемый ОТКРЫТ. Положить g(s)=0.

2) Если список ОТКРЫТ пуст, то на выход подается сигнал о неудаче поиска, в противном случае переходить к следующему шагу.

3) Взять из списка ОТКРЫТ ту вершину, для которой величина g имеет наименьшее значение, и поместить ее в список ЗАКРЫТ. Дать этой вершине название n. (В случае совпадения значений выбирать вершину с минимальными g произвольно, но всегда отдавая предпочтение целевой вершине.)

4) Если n есть целевая вершина, то на выход выдать решающий путь, получаемый путем просмотра назад в соответствии с указателями; в противном случае переходить к следующему шагу.

5) Раскрыть вершину n, построив все непосредственно следующие за ней вершины. (Если таковых нет переходить к шагу (2).) Для каждой из такой непосредственно следующей (дочерней) вершины ni вычислить стоимость g(n), положив g(ni)=g(n)+c(n,ni). Поместить эти вершины вместе с соответствующими им только что найденными значениями g в список ОТКРЫТ и построить указатели, идущие назад к n.

6) Перейти к шагу (2).

    052914 1039 2 МЕТОДЫ ПОИСКА В ПРОСТРАНСТВЕ СОСТОЯНИЙ

Рис. 1 Блок- схема программы алгоритма полного перебора для дерева

 
 

Блок- схема этого алгоритма показана на рис.1. Проверка того, является ли некоторая вершина целевой, включена в эту схему так, что гарантируется обнаружение путей минимальной стоимости.

Алгоритм, работающий по методу равных цен, может быть также использован для поиска путей минимальной длины, если просто положить стоимость каждого ребра равной единице. Если имеется несколько начальных вершин, о алгоритм просто модифицируется: на шаге (1) все начальные вершины помещаются в список ОТКРЫТ. Если состояния, отвечающие поставленной цели, могут быть описаны явно, то процесс перебора можно пустить в обратном направлении, приняв целевые вершины в качестве начальных и используя обращение оператора Г.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3. Поиск в ширину и в глубину

 

В методе в ширину вершины раскрываются в том порядке, в котором они строятся. Основной алгоритм состоит в выполнении следующих действий.

1. Раскрывается начальная вершина . Она раскрывается до тех пор, пока ее можно раскрыть, применяя один и тот же оператор (или разные, смотря по условию). При этом образуются вершины первого уровня: S1, S2, S3…Они раскрываются в свою очередь, и образуются вершины второго уровня и т.д. (рис. 2 может служить примером этого метода: S1 и S2 — вершины первого уровня, S3 и S4 — вершины второго уровня, S5 и S6
— третьего и т.д.).

2. Расставляются указатели, ведущие от новых вершин к корню. Это могут быть условные имена, буквы, цифры, имена операторов и т.п. Но могут быть и реальные величины, например расстояния, стоимость, вес и т.д.

3. Проверяется, нет ли среди полученных вершин целевой. Если есть, то формируется решение на основе соответствующего оператора. Если целевых вершин нет, то рассматривается первая порожденная вершина и к ней применяется тот же алгоритм, после чего, переходят ко второй и т.д., пока среди получаемых вершин не окажется целевой.

Метод полного перебора в ширину гарантирует нахождение целевой вершины как раз потому, что перебор — полный. Путей достижения цели, вообще говоря, может быть много. В этом случае у нас имеется возможность выбрать наикратчайший (или самый дешевый, или самый легкий — критериев много) путь. Но может быть случай, когда граф поиска окажется бесконечным и тогда этот алгоритм никогда не кончит работу.

Таким образом, метод полного перебора гарантирует поиск оптимального решения, если дерево пространства состояний не бесконечно.

Синонимами названия метода являются: метод грубой силы, метод проб и ошибок.

 
 

052914 1039 3 МЕТОДЫ ПОИСКА В ПРОСТРАНСТВЕ СОСТОЯНИЙ

Рис. 2. Элемент дерева полного перебора в ширину для примера с обезьяной и бананами

 На рис. 2 показан элемент дерева полного перебора в ширину для примера с обезьяной и бананами (для полноты изложения здесь применяется дополнительный оператор g5, отображающий перемещение обезьяны по комнате из точки в точку).

Корень дерева совпадает с (a,b,c,0,0,). Точки d, f, k, n, m — координаты возможной миграции обезьяны по комнате. Таких точек, конечно, множество, но мы выбрали лишь несколько для примера. Они не приводят к решению, но теоретически вполне допустимы. Жирной линией показан путь до целевой вершины (c,c,c,1,1), которому соответствует последовательность операторов g4, g3, g2, g1. Алгоритм решения отобразится формулой

= g4(g3(g2(g1(a,b,c,0,0)))).

 Метод полного перебора в глубину в отличие от метода перебора в ширину предлагает раскрывать прежде всего те вершины, которые были построены последними. Первой раскрываемой вершиной, а следовательно, и последней является корневая, но процесс всегда будет идти по самой левой ветви вершин. Чтобы как-то ограничить перебор, вводится понятие глубины вершины в дереве перебора. Полагаем, что глубина корня дерева равна нулю, а глубина любой последующей вершины равна единице плюс глубина вершины, непосредственно ей предшествующей.

Отсюда следует, что наибольшую глубину всегда будет иметь та вершина, которая должна быть в этот момент раскрыта. Если образующийся путь оказывается бесполезным, то есть при заданной глубине раскрытия целевой вершины не получилось, необходимо вернуться в вершину, предшествующую раскрытой, и попытаться еще раз применить к ней операцию раскрытия. И так до тех пор, пока не будет получена целевая вершина.

052914 1039 4 МЕТОДЫ ПОИСКА В ПРОСТРАНСТВЕ СОСТОЯНИЙ

Рис. 3. Дерево полного перебора в глубину

Возврат осуществляется с помощью указателей. Как только в процессе порождения вершин достигается заданная граничная глубина, раскрывается вершина наибольшей глубины, не превышающая этой границы. Общая схема перебора в глубину показана на рис. 3.

Алгоритм перебора в глубину состоит в следующем.

1. Раскрывается начальная вершина, соответствующая начальному состоянию Sн.

2. Раскрывается первая вершина, получаемая в результате раскрытия . Ставится указатель.

3. Если она раскрывается, то следующей будет раскрываться вновь порожденная вершина. Если вершина не раскрывается, то процесс возвращается в предыдущую вершину.

4. По получении целевой вершины процесс раскрытия заканчивается и по указателям строится путь, ведущий к корню. Соответствующие дугам операторы образуют решение задачи.

5. Если для заданной глубины раскрытия целевая вершина не находится, то весь процесс повторяется снова, а в качестве новой вершины рассматривается самая левая из полученных на предыдущем этапе.

Так же, как и метод поиска «в ширину», этот метод относится к методам грубой силы. Он обеспечивает перебор всех состояний, если, конечно, прежде не встретит целевое.

 
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

СПИСОК ЛИТЕРАТУРЫ

 

  1. Андрейчиков А.В., Андрейчикова О.Н. Интеллектуальные информационные системы. Учебник. — М.: Финансы и статистика, 2004.
  2. Арсеньев С.Н., Шелобов С.И., Давыдова Т.Ю. Принятие решений. Интегрированные информационные системы. Учебное пособие для вузов. –М.: ЮНИТИ-ДАНА, 2003.
  3. Дубровин А.Д. Интеллектуальные информационные системы / Науч. ред. Шлыкова О.В. Джексон П. Введение в экспертные системы / Учебное пособие. – М.: «Вильямс», 2001
  4. –Леденева Т.М., Подвальный С.Л. Системы искусственного интеллекта и принятие решений; Учебное пособие; Уфа: УГАТУ, 2005.
  5. Романов В.П. Интеллектуальные информационные системы в экономике: Учебное пособие / Под ред. д. э. н., проф. Н. П. Тихомирова. — М.: Издательство «Экзамен», 2003.
<

Комментирование закрыто.

WordPress: 24.37MB | MySQL:116 | 1,297sec