|
|
| (не показана 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}}
| + | |
