Изменения при переборе в произвольных графах

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

Для поиска в произвольном графе без учёта стоимостей нужно только проверить есть ли данная вершина в списках OPEN или CLOSED и если она там есть, то второй раз её не вносить, а только изменить указатель.

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

В поиске в глубину: Необходимо пересчитывать глубину при раскрытии той же самой вершины.

В произвольном графе множество вершин и указателей на каждом шаге перебора образуют дерево.

3. Алгоритм упорядочения поиска в пространстве состояний.

Алгоритм упорядоченного перебора А:

1. Поместить начальные вершины в список OPEN и вычислить значение .

2. Если список OPEN пусть, значит решений нет.

3. Взять из OPEN ту вершину для которой - минимально, перенести её в CLOSED. Дать этой вершине имя n. В случаи равенства значений -, выбрать любую, отдавая предпочтение целевой.

4. Если n - целевая вершина, то выход с указанием решения по средствам указателей.

5. Раскрыть вершину n. Для порожденных вершин посчитать . Если порожденных вершин нет то перейти к п2.

6. Связать с теми вершинами n_i- которых нет в списках OPEN и CLOSED посчитанные значения и поместить их в список OPEN. Провести указатели к n.

7. Те порожденные вершины, которые есть в OPEN и CLOSED связать со значениями , если эти значения меньше, чем вычисленные раньше. Поместить их в OPEN и связать указателями к вершине n.

8. Перейти к пункту 2.

ПРИМЕР:

Оптимальный алгоритм перебора

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

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

В формуле для текущего значения целевой функции первое слагаемое определяется по ходу решения. Второе слагаемое определяется исходя из эвристической информации

Харт, Нильсон и Рафаэль определили условие при котором алгоритм упорядоченного перебора А становится оптимальным становится оптимальным алгоритмом А^*. Это условие сформулировано в следующей теореме:

ТЕОРЕМА:

Если для всех вершин n выполняется условие

где -эвристическое значение n - действительное. И стоимости всех дуг превосходят некоторое число  >0, то алгоритм А будет допустимым.

Выбрав в качестве найбольшей из нижних границ прейдем к тому, что раскрывается наименьшее число вершин, при допустимости алгоритма, т.е. А^* становится оптимальным, если в качестве выбирается

ЗАМЕЧАНИЕ:

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

4. Оптимальный алгоритм эвристического поиска А*

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

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

В формуле для текущего значения целевой функции первое слагаемое определяется по ходу решения. Второе слагаемое определяется исходя из эвристической информации

Харт, Нильсон и Рафаэль определили условие при котором алгоритм упорядоченного перебора А становится оптимальным становится оптимальным алгоритмом А^*. Это условие сформулировано в следующей теореме:

ТЕОРЕМА:

Если для всех вершин n выполняется условие

где -эвристическое значение n - действительное. И стоимости всех дуг превосходят некоторое число  >0, то алгоритм А будет допустимым.

Выбрав в качестве найбольшей из нижних границ прейдем к тому, что раскрывается наименьшее число вершин, при допустимости алгоритма, т.е. А^* становится оптимальным, если в качестве выбирается

ЗАМЕЧАНИЕ:

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

5. Критерии качества работы эвристических алгоритмов.

Критерий целенаправленности Дорана-Мичи

L - длинна найденного пути до цели, Т - общее число раскрытых вершин при переборе.

II. Фактор эффективного ветвления (Слендис, Диксон)

Критерий ветвистости - это В. Он и оценивает эффективность алгоритма, Т - общее число построенных вершин. L - длинна пути.

6. Метод сведения задач к подзадачам

Идея заключается в разбиении данной задачи на подзадачи. Это разбиение производится дол тех пор пока не прейдём к элементарным подзадачам. Элементарной называется задача которая имеет известное решение, или для которой известно отсутствие решения. Часть проблем можно решить или доказать неразрешимость с помощью доказательства теоремы.Процесс решения задачи разбивается на 2 этапа:

1) Представление задачи. Для одной и той же задачи возможно не одно представление.

2)Поиск решения, который зависит от представления.

Пусть есть некоторая проблема А, которая разбита на подпроблемы B,C,D

В итоге получаем И-ИЛИ граф. Алгоритм поиска в графах И-ИЛИ связан с разметкой вершин на разрешимость и неразрешимость. Эта разметка обычно производится Когда найдены элементарные задачи. Определение разрешимой вершины рекурсивное. И-вершина считается разрешимой, если все порожденные разрешимы. ИЛИ-вершина считается разрешима, если хотя бы одна порожденная вершина разрешима.

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

Корневая вершина считается разрешимой, если все порождённые И-вершины разрешены или хотя бы одна порождённая ИЛИ вершина разрешена. Проблема не имеет решения, если доказана неразрешимость корневой вершины. Корневая вершина считается неразрешимой, если неразрешима И-вершина или неразрешимы все порождённые ИЛИ-вершины.

Метод поиска решений при сведении задач к подзадачам.

Решение считается найденным, если при разметке графа И-ИЛИ корневая вершина помечена, как разрешимая, при этом само решение представляется поддеревом, которое включает корневую вершину.

Если граф или дерево взвешенное, то ставится задача нахождения оптимального решения.

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

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

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

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

При эвристическом поиске порядок раскрытия вершин определяется значением оценочной функции. Стоимость пути заменяется стоимостью поддерева решений.

Оптимальным называется дерево решений с минимальной стоимостью.

Разметка графов И-ИЛИ начинается с листьев.

Оценочная эвристическая функция определяется рекурсивно следующим образом: 1) Для концевых вершин h(n)=02) для не концевых вершин типа И 3) Для не концевых вершин типа ИЛИ

При эвристическом поиске появляется - это оценка поддерева, которая возможна для вершины , как корневой вершины. На каждом этапе перебора существует некоторое подмножество поддеревьев содержащих начальную вершину, по оценке являющихся оптимальными. Такие поддеревья будем называть потенциальными, обозначается .

Если в результате поиска возникает комбинаторный взрыв, то применяются эвристические методы поиска, т.е. вводится оценочная функция.

ПРИМЕР: Символьное интегрирование.

Входная информация – подынтегральная функция, выходная – символьное значение интеграла.

Для вычислений используется таблица интегралов 1. 2. 3. 4. 5. а так же правила интегрирования1.

2. Интегрирование по частм

3. Правило подстановок.

7. Основные методы поиска в "и–или" деревьях

Поиск по сайту: