Алгоритм Прима — различия между версиями
BenderBot (обсуждение | вклад) м (реплицировано из внутренней CustisWiki) |
StasFomin (обсуждение | вклад) м (→Итерация 5) |
||
Строка 14: | Строка 14: | ||
<code-python> | <code-python> | ||
− | + | def mst_prim(G,s): | |
− | + | # минимальное остовное дерево, хэш (вершина:предшествующая вершина) | |
− | + | ||
− | + | ||
− | # минимальное остовное дерево | + | |
MST={} | MST={} | ||
− | + | # хэш, граничащих с MST, узел:(стоимость) | |
− | + | ToVisit={s:0} | |
− | + | # хэш: вершины из которых планируется включать другие вершины. | |
− | + | Predecessor={s:s} | |
− | v=argmin(ToVisit) | + | # пока есть вершины, до которых не построен кратчайший путь |
+ | while ToVisit: | ||
+ | # выбираем ближайшую достижимую вершину | ||
+ | v=argmin(ToVisit) | ||
MST[v]=Predecessor[v]; del ToVisit[v]; del Predecessor[v]; | MST[v]=Predecessor[v]; del ToVisit[v]; del Predecessor[v]; | ||
− | for w in G.neighbors(v): # | + | # для всех соседей вершины $v$ |
− | if (w not in MST): | + | for w in G.neighbors(v): |
+ | # которые еще не в нашем остовном дереве | ||
+ | if (w not in MST): | ||
# обновляем стоимость включения в MST | # обновляем стоимость включения в MST | ||
if (w not in ToVisit) or (G.get_edge(v,w) < ToVisit[w]): | if (w not in ToVisit) or (G.get_edge(v,w) < ToVisit[w]): | ||
ToVisit[w] = G.get_edge(v,w) | ToVisit[w] = G.get_edge(v,w) | ||
Predecessor[w] = v | Predecessor[w] = v | ||
− | + | print_frame(G, MST, ToVisit, Predecessor) | |
− | + | ||
return MST | return MST | ||
</code-python> | </code-python> | ||
− | + | ==Трассировка алгоритма== | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | < | + | ===Итерация 1=== |
− | graph G{ rankdir=TB; | + | <neato> |
− | 0 [label="NY | + | graph G{ rankdir=LR; overlap=scale; rankdir=TB; splines=true; |
− | 1 [label="Moscow( | + | edge[len=3,fontcolor="blue",style="dashed"]; |
− | 2 [label="Minsk | + | node[fontcolor="red"]; |
− | 3 [label="Berlin( | + | |
− | 4 [label="Kiev( | + | |
− | 0 -- 1[ | + | 0 [label="NY", ]; |
− | 0 -- 3[ | + | |
− | 0 -- 4[ | + | 1 [label="Moscow ($15)", style=filled, fillcolor="yellow" ]; |
− | 1 -- 2[ | + | |
− | 1 -- 3[ | + | 2 [label="Minsk\n Start", shape=box, periferies=2 ]; |
− | 1 -- 4[ | + | |
− | 2 -- 3[ | + | 3 [label="Berlin ($20)", style=filled, fillcolor="yellow" ]; |
− | 2 -- 4[ | + | |
− | 3 -- 4[ | + | 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> | ||
− | [[Category:Алгоритмы]] | + | ===Итерация 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}} | {{replicate-from-custiswiki-to-lib}} |
Версия 16:10, 5 марта 2007
Алгоритм Прима предназначен для решения задачи Минимальное остовное дерево.
В этом алгоритме минимальный остов строится постепенно: сначала выбирается произвольная вершина, которая включается в остов, затем, на каждой итерации, к текущему остову добавляется наиболее дешевое ребро (u,v), соединяющее какую-либо вершину из остова u, с какой-либо вершиной v не из остова. Алгоритм Прима, похож на алгоритм Дейкстры, он также является жадным алгоритмом.
Код алгоритма, представлен в виде функции на языке 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
Содержание
Трассировка алгоритма
Итерация 1
Итерация 2
Итерация 3
Итерация 4
Итерация 5
Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion».
Репликация: База Знаний «Заказных Информ Систем» → «Алгоритм Прима»