Предыдущая страница реферата | 5  6  7  8  9  10  11  12  13  14  15 | Следующая страница реферата

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

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

Пуск

Поместить s в список ОТКРЫТ.

Положить g(s)=0.

нет Пуст ли да

список неудача

ОТКРЫТ?

Взять из списка ОТКРЫТ вершину с наименьшим значением g и поместить ее в список ЗАКРЫТ.

Обозначить ее через n.

нет Является ли n да успех вершиной цели?

Раскрыть n. Вычислить значение g для дочерних вершин.

Поместить эти вершины в список ОТКРЫТ.

Провести от них указатели к n.

рис.7 Блок- схема программы алгоритма равных цен для деревьев.

4.3 Метод перебора в глубину.

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

Глубина корня дерева равна нулю.

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

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

Метод перебора в глубину определяется следующей последовательностью шагов:
1) Поместить начальную вершину в список, называемый ОТКРЫТ.
2) Если список ОТКРЫТ пуст, то на выход подается сигнал о неудаче поиска, в противном случае перейти к шагу (3).
3) Взять первую вершину из списка ОТКРЫТ и перенести в список ЗАКРЫТ. Дать этой вершине название n.
4) Если глубина вершины n равна граничной глубине, то переходить к (2), в противном случае к (5).
5) Раскрыть вершину n, построив все непосредственно следующие за ней вершины. Поместить их (в произвольном порядке) в начало списка ОТКРЫТ и построить указатели, идущие от них к n.
6) Если одна из этих вершин целевая, то на выход выдать решение , просматривая для этого соответствующие указатели, в противном случае переходить к шагу (2).

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

Пуск

Поместить s в список ОТКРЫТ.

нет Пуст ли да

Рекомендуем скачать другие рефераты по теме: конспекты 9 класс, курсовые рефераты.



Предыдущая страница реферата | 5  6  7  8  9  10  11  12  13  14  15 | Следующая страница реферата

Поделитесь этой записью или добавьте в закладки