Участник:Anastasy/Алгоритм Диница - История изменений

Anastasy: /* Масштабируемость алгоритма и его реализации */

2017-11-30T09:12:45Z

Масштабируемость алгоритма и его реализации

← Предыдущая версия		Версия от 09:12, 30 ноября 2017
Строка 106:		Строка 106:
	<div><ul>		<div><ul>
	<li style="display: inline-block;"> [[File:Dinic scalability.png\|thumb\|none\|600px\|Рисунок 3. График зависимости производительности от количества процессов и количества вершин графа]] </li>		<li style="display: inline-block;"> [[File:Dinic scalability.png\|thumb\|none\|600px\|Рисунок 3. График зависимости производительности от количества процессов и количества вершин графа]] </li>
			<li style="display: inline-block;"> [[File:speedup_dinic.png\|thumb\|none\|600px\|Рисунок 3. График зависимости производительности от количества процессов и количества вершин графа]] </li>
	</ul></div>		</ul></div>

Anastasy: /* Масштабируемость алгоритма и его реализации */

2017-11-30T09:10:13Z

Масштабируемость алгоритма и его реализации

← Предыдущая версия		Версия от 09:10, 30 ноября 2017
Строка 103:		Строка 103:
	На графике, приведенном ниже, показана зависимость производительности (количество обработанных ребер в единицу времени) от количества процессов и количества вершин графа. Время алгоритма сильно зависит от структуры графа (она влияет на количество итераций алгоритма Диница), поэтому время выполнения алгоритма в общем случае не пропорционально размеру графа.		На графике, приведенном ниже, показана зависимость производительности (количество обработанных ребер в единицу времени) от количества процессов и количества вершин графа. Время алгоритма сильно зависит от структуры графа (она влияет на количество итераций алгоритма Диница), поэтому время выполнения алгоритма в общем случае не пропорционально размеру графа.

	~~Для большей наглядности на рисунке 4 приведен график~~ зависимости ускорения от количества процессов и количества вершин графа. ~~Так~~ как		График зависимости ускорения от количества процессов и количества вершин графа (рис. 4) более нагляден, так как количество итераций в алгоритме не зависит от количества процессов и время выполнения пропорционально числу итераций. По этому графику видно, что ускорение падает с увеличением размера графа.
	<div><ul>		<div><ul>
	<li style="display: inline-block;"> [[File:Dinic scalability.png\|thumb\|none\|600px\|Рисунок 3. График зависимости производительности от количества процессов и количества вершин графа]] </li>		<li style="display: inline-block;"> [[File:Dinic scalability.png\|thumb\|none\|600px\|Рисунок 3. График зависимости производительности от количества процессов и количества вершин графа]] </li>

Anastasy: /* Масштабируемость алгоритма и его реализации */

2017-11-30T08:44:46Z

Масштабируемость алгоритма и его реализации

← Предыдущая версия		Версия от 08:44, 30 ноября 2017
Строка 103:		Строка 103:
	На графике, приведенном ниже, показана зависимость производительности (количество обработанных ребер в единицу времени) от количества процессов и количества вершин графа. Время алгоритма сильно зависит от структуры графа (она влияет на количество итераций алгоритма Диница), поэтому время выполнения алгоритма в общем случае не пропорционально размеру графа.		На графике, приведенном ниже, показана зависимость производительности (количество обработанных ребер в единицу времени) от количества процессов и количества вершин графа. Время алгоритма сильно зависит от структуры графа (она влияет на количество итераций алгоритма Диница), поэтому время выполнения алгоритма в общем случае не пропорционально размеру графа.

	[[File:Dinic scalability.png\|600px]]		Для большей наглядности на рисунке 4 приведен график зависимости ускорения от количества процессов и количества вершин графа. Так как
			<div><ul>
			<li style="display: inline-block;"> [[File:Dinic scalability.png\|thumb\|none\|600px\|Рисунок 3. График зависимости производительности от количества процессов и количества вершин графа]] </li>
			</ul></div>

	=== Динамические характеристики и эффективность реализации алгоритма ===		=== Динамические характеристики и эффективность реализации алгоритма ===

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

2017-11-29T18:52:34Z

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

← Предыдущая версия		Версия от 18:52, 29 ноября 2017
Строка 108:		Строка 108:
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===
	=== Существующие реализации алгоритма ===		=== Существующие реализации алгоритма ===
			* Python: [https://networkx.github.io NetworkX] (функция <code>[https://networkx.github.io/documentation/stable/reference/algorithms/generated/networkx.algorithms.flow.dinitz.html dinitz]</code>): алгоритм Диница

	== Литература ==		== Литература ==
	<references />		<references />

Anastasy: /* Информационный граф */

2017-11-29T18:00:16Z

Информационный граф

← Предыдущая версия		Версия от 18:00, 29 ноября 2017
Строка 55:		Строка 55:
	=== Информационный граф ===		=== Информационный граф ===
	<div><ul>		<div><ul>
	<li style="display: inline-block;"> [[File:dinic.png\|thumb\|none\|500px\|Информационный граф алгоритма Диница]] </li>		<li style="display: inline-block;"> [[File:dinic.png\|thumb\|none\|500px\|Рисунок 1. Информационный граф алгоритма Диница]] </li>
	<li style="display: inline-block;"> [[File:bfs.png\|thumb\|none\|650px\|Информационный граф поиска в ширину]] </li>		<li style="display: inline-block;"> [[File:bfs.png\|thumb\|none\|650px\|Рисунок 2. Информационный граф поиска в ширину]] </li>
	</ul></div>		</ul></div>
	Для алгоритма Диница:		Для алгоритма Диница:

Anastasy: /* Масштабируемость алгоритма и его реализации */

2017-11-29T17:59:22Z

Масштабируемость алгоритма и его реализации

← Предыдущая версия		Версия от 17:59, 29 ноября 2017
Строка 101:		Строка 101:
	* число процессоров <math>[2^k, k = 0, 1, ...7]</math>;		* число процессоров <math>[2^k, k = 0, 1, ...7]</math>;
	* число вершин графа [5 000:20 000] с шагом 5000. Количество ребер одинаково для всех графов и равно 2 500 000.		* число вершин графа [5 000:20 000] с шагом 5000. Количество ребер одинаково для всех графов и равно 2 500 000.
			На графике, приведенном ниже, показана зависимость производительности (количество обработанных ребер в единицу времени) от количества процессов и количества вершин графа. Время алгоритма сильно зависит от структуры графа (она влияет на количество итераций алгоритма Диница), поэтому время выполнения алгоритма в общем случае не пропорционально размеру графа.

	[[File:Dinic scalability.png\|600px]]		[[File:Dinic scalability.png\|600px]]

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

2017-11-29T16:09:24Z

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

← Предыдущая версия		Версия от 16:09, 29 ноября 2017
Строка 5:		Строка 5:
	== Постановка задачи ==		== Постановка задачи ==
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===
	Алгоритм Диница <ref name="Dinic">Диниц, Е. А. “Алгоритм решения задачи о максимальном потоке в сети со степенной оценкой.” Доклады АН СССР 194, no. 4 (1970): 754–57</ref> — полиномиальный алгоритм, предназначенный для поиска [[Поиск максимального потока в транспортной сети\| максимального потока в транспортной сети]]. Он был предложен советским учёным Ефимом Диницем в 1970 году. Временная сложность алгоритма <math>O(nm^2)</math>, где <math>m</math> — число ребер, а <math>n</math> — число вершин.		Алгоритм Диница <ref name="Dinic">Диниц, Е. А. “Алгоритм решения задачи о максимальном потоке в сети со степенной оценкой.” Доклады АН СССР 194, no. 4 (1970): 754–57</ref> — полиномиальный алгоритм, предназначенный для поиска [[Поиск максимального потока в транспортной сети\| максимального потока в транспортной сети]]. Он был предложен советским учёным Ефимом Диницем в 1970 году. Временная сложность алгоритма <math>O(n^2m)</math>, где <math>m</math> — число ребер, а <math>n</math> — число вершин.

	Основная идея алгоритма состоит в том, чтобы итеративно увеличивать величину потока вдоль некоторых путей из истока в сток.		Основная идея алгоритма состоит в том, чтобы итеративно увеличивать величину потока вдоль некоторых путей из истока в сток.

Anastasy: /* Масштабируемость алгоритма и его реализации */

2017-11-28T11:44:56Z

Масштабируемость алгоритма и его реализации

← Предыдущая версия		Версия от 11:44, 28 ноября 2017
Строка 100:		Строка 100:

	* число процессоров <math>[2^k, k = 0, 1, ...7]</math>;		* число процессоров <math>[2^k, k = 0, 1, ...7]</math>;
	* число вершин графа [~~5000~~:~~20000~~] с шагом 5000. Количество ребер одинаково для всех графов и равно ~~2500000~~.		* число вершин графа [5 000:20 000] с шагом 5000. Количество ребер одинаково для всех графов и равно 2 500 000.

	[[File:Dinic scalability.png\|600px]]		[[File:Dinic scalability.png\|600px]]

Anastasy: /* Масштабируемость алгоритма и его реализации */

2017-11-28T11:44:37Z

Масштабируемость алгоритма и его реализации

← Предыдущая версия		Версия от 11:44, 28 ноября 2017
Строка 97:		Строка 97:
	=== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===
	=== Масштабируемость алгоритма и его реализации ===		=== Масштабируемость алгоритма и его реализации ===
			Набор и границы значений изменяемых параметров запуска реализации алгоритма:

			* число процессоров <math>[2^k, k = 0, 1, ...7]</math>;
			* число вершин графа [5000:20000] с шагом 5000. Количество ребер одинаково для всех графов и равно 2500000.

			[[File:Dinic scalability.png\|600px]]

	=== Динамические характеристики и эффективность реализации алгоритма ===		=== Динамические характеристики и эффективность реализации алгоритма ===
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===

Anastasy: /* Свойства алгоритма */

2017-11-28T11:36:39Z

Свойства алгоритма

← Предыдущая версия		Версия от 11:36, 28 ноября 2017
Строка 90:		Строка 90:

	=== Свойства алгоритма ===		=== Свойства алгоритма ===
			В зависимости от порядка обработки ребер графа, вычисленные блокирующие потоки на соответствующих итерациях могут быть различны, кроме того, может поменяться количество итераций алгоритма Диница.

	== Программная реализация алгоритма ==		== Программная реализация алгоритма ==