Алгоритм Прима — различия между версиями

-     CUSTIS
    
    
     
     
    
    
     
     
      Сайт CUSTIS →
     
    
    
     
     
    
    
     
     
      Вакансии
     
    
    
     
     
    
    
     
     
      Блог команды
     
    
    
     
     
    
    
     
     
      Архив событий
     
    
    
     
     
    
    
     
     
      Архив публикаций
     
    
    
     
     
    
  
     
     Навигация
    
    
     
     
    
    
     
     
      Заглавная страница
     
    
    
     
     
    
    
     
     
      Свежие правки
     
    
    
     
     
    
    
     
     
      Случайная статья
     
    
    
     
     
    
    
     
     
      Справка
     
    
    
     
     
    
  
     
     Поиск
    
    
     
     
    
    
     
     
    
        
         
    


    
    
     
     
    
  
     
     Инструменты
    
    
     
     
    
    
     
     
      Ссылки сюда
     
    
    
     
     
    
    
     
     
      Связанные правки
     
    
    
     
     
    
    
     
     
      Спецстраницы
     
    
    
     
     
    
    
     
     
      Версия для печати
     
    
    
     
     
    

Чистый HTML



→M$WORD



→OOffice
+    Алгоритм Прима — различия между версиями
   
      
    Материал из CustisWiki
    
            Перейти к: навигация, поиск
    
    

				
				
				
				
				
				Версия 19:47, 23 октября 2008 (просмотреть исходный код)
WikiSysop (обсуждение | вклад)
м (1 версия)
← Предыдущая правка
				Текущая версия на 20:45, 13 июня 2011 (просмотреть исходный код) 
StasFomin (обсуждение | вклад) 
м (Содержимое страницы заменено на «#REDIRECT [[discopal:{{PAGENAME}}]]»)
 
				
Строка 1:
Строка 1:
− Алгоритм Прима предназначен для решения задачи + #REDIRECT [[discopal:{{PAGENAME}}]]
− [[Минимальное остовное дерево]]. + 
−   + 
− В этом алгоритме минимальный остов строится постепенно: сначала выбирается произвольная + 
− вершина, которая включается в остов, затем, на каждой итерации, к + 
− текущему остову добавляется наиболее дешевое ребро ''(u,v)'', + 
− соединяющее какую-либо вершину из остова ''u'', с какой-либо + 
− вершиной ''v'' не из остова. + 
− Алгоритм Прима, похож на [[алгоритм Дейкстры]], он также является жадным алгоритмом. + 
−   + 
− Код алгоритма, представлен в виде функции на языке [[Python]]. + 
−   + 
− Сложность алгоритма равна <m>O(n^3)</m>. + 
−   + 
− <code-python> + 
− def mst_prim(G,s): + 
−     # минимальное остовное дерево, хэш (вершина:предшествующая вершина) + 
−     MST={}                  + 
−     # хэш, граничащих с MST, узел:(стоимость) + 
−     ToVisit={s:0}     + 
−     # хэш: вершины из которых планируется включать другие вершины. + 
−     Predecessor={s:s} + 
−     # пока есть вершины, до которых не построен кратчайший путь + 
−     while ToVisit:  + 
−         # выбираем ближайшую достижимую вершину + 
−         v=argmin(ToVisit)       + 
−         MST[v]=Predecessor[v]; del ToVisit[v]; del Predecessor[v];   + 
−         # для всех соседей вершины $v$ + 
−         for w in G.neighbors(v): + 
−             # которые еще не в нашем остовном дереве      + 
−             if (w not in MST):  + 
−                 # обновляем стоимость включения в MST + 
−                 if (w not in ToVisit) or (G.get_edge(v,w) < ToVisit[w]): + 
−                     ToVisit[w] = G.get_edge(v,w) + 
−                     Predecessor[w] = v + 
−         print_frame(G, MST, ToVisit, Predecessor)                + 
−     return MST + 
− </code-python> + 
−   + 
− ==Трассировка алгоритма== + 
−   + 
− ===Итерация 1=== + 
− <neato> + 
− graph G{ rankdir=LR; overlap=scale; rankdir=TB; splines=true; + 
−         edge[len=3,fontcolor="blue",style="dashed"]; + 
−         node[fontcolor="red"]; + 
−    + 
−     + 
−             0 [label="NY", ]; + 
−         + 
−             1 [label="Moscow ($15)",  style=filled, fillcolor="yellow" ]; + 
−         + 
−             2 [label="Minsk\n Start",  shape=box, periferies=2 ]; + 
−         + 
−             3 [label="Berlin ($20)",  style=filled, fillcolor="yellow" ]; + 
−         + 
−             4 [label="Kiev ($15)",  style=filled, fillcolor="yellow" ]; + 
−         + 
−     + 
−             0 -- 1 [label="$60", ]; + 
−         + 
−             0 -- 3 [label="$50", ]; + 
−         + 
−             0 -- 4 [label="$80", ]; + 
−         + 
−             1 -- 2 [label="$15", ]; + 
−         + 
−             1 -- 3 [label="$50", ]; + 
−         + 
−             1 -- 4 [label="$10", ]; + 
−         + 
−             2 -- 3 [label="$20", ]; + 
−         + 
−             2 -- 4 [label="$15", ]; + 
−         + 
−             3 -- 4 [label="$30", ]; + 
−         + 
−     } + 
− </neato> + 
−   + 
− ===Итерация 2=== + 
− <neato> + 
− graph G{ rankdir=LR; overlap=scale; rankdir=TB; splines=true; + 
−         edge[len=3,fontcolor="blue",style="dashed"]; + 
−         node[fontcolor="red"]; + 
−    + 
−     + 
−             0 [label="NY ($60)",  style=filled, fillcolor="yellow" ]; + 
−         + 
−             1 [label="Moscow", ]; + 
−         + 
−             2 [label="Minsk\n Start",  shape=box, periferies=2 ]; + 
−         + 
−             3 [label="Berlin ($20)",  style=filled, fillcolor="yellow" ]; + 
−         + 
−             4 [label="Kiev ($10)",  style=filled, fillcolor="yellow" ]; + 
−         + 
−     + 
−             0 -- 1 [label="$60", ]; + 
−         + 
−             0 -- 3 [label="$50", ]; + 
−         + 
−             0 -- 4 [label="$80", ]; + 
−         + 
−             1 -- 2 [label="$15",  style=bold ]; + 
−         + 
−             1 -- 3 [label="$50", ]; + 
−         + 
−             1 -- 4 [label="$10", ]; + 
−         + 
−             2 -- 3 [label="$20", ]; + 
−         + 
−             2 -- 4 [label="$15", ]; + 
−         + 
−             3 -- 4 [label="$30", ]; + 
−         + 
−     } + 
− </neato> + 
−   + 
− ===Итерация 3=== + 
− <neato> + 
− graph G{ rankdir=LR; overlap=scale; rankdir=TB; splines=true; + 
−         edge[len=3,fontcolor="blue",style="dashed"]; + 
−         node[fontcolor="red"]; + 
−    + 
−     + 
−             0 [label="NY ($60)",  style=filled, fillcolor="yellow" ]; + 
−         + 
−             1 [label="Moscow", ]; + 
−         + 
−             2 [label="Minsk\n Start",  shape=box, periferies=2 ]; + 
−         + 
−             3 [label="Berlin ($20)",  style=filled, fillcolor="yellow" ]; + 
−         + 
−             4 [label="Kiev", ]; + 
−         + 
−     + 
−             0 -- 1 [label="$60", ]; + 
−         + 
−             0 -- 3 [label="$50", ]; + 
−         + 
−             0 -- 4 [label="$80", ]; + 
−         + 
−             1 -- 2 [label="$15",  style=bold ]; + 
−         + 
−             1 -- 3 [label="$50", ]; + 
−         + 
−             1 -- 4 [label="$10",  style=bold ]; + 
−         + 
−             2 -- 3 [label="$20", ]; + 
−         + 
−             2 -- 4 [label="$15", ]; + 
−         + 
−             3 -- 4 [label="$30", ]; + 
−         + 
−     } + 
− </neato> + 
−   + 
− ===Итерация 4=== + 
− <neato> + 
− graph G{ rankdir=LR; overlap=scale; rankdir=TB; splines=true; + 
−         edge[len=3,fontcolor="blue",style="dashed"]; + 
−         node[fontcolor="red"]; + 
−    + 
−     + 
−             0 [label="NY ($50)",  style=filled, fillcolor="yellow" ]; + 
−         + 
−             1 [label="Moscow", ]; + 
−         + 
−             2 [label="Minsk\n Start",  shape=box, periferies=2 ]; + 
−         + 
−             3 [label="Berlin", ]; + 
−         + 
−             4 [label="Kiev", ]; + 
−         + 
−     + 
−             0 -- 1 [label="$60", ]; + 
−         + 
−             0 -- 3 [label="$50", ]; + 
−         + 
−             0 -- 4 [label="$80", ]; + 
−         + 
−             1 -- 2 [label="$15",  style=bold ]; + 
−         + 
−             1 -- 3 [label="$50", ]; + 
−         + 
−             1 -- 4 [label="$10",  style=bold ]; + 
−         + 
−             2 -- 3 [label="$20",  style=bold ]; + 
−         + 
−             2 -- 4 [label="$15", ]; + 
−         + 
−             3 -- 4 [label="$30", ]; + 
−         + 
−     } + 
− </neato> + 
−   + 
− ===Итерация 5=== + 
− <neato> + 
− graph G{ rankdir=LR; overlap=scale; rankdir=TB; splines=true; + 
−         edge[len=3,fontcolor="blue",style="dashed"]; + 
−         node[fontcolor="red"]; + 
−    + 
−     + 
−             0 [label="NY", ]; + 
−         + 
−             1 [label="Moscow", ]; + 
−         + 
−             2 [label="Minsk\n Start",  shape=box, periferies=2 ]; + 
−         + 
−             3 [label="Berlin", ]; + 
−         + 
−             4 [label="Kiev", ]; + 
−         + 
−     + 
−             0 -- 1 [label="$60", ]; + 
−         + 
−             0 -- 3 [label="$50",  style=bold ]; + 
−         + 
−             0 -- 4 [label="$80", ]; + 
−         + 
−             1 -- 2 [label="$15",  style=bold ]; + 
−         + 
−             1 -- 3 [label="$50", ]; + 
−         + 
−             1 -- 4 [label="$10",  style=bold ]; + 
−         + 
−             2 -- 3 [label="$20",  style=bold ]; + 
−         + 
−             2 -- 4 [label="$15", ]; + 
−         + 
−             3 -- 4 [label="$30", ]; + 
−         + 
−     } + 
− </neato> + 
−   + 
−   + 
− [[Category:Алгоритмы|П]] + 
− {{replicate-from-custiswiki-to-lib}} + 

		Текущая версия на 20:45, 13 июня 2011
REDIRECT discopal:Алгоритм Прима







Источник — «http://lib.custis.ru/index.php?title=Алгоритм_Прима&oldid=27279»
 CUSTIS
       Сайт CUSTIS →
       Вакансии
       Блог команды
       Архив событий
       Архив публикаций
 Навигация
       Заглавная страница
       Свежие правки
       Случайная статья
       Справка
 Поиск
 Инструменты
       Ссылки сюда
       Связанные правки
       Спецстраницы
       Версия для печати
 Чистый HTML
 →M$WORD
 →OOffice
@@ Строка 1: / Строка 1: @@
-Алгоритм Прима предназначен для решения задачи
+#REDIRECT [[discopal:{{PAGENAME}}]]
-[[Минимальное остовное дерево]].
-В этом алгоритме минимальный остов строится постепенно: сначала выбирается произвольная
-вершина, которая включается в остов, затем, на каждой итерации, к
-текущему остову добавляется наиболее дешевое ребро ''(u,v)'',
-соединяющее какую-либо вершину из остова ''u'', с какой-либо
-вершиной ''v'' не из остова.
-Алгоритм Прима, похож на [[алгоритм Дейкстры]], он также является жадным алгоритмом.
-Код алгоритма, представлен в виде функции на языке [[Python]].
-Сложность алгоритма равна <m>O(n^3)</m>.
-<code-python>
-def mst_prim(G,s):
-    # минимальное остовное дерево, хэш (вершина:предшествующая вершина)
-    MST={}
-    # хэш, граничащих с MST, узел:(стоимость)
-    ToVisit={s:0}
-    # хэш: вершины из которых планируется включать другие вершины.
-    Predecessor={s:s}
-    # пока есть вершины, до которых не построен кратчайший путь
-    while ToVisit:
-        # выбираем ближайшую достижимую вершину
-        v=argmin(ToVisit)
-        MST[v]=Predecessor[v]; del ToVisit[v]; del Predecessor[v];
-        # для всех соседей вершины $v$
-        for w in G.neighbors(v):
-            # которые еще не в нашем остовном дереве
-            if (w not in MST):
-                # обновляем стоимость включения в MST
-                if (w not in ToVisit) or (G.get_edge(v,w) < ToVisit[w]):
-                    ToVisit[w] = G.get_edge(v,w)
-                    Predecessor[w] = v
-        print_frame(G, MST, ToVisit, Predecessor)
-    return MST
-</code-python>
-==Трассировка алгоритма==
-===Итерация 1===
-<neato>
-graph G{ rankdir=LR; overlap=scale; rankdir=TB; splines=true;
-        edge[len=3,fontcolor="blue",style="dashed"];
-        node[fontcolor="red"];
-[label="NY", ];
-[label="Moscow ($15)",  style=filled, fillcolor="yellow" ];
-[label="Minsk\n Start",  shape=box, periferies=2 ];
-[label="Berlin ($20)",  style=filled, fillcolor="yellow" ];
-[label="Kiev ($15)",  style=filled, fillcolor="yellow" ];
--- 1 [label="$60", ];
--- 3 [label="$50", ];
--- 4 [label="$80", ];
--- 2 [label="$15", ];
--- 3 [label="$50", ];
--- 4 [label="$10", ];
--- 3 [label="$20", ];
--- 4 [label="$15", ];
--- 4 [label="$30", ];
-    }
-</neato>
-===Итерация 2===
-<neato>
-graph G{ rankdir=LR; overlap=scale; rankdir=TB; splines=true;
-        edge[len=3,fontcolor="blue",style="dashed"];
-        node[fontcolor="red"];
-[label="NY ($60)",  style=filled, fillcolor="yellow" ];
-[label="Moscow", ];
-[label="Minsk\n Start",  shape=box, periferies=2 ];
-[label="Berlin ($20)",  style=filled, fillcolor="yellow" ];
-[label="Kiev ($10)",  style=filled, fillcolor="yellow" ];
--- 1 [label="$60", ];
--- 3 [label="$50", ];
--- 4 [label="$80", ];
--- 2 [label="$15",  style=bold ];
--- 3 [label="$50", ];
--- 4 [label="$10", ];
--- 3 [label="$20", ];
--- 4 [label="$15", ];
--- 4 [label="$30", ];
-    }
-</neato>
-===Итерация 3===
-<neato>
-graph G{ rankdir=LR; overlap=scale; rankdir=TB; splines=true;
-        edge[len=3,fontcolor="blue",style="dashed"];
-        node[fontcolor="red"];
-[label="NY ($60)",  style=filled, fillcolor="yellow" ];
-[label="Moscow", ];
-[label="Minsk\n Start",  shape=box, periferies=2 ];
-[label="Berlin ($20)",  style=filled, fillcolor="yellow" ];
-[label="Kiev", ];
--- 1 [label="$60", ];
--- 3 [label="$50", ];
--- 4 [label="$80", ];
--- 2 [label="$15",  style=bold ];
--- 3 [label="$50", ];
--- 4 [label="$10",  style=bold ];
--- 3 [label="$20", ];
--- 4 [label="$15", ];
--- 4 [label="$30", ];
-    }
-</neato>
-===Итерация 4===
-<neato>
-graph G{ rankdir=LR; overlap=scale; rankdir=TB; splines=true;
-        edge[len=3,fontcolor="blue",style="dashed"];
-        node[fontcolor="red"];
-[label="NY ($50)",  style=filled, fillcolor="yellow" ];
-[label="Moscow", ];
-[label="Minsk\n Start",  shape=box, periferies=2 ];
-[label="Berlin", ];
-[label="Kiev", ];
--- 1 [label="$60", ];
--- 3 [label="$50", ];
--- 4 [label="$80", ];
--- 2 [label="$15",  style=bold ];
--- 3 [label="$50", ];
--- 4 [label="$10",  style=bold ];
--- 3 [label="$20",  style=bold ];
--- 4 [label="$15", ];
--- 4 [label="$30", ];
-    }
-</neato>
-===Итерация 5===
-<neato>
-graph G{ rankdir=LR; overlap=scale; rankdir=TB; splines=true;
-        edge[len=3,fontcolor="blue",style="dashed"];
-        node[fontcolor="red"];
-[label="NY", ];
-[label="Moscow", ];
-[label="Minsk\n Start",  shape=box, periferies=2 ];
-[label="Berlin", ];
-[label="Kiev", ];
--- 1 [label="$60", ];
--- 3 [label="$50",  style=bold ];
--- 4 [label="$80", ];
--- 2 [label="$15",  style=bold ];
--- 3 [label="$50", ];
--- 4 [label="$10",  style=bold ];
--- 3 [label="$20",  style=bold ];
--- 4 [label="$15", ];
--- 4 [label="$30", ];
-    }
-</neato>
-[[Category:Алгоритмы|П]]
-{{replicate-from-custiswiki-to-lib}}

Персональные инструменты

Просмотры

Алгоритм Прима — различия между версиями

Материал из CustisWiki

Текущая версия на 20:45, 13 июня 2011