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

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

Материал из CustisWiki

Перейти к: навигация, поиск
м (обновление данных)
м (Содержимое страницы заменено на «#REDIRECT [[discopal:{{PAGENAME}}]]»)
 
(не показана 1 промежуточная версия 1 участника)
Строка 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

  1. REDIRECT discopal:Алгоритм Прима