Полезное для программистов:

Фриланс
Новости
Статьи
   
Рубрики:


Поиск на графе и его обход

Поиск:
Для начала пусть дерево G задано множеством вершин V ( корневая вершина v0 ), дуг - E и Г(v,-) - перечнем потомков вершины v из V.

Обход (пока)дерева вширь (сначала уровень 0, затем 1, и т.д.)
будет идти так 0 - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8, если дерево - такое, как на рис.1

    
   уровень:

          0 |      0=v0
            |     /|
            |    / |
            |   /  |  
          1 |   1  2  3
            |  /|  |
            | / |  |
          2 |4  5  6  7
            |          
            |           
          3 |            8

              рис.1.

Он потребует использования очереди QUEUE

     ----------    ---------------------------
--->|v=>QUEUE|--->|WHILE  QUEUE # ПУСТО  DO |-------->
     ----------    ----------+----------------
                    ---------v---------   ^
                    |     w<=QUEUE    |   |
                    |      USE(w)     |>--+
                    | Г(w,-) => QUEUE |
                    -------------------
    Г(w,-) => QUEUE  - запись в очередь всего содержимого Г(w,-)

Обход вершин произвольного графа G = { V, E } отличается от обхода дерева лишь тем, что необходимо устранить дублирующее попадание в пройденную вершину. Для этого вводится пометка вершин NEW[V]= 1*TRUE, в стек или очередь заносятся только вершины, помеченные TRUE, при этом их пометка заменяется на FALSE. Следует помнить, что граф может оказаться не связным или некоторые вершины могут быть недостижимы из исходной v0.

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

Алгоритм поиска вглубь на произвольном графе имеет вид:

       --------------------           --------------------
  ---->| FOR  v из  V  DO |---------->| FOR  v из  V  DO |---->
       --------------------           --------------------
              |         ^                   |          ^
        ------v-------  |              -----v--------  |
    |NEW[V]:=TRUE|--+              |   WALK(v)  |--+
        --------------                 --------------


где рекурсивная процедура WALK соответствует блок-схеме:

              ----------------     -----------------------
        ----->¦  USE(v)      |---->|FOR  w из Г(v,-)  DO |----->
              ¦NEW[V]:=FALSE |     -----------------------
              ----------------              |        ^
                                       -----v----нет |
                                       | NEW[w] |----+
                                       ----------    |
                                            | да     |
                                       -----v-----   |
                                       | WALK(w) |---+
                                       -----------


Сложность этого алгоритма О(m+n), где m=||V||, n=||E||.

Достоинства метода:

1. Каждая дуга графа анализируется только один раз.
2. Алгоритм решения задачи легко погружается в этот метод.

Применение алгоритма:

- определение компонент связности графа за О(m+n) операций
- при противоположной пометке вершин алгоритм позволяет определять наличие контура в графе.

Алгоритм поиска вширь из вершины v0 на произвольном графе имеет вид /первоначально NEW[V] = 1*TRUE/:

     ------------        ---------------------------
--->| v0=>QUEUE| ------>| WHILE  QUEUE # ПУСТО DO |-------->
     |NEW[v0]=  |        -----------+---------------
     |     FALSE  |       ------------v-----------  ^
     ------------       | v =< QUEUE; USE(v)   |  |
                        | FOR w из Г(v,-) DO   |--+
                        -------+----------------
                               |             ^
                         ------v---- нет     |
                         |  NEW[w] |---------+
                         ------+----         |
                               | да          |
                         ------v----------   |
                         |  NEW[w]=FALSE |   |
                         |   w => STACK  |---+
                         -----------------


  Применение алгоритма:
- поиск кратчайшего пути на графе (выхода из лабиринта)

  Пример использования стратегии "разделяй и властвуй" MINMAX(S) - одновременный поиск наибольшего и наименьшего значений на множестве S. Вспомогательные процедуры:

MIN_MAX(min,max,s1,s2) - используя одно сравнение находит наименьшее min и наибольшее - max значение среди S={s1,s2} - одного или двух элементов линейно упорядоченного множества (например, чисел) s1 и s2.

FMAX(max,s1,s2) - находит наибольшее max, FMIN(min,s1,s2) - наименьшее min среди s1,s2.

S -> S1 + S2 - эффективная процедура деления множества S на два примерно равных S1, S2.

Исходные данные - множество S исходных значений (к примеру вектор S[1:n]) MINMAX(S,min,max)

                                -----------------да
                                | || S ||  <= 2 |----+
                                --+--------------    |
                                  |нет               |
                      ------------v----------    ----v-------------------
                      |  S -> S1 + S2       |    |MIN_MAX(min,max,s1,s2)|
                      | MINMAX(S1,min1,max1)|    ----+-------------------
                      | MINMAX(S2,min2,max2)|        |
                      | FMIN(min,min1,min2) |        |
                      | FMAX(max,max1,max2) |        |
                      -------------+---------        |
                                   |            -----v---
                                   ------------>| RETURN|-->
                                                ---------

Расчет трудоемкости алгоритма. Пусть T(n) - требуемое коли- чество сравнений для поиска наибольшего и наименьшего значений среди n чисел. Тогда Т(n) определяется следующим соотношением:

                     {  1,          n <= 2
             T(n) =  {
                     { 2 T(n/2)+2,  n  > 2.

Решение соотношения: T(n) = 3/2*n - 2 - трудоемкость алгоритма.

В случае рекуррентного соотношения

                     {  b,          n <= n1
             T(n) =  {
                     { a*T(n/c)+b,  n  > n1.

его решение имеет следующую асимптотику:

                     {  O(n),          a < c,
             T(n) =  {  O(n*log(n),    a = c,
                     {  O(n**log (a)), a > c.






Просмотров: 2187

 

 

Новые статьи:


Популярные:
  1. Как сделать цикличным проигрывание MIDI-файла?
  2. Создание AVI файла из рисунков
  3. Как устройство "отключить в данной конфигурации"?
  4. Kто в данный момент присоединен через Сеть?
  5. Как узнать количество доступной памяти?
  6. Как реализовать в RichEdit разноцветный текст?
  7. Как скрыть свое приложение от ProcessViewer
  8. Как программно нажать/скрыть/показ кнопку "Start"?
  9. Модуль работы с ресурсами в PE файлах
10. Функции вызова диалоговых окон выбора
11. Проверка граматики средствами Word'а из Delphi.
12. Модуль для упрощенного вызова сообщений
13. Функции для записи и чтение своих данных в, ЕХЕ- файле
14. Рекурсивный просмотр директорий
15. Network Traffic Monitor
16. Разные модули
17. Универсальная функция для обращения к любым экспортируем функциям DLL
18. Библиотека от VladS
19. Протектор для UPX'а
20. Еще об ICQ, сообщения по контакт листу?
21. Использование открытых интерфейсов
22. Теория и практика использования RTTI
23. Работа с TApplication
24. Примеры использования Drag and Drop для различных визуальных компонентов
25. Что такое порт? Правила для работы с портами
26. Симфония на клавиатуре
27. Загрузка DLL
28. Исправление автоинкремента
29. Взаимодействие с чужими окнами
30. Проверить дубляжи в столбце


 

 

 
 
На главную