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

ASA в 07:13, 6 июля 2022

2022-07-06T07:13:56Z

← Предыдущая версия		Версия от 07:13, 6 июля 2022
Строка 36:		Строка 36:
	== Программная реализация алгоритма ==		== Программная реализация алгоритма ==
	=== Особенности реализации последовательного алгоритма ===		=== Особенности реализации последовательного алгоритма ===
	~~=== Локальность данных и вычислений ===~~
	~~==== Локальность реализации алгоритма ====~~
	~~===== Структура обращений в память и качественная оценка локальности =====~~
	~~===== Количественная оценка локальности =====~~
	=== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===
	=== ~~Масштабируемость алгоритма и его реализации ===~~		=== Результаты прогонов ===
	~~==== Масштабируемость алгоритма ====~~
	~~==== Масштабируемость реализации алгоритма ====~~
	~~=== Динамические характеристики и эффективность реализации алгоритма~~ ===
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===
	~~=== Существующие реализации алгоритма ===~~

	* C++: [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/prim_minimum_spanning_tree.html prim_minimum_spanning_tree]</code>), сложность <math>O(m \ln n)</math>.
	* Java: [http://jgrapht.org JGraphT] (класс <code>[http://jgrapht.org/javadoc/org/jgrapht/alg/PrimMinimumSpanningTree.html PrimMinimumSpanningTree]</code>).

	== Литература ==		== Литература ==

ASA в 13:48, 14 марта 2018

2018-03-14T13:48:19Z

← Предыдущая версия		Версия от 13:48, 14 марта 2018
Строка 56:		Строка 56:

	[[Категория:Начатые статьи]]		[[Категория:Начатые статьи]]

			[[en:Prim's algorithm]]

ASA в 14:13, 6 марта 2018

2018-03-06T14:13:06Z

← Предыдущая версия		Версия от 14:13, 6 марта 2018
Строка 1:		Строка 1:
			{{level-a}}

	== Свойства и структура алгоритма ==		== Свойства и структура алгоритма ==
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===

ASA в 11:16, 29 июля 2015

2015-07-29T11:16:33Z

← Предыдущая версия		Версия от 11:16, 29 июля 2015
Строка 1:		Строка 1:
	== Свойства и структура ~~алгоритмов~~ ==		== Свойства и структура алгоритма ==
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===

	'''Алгоритм Прима'''<ref>Prim, R C. “Shortest Connection Networks and Some Generalizations.” Bell System Technical Journal 36, no. 6 (November 1957): 1389–1401. doi:10.1002/j.1538-7305.1957.tb01515.x.</ref><ref>Dijkstra, E W. “A Note on Two Problems in Connexion with Graphs.” Numerische Mathematik 1, no. 1 (December 1959): 269–71. doi:10.1007/BF01386390.</ref> предназначен для решения [[Построение минимального остовного дерева (MST)\|задачи о построении минимального остовного дерева]] во взвешенном неориентированном графе.		'''Алгоритм Прима'''<ref>Prim, R C. “Shortest Connection Networks and Some Generalizations.” Bell System Technical Journal 36, no. 6 (November 1957): 1389–1401. doi:10.1002/j.1538-7305.1957.tb01515.x.</ref><ref>Dijkstra, E W. “A Note on Two Problems in Connexion with Graphs.” Numerische Mathematik 1, no. 1 (December 1959): 269–71. doi:10.1007/BF01386390.</ref> предназначен для решения [[Построение минимального остовного дерева (MST)\|задачи о построении минимального остовного дерева]] во взвешенном неориентированном графе.

	=== Математическое описание ===		=== Математическое описание алгоритма ===

	Пусть задан связный неориентированный граф <math>G = (V, E)</math> с весами рёбер <math>f(e)</math>. Предполагается, что веса всех рёбер различны (если это не так, то можно упорядочить рёбра сначала по весу, а потом по номеру).		Пусть задан связный неориентированный граф <math>G = (V, E)</math> с весами рёбер <math>f(e)</math>. Предполагается, что веса всех рёбер различны (если это не так, то можно упорядочить рёбра сначала по весу, а потом по номеру).
Строка 16:		Строка 16:
	=== Вычислительное ядро алгоритма ===		=== Вычислительное ядро алгоритма ===
	=== Макроструктура алгоритма ===		=== Макроструктура алгоритма ===
	=== ~~Описание схемы~~ реализации последовательного алгоритма ===		=== Схема реализации последовательного алгоритма ===
	=== Последовательная сложность алгоритма ===		=== Последовательная сложность алгоритма ===

Строка 28:		Строка 28:

	=== Информационный граф ===		=== Информационный граф ===
	=== ~~Описание ресурса~~ параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===
	=== ~~Описание входных~~ и ~~выходных данных~~ ===		=== Входные и выходные данные алгоритма ===
	=== Свойства алгоритма===		=== Свойства алгоритма ===
	== Программная реализация ~~алгоритмов~~ ==
			== Программная реализация алгоритма ==
	=== Особенности реализации последовательного алгоритма ===		=== Особенности реализации последовательного алгоритма ===
	=== ~~Описание локальности~~ данных и вычислений ===		=== Локальность данных и вычислений ===
	=== Возможные способы и особенности реализации ~~параллельного~~ алгоритма ===		==== Локальность реализации алгоритма ====
			===== Структура обращений в память и качественная оценка локальности =====
			===== Количественная оценка локальности =====
			=== Возможные способы и особенности параллельной реализации алгоритма ===
	=== Масштабируемость алгоритма и его реализации ===		=== Масштабируемость алгоритма и его реализации ===
			==== Масштабируемость алгоритма ====
			==== Масштабируемость реализации алгоритма ====
	=== Динамические характеристики и эффективность реализации алгоритма ===		=== Динамические характеристики и эффективность реализации алгоритма ===
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===
Строка 46:		Строка 52:

	<references />		<references />

			[[Категория:Начатые статьи]]

Daryin: /* Математическое описание */

2015-07-08T13:23:10Z

Математическое описание

← Предыдущая версия		Версия от 13:23, 8 июля 2015
Строка 8:		Строка 8:
	Пусть задан связный неориентированный граф <math>G = (V, E)</math> с весами рёбер <math>f(e)</math>. Предполагается, что веса всех рёбер различны (если это не так, то можно упорядочить рёбра сначала по весу, а потом по номеру).		Пусть задан связный неориентированный граф <math>G = (V, E)</math> с весами рёбер <math>f(e)</math>. Предполагается, что веса всех рёбер различны (если это не так, то можно упорядочить рёбра сначала по весу, а потом по номеру).

	Алгоритм ~~Борувки~~ основан на следующих двух свойствах задачи:		Алгоритм Прима основан на следующих двух свойствах задачи:
	* '''Минимальное ребро фрагмента'''. Пусть <math>F</math> – фрагмент минимального остовного дерева и <math>e_F</math> – ребро наименьшего веса, исходящее из <math>F</math> (т.е. ровно один его конец является вершиной из <math>F</math>). Если ребро <math>e_F</math> единственно, то оно принадлежит минимальному остовному дереву.		* '''Минимальное ребро фрагмента'''. Пусть <math>F</math> – фрагмент минимального остовного дерева и <math>e_F</math> – ребро наименьшего веса, исходящее из <math>F</math> (т.е. ровно один его конец является вершиной из <math>F</math>). Если ребро <math>e_F</math> единственно, то оно принадлежит минимальному остовному дереву.
	* '''Схлопывание фрагментов'''. Пусть <math>F</math> – фрагмент минимального остовного дерева графа <math>G</math>, а граф <math>G'</math> получен из <math>G</math> склеиванием вершин, принадлежащих <math>F</math>. Тогда объединение <math>F</math> и минимального остовного дерева графа <math>G'</math> даёт минимальное остовное дерево исходного графа <math>G</math>.		* '''Схлопывание фрагментов'''. Пусть <math>F</math> – фрагмент минимального остовного дерева графа <math>G</math>, а граф <math>G'</math> получен из <math>G</math> склеиванием вершин, принадлежащих <math>F</math>. Тогда объединение <math>F</math> и минимального остовного дерева графа <math>G'</math> даёт минимальное остовное дерево исходного графа <math>G</math>.

Daryin: /* Математическое описание */

2015-07-08T13:22:58Z

Математическое описание

← Предыдущая версия		Версия от 13:22, 8 июля 2015
Строка 5:		Строка 5:

	=== Математическое описание ===		=== Математическое описание ===

			Пусть задан связный неориентированный граф <math>G = (V, E)</math> с весами рёбер <math>f(e)</math>. Предполагается, что веса всех рёбер различны (если это не так, то можно упорядочить рёбра сначала по весу, а потом по номеру).

			Алгоритм Борувки основан на следующих двух свойствах задачи:
			* '''Минимальное ребро фрагмента'''. Пусть <math>F</math> – фрагмент минимального остовного дерева и <math>e_F</math> – ребро наименьшего веса, исходящее из <math>F</math> (т.е. ровно один его конец является вершиной из <math>F</math>). Если ребро <math>e_F</math> единственно, то оно принадлежит минимальному остовному дереву.
			* '''Схлопывание фрагментов'''. Пусть <math>F</math> – фрагмент минимального остовного дерева графа <math>G</math>, а граф <math>G'</math> получен из <math>G</math> склеиванием вершин, принадлежащих <math>F</math>. Тогда объединение <math>F</math> и минимального остовного дерева графа <math>G'</math> даёт минимальное остовное дерево исходного графа <math>G</math>.

			В начале работы алгоритма создаётся фрагмент, содержащий одну произвольную вершину графа. На каждом шаге выбирается ребро минимального веса, исходящее из текущего фрагмента. Это ребро помещается в минимальное остовное дерево, а его конец добавляется в текущий фрагмент. Процесс останавливается, когда у текущего фрагмента не остаётся исходящих рёбер. Тогда выбирается одна из ранее не посещённых вершин графа, и начиная с неё «выращивается» новый фрагмент. Алгоритм прекращает работу, когда посещены все вершины графа.

	=== Вычислительное ядро алгоритма ===		=== Вычислительное ядро алгоритма ===
	=== Макроструктура алгоритма ===		=== Макроструктура алгоритма ===

Daryin: /* Существующие реализации алгоритма */

2015-06-11T19:50:34Z

Существующие реализации алгоритма

← Предыдущая версия		Версия от 19:50, 11 июня 2015
Строка 31:		Строка 31:
	=== Существующие реализации алгоритма ===		=== Существующие реализации алгоритма ===

	* [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/prim_minimum_spanning_tree.html prim_minimum_spanning_tree]</code>), сложность <math>O(m \ln n)</math>.		* C++: [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/prim_minimum_spanning_tree.html prim_minimum_spanning_tree]</code>), сложность <math>O(m \ln n)</math>.
	* Java: [http://jgrapht.org JGraphT] (класс <code>[http://jgrapht.org/javadoc/org/jgrapht/alg/PrimMinimumSpanningTree.html PrimMinimumSpanningTree]</code>).		* Java: [http://jgrapht.org JGraphT] (класс <code>[http://jgrapht.org/javadoc/org/jgrapht/alg/PrimMinimumSpanningTree.html PrimMinimumSpanningTree]</code>).

Daryin: /* Существующие реализации алгоритма */

2015-06-11T19:50:24Z

Существующие реализации алгоритма

← Предыдущая версия		Версия от 19:50, 11 июня 2015
Строка 32:		Строка 32:

	* [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/prim_minimum_spanning_tree.html prim_minimum_spanning_tree]</code>), сложность <math>O(m \ln n)</math>.		* [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/prim_minimum_spanning_tree.html prim_minimum_spanning_tree]</code>), сложность <math>O(m \ln n)</math>.
			* Java: [http://jgrapht.org JGraphT] (класс <code>[http://jgrapht.org/javadoc/org/jgrapht/alg/PrimMinimumSpanningTree.html PrimMinimumSpanningTree]</code>).

	== Литература ==		== Литература ==

	<references />		<references />

Daryin: /* Общее описание алгоритма */

2015-06-11T14:41:12Z

Общее описание алгоритма

← Предыдущая версия		Версия от 14:41, 11 июня 2015
Строка 2:		Строка 2:
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===

	Алгоритм Прима<ref>Prim, R C. “Shortest Connection Networks and Some Generalizations.” Bell System Technical Journal 36, no. 6 (November 1957): 1389–1401. doi:10.1002/j.1538-7305.1957.tb01515.x.</ref><ref>Dijkstra, E W. “A Note on Two Problems in Connexion with Graphs.” Numerische Mathematik 1, no. 1 (December 1959): 269–71. doi:10.1007/BF01386390.</ref> предназначен для решения [[Построение минимального остовного дерева (MST)\|задачи о построении минимального остовного дерева]] во взвешенном неориентированном графе.		'''Алгоритм Прима'''<ref>Prim, R C. “Shortest Connection Networks and Some Generalizations.” Bell System Technical Journal 36, no. 6 (November 1957): 1389–1401. doi:10.1002/j.1538-7305.1957.tb01515.x.</ref><ref>Dijkstra, E W. “A Note on Two Problems in Connexion with Graphs.” Numerische Mathematik 1, no. 1 (December 1959): 269–71. doi:10.1007/BF01386390.</ref> предназначен для решения [[Построение минимального остовного дерева (MST)\|задачи о построении минимального остовного дерева]] во взвешенном неориентированном графе.

	=== Математическое описание ===		=== Математическое описание ===

Daryin: /* Последовательная сложность алгоритма */

2015-06-10T23:06:02Z

Последовательная сложность алгоритма

← Предыдущая версия		Версия от 23:06, 10 июня 2015
Строка 9:		Строка 9:
	=== Описание схемы реализации последовательного алгоритма ===		=== Описание схемы реализации последовательного алгоритма ===
	=== Последовательная сложность алгоритма ===		=== Последовательная сложность алгоритма ===

			Основной объём вычислений в алгоритме Прима приходится на поддержание набора рёбер, выходящих из текущего фрагмента. Необходимо добавлять новые рёбра или вершины в набор, и находить ребро с наименьшим весом.

			* При использовании списков вершин сложность <math>O(n^2)</math>.
			* При использовании бинарной кучи рёбер сложность <math>O(m \ln m)</math>.
			* При использовании бинарной кучи вершин и сортировке рёбер у каждой вершины сложность <math>O(m \ln n)</math>.
			* При использовании быстрой кучи<ref>Navarro, Gonzalo, and Rodrigo Paredes. “On Sorting, Heaps, and Minimum Spanning Trees.” Algorithmica 57, no. 4 (March 23, 2010): 585–620. doi:10.1007/s00453-010-9400-6.</ref> сложность <math>O(m + n \ln^2 n)</math>.
			* При использовании фибоначчиевой кучи<ref>Fredman, Michael L, and Robert Endre Tarjan. “Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms.” Journal of the ACM 34, no. 3 (July 1987): 596–615. doi:10.1145/28869.28874.</ref> сложность <math>O(m + n \ln n)</math>.

	=== Информационный граф ===		=== Информационный граф ===
	=== Описание ресурса параллелизма алгоритма ===		=== Описание ресурса параллелизма алгоритма ===