StasFomin: Содержимое страницы заменено на «#REDIRECT discopal:{{PAGENAME}}»

2011-06-13T17:45:13Z

Содержимое страницы заменено на «#REDIRECT [[discopal:{{PAGENAME}}]]»

Внесённые изменения

WikiSysop: 1 версия

2008-10-23T16:47:54Z

1 версия

StasFomin: обновление данных

2008-10-22T15:43:50Z

обновление данных

WikiSysop: 1 версия

2008-08-04T09:55:51Z

1 версия

BenderBot: реплицировано из внутренней CustisWiki

2007-03-06T04:53:53Z

реплицировано из внутренней CustisWiki

Новая страница

Алгоритм Прима предназначен для решения задачи
[[Минимальное остовное дерево]].

В этом алгоритме минимальный остов строится постепенно: сначала выбирается произвольная
вершина, которая включается в остов, затем, на каждой итерации, к
текущему остову добавляется наиболее дешевое ребро ''(u,v)'',
соединяющее какую-либо вершину из остова ''u'', с какой-либо
вершиной ''v'' не из остова.
Алгоритм Прима, похож на [[алгоритм Дейкстры]], он также является жадным алгоритмом.

Код алгоритма, представлен в виде функции на языке [[Python]].

Сложность алгоритма равна <math>O(n^3)</math>.

<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}}

StasFomin: /* Итерация 5 */

2007-03-05T13:10:29Z

‎Итерация 5

Внесённые изменения

BenderBot: реплицировано из внутренней CustisWiki

2005-12-06T04:40:33Z

реплицировано из внутренней CustisWiki

Внесённые изменения

← Предыдущая	Версия 09:55, 4 августа 2008
(не показана 1 промежуточная версия 1 участника)
(нет различий)

← Предыдущая	Версия 16:47, 23 октября 2008
(нет различий)

@@ Строка 11: / Строка 11: @@
 Код алгоритма, представлен в виде функции на языке [[Python]].
-Сложность алгоритма равна <math>O(n^3)</math>.
+Сложность алгоритма равна <m>O(n^3)</m>.
 <code-python>

Алгоритм Прима - История изменений

StasFomin: Содержимое страницы заменено на «#REDIRECT discopal:{{PAGENAME}}»

WikiSysop: 1 версия

StasFomin: обновление данных

WikiSysop: 1 версия

BenderBot: реплицировано из внутренней CustisWiki

StasFomin: /* Итерация 5 */

BenderBot: реплицировано из внутренней CustisWiki