"Поиск кратчайшего пути" - История изменений

Triada63: /* Тема исследования группы */

2011-12-29T17:28:04Z

Тема исследования группы

Triada63: /* Раскрытие вопроса */

2011-12-29T17:27:31Z

Раскрытие вопроса

Triada63: /* Раскрытие вопроса */

2011-12-29T17:27:22Z

Раскрытие вопроса

Triada63: /* Раскрытие вопроса */

2011-12-29T17:27:09Z

Раскрытие вопроса

Triada63: /* Раскрытие вопроса */

2011-12-29T17:25:02Z

Раскрытие вопроса

Triada63: /* Раскрытие вопроса */

2011-12-29T17:23:24Z

Раскрытие вопроса

Triada63 в 17:17, 29 декабря 2011

2011-12-29T17:17:53Z

Triada63: /* Раскрытие вопроса */

2011-12-29T17:15:49Z

Раскрытие вопроса

Triada63: Новая: == Название проекта == '''Поиск кратчайшего пути''' == Авторы и участники проекта == Абашин Павел == Тема и...

2011-12-29T17:08:20Z

Новая: == Название проекта == '''Поиск кратчайшего пути''' == Авторы и участники проекта == Абашин Павел == Тема и...

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

== Название проекта ==
'''Поиск кратчайшего пути'''

== Авторы и участники проекта ==
Абашин Павел

== Тема исследования группы ==

Преимущества и недостатки алгоритмов

== Проблемный вопрос (вопрос для исследования) ==

Каковы преимущества и недостатки алгоритмов поиска кратчайшего пути?

== Раскрытие вопроса ==

<table>

<tr>
<td>[[Изображение:2u43s.gif]]</td>
<td>
"Искра" - кодовое наименование плана операции советских войск по прорыву блокады Ленинграда. План предусматривал одновременными встречными ударами войск Ленинградского фронта с запада и Волховского с востока в направлении на Синявино и Рабочий поселок № 5 во взаимодействии с Балтийским флотом разгромить группировку противника южнее Ладожского озера, ликвидировать шлиссельбургско-синявинский выступ и тем самым обеспечить сухопутное сообщение Ленинграда со страной...

12 января 1943 соединения 67-й армии Ленинградского фронта (командующий генерал-лейтенант Л. А. Говоров), 2-й ударной и части сил 8-й армии Волховского фронта (командующий генерал армии К. А. Мерецков) по приказу Ставки ВГК приступили к осуществлению операции "Искра"...

18 января 1943 года войска фронта соединились в районах Рабочих поселков № 5 и № 1. Блокада Ленинграда была прорвана. Между Ладожским озером и линией фронта образовался коридор шириной 8-11 км.

12 - 30 января 1943 г.

Стратегическая наступательная операция по прорыву блокады Ленинграда проводилась силами ударных группировок Ленинградского и Волховского фронтов при содействии части сил Балтийского флота и авиации дальнего действия.

Продолжительность - 19 суток. Ширина фронта боевых действий - 45 км.

Глубина продвижения советских войск - 60 км. Среднесуточные темпы наступления - 3-3,5 км.
</td>
</tr>

</table>

<center>'''Боевой состав, численность войск и людские потери'''</center>
<TABLE cellSpacing=1 cellPadding=2 border=1 width=760 align=center>
<TR vAlign=top align=center><TD rowSpan=2><B>Наименование объединений и сроки их участия в операции</B></TD>
<TD colSpan=2><B>Боевой состав и численность войск к началу операции</B></TD>
<TD colSpan=4><B>Людские потери в операции (чел.)</B></TD></TR>
<TR vAlign=top align=center><TD><B>Количество соединений</B></TD>
<TD><B>Численность</B></TD><TD><B>Безвозвратные</B></TD><TD><B>Санитарные</B></TD><TD><B>Всего</B></TD><TD><B>Среднесуточные</B></TD></TR>
<TR vAlign=top align=center>
<TD align=left>Ленинградский фронт (весь период) - 67-я армия - 13-я воздушная армия (летный состав)</TD>
<TD>сд-6, сбр-7, тбр-3, УР-1</TD>
<TD>133300</TD><TD>12320</TD><TD>28944</TD><TD>41264</TD><TD>2172</TD></TR>
<TR vAlign=top align=center>
<TD align=left>Волховский фронт (весь период) - 2-я ударная армия - 8-я армия - 14-я воздушная армия (летный состав)</TD>
<TD>сд-15 сбр-7 тбр-4</TD><TD>169500</TD><TD>21620</TD><TD>52198</TD><TD>73818</TD><TD>3885</TD></TR>
<TR vAlign=top align=center>
<TD>Итого</TD><TD>Дивизий-21, бригад-21, УР-1</TD><TD>302800</TD><TD>33940 <BR>11,2%</TD><TD>81142</TD><TD>115082</TD><TD>6057</TD></TR>
</TABLE>

'''Результаты операции'''. В ходе наступления войска Ленинградского и Волховского фронтов прорвали вражескую блокаду Ленинграда, создав коридор, шириной 8-11 км, позволивший восстановить сухопутные коммуникации города со страной. Южное побережье Ладожского озера было очищено от противника. Несмотря на то, что дальнейшее наступление советских войск развития не получило, операция по прорыву блокады имела важное стратегическое значение и явилась переломным моментом в битве за Ленинград. Замысел врага задушить голодом защитников и жителей города был сорван. Инициатива ведения боевых действий на этом направлении перешла к Красной Армии.

[[Категория:ТГУ]]
[[Категория:TEO2]]

← Предыдущая		Версия 17:27, 29 декабря 2011
Строка 25:		Строка 25:

	В итоге среди других алгоритмов выделяется алгоритм Дейкстры, у него больше всего достоинств и меньше всего недостатков, это:		В итоге среди других алгоритмов выделяется алгоритм Дейкстры, у него больше всего достоинств и меньше всего недостатков, это:
		+
	+высокая скорость работы		+высокая скорость работы

@@ Строка 26: / Строка 26: @@
 В итоге среди других алгоритмов выделяется алгоритм Дейкстры, у него больше всего достоинств и меньше всего недостатков, это:
 +высокая скорость работы
 +просчет ребер с отрицательным весом
 +высокая точность результата
 -сложность понимания
 [[Категория:ТГУ]]
 [[Категория:TEO2]]

@@ Строка 24: / Строка 24: @@
 Алгоритм Форда-Беллмана позволяет решить задачу о кратчайшем пути из фиксированного истока в общем случае, когда вес любого ребра может быть отрицательным. Этот алгоритм отличается своей простотой. К его достоинствам также относится то, что он определяет, содержится ли в графе цикл с отрицательным весом, достижимый из истока. Алгоритм Дейкстры характеризуется меньшим временем выполнения, чем алгоритм Форда-Беллмана, и менее претезателен чем другие алгоритмы. Кроме того, приведен алгоритм динамического программирования — алгоритм Флойда-Уоршалла (Floyd-Warshall), который позволяет решить задачу о поиске кратчайших путей между всеми парами вершин, он очень прост в освоении и с него начинают изучение темы алгоритмов поиска кратчайшего пути, но у него очень низкая скорость работы и в нем не предусмотрен просчет ребер с отрицательным весом.
-В итоге среди других алгоритмов выделяется алгоритм Дейкстры, у него больше всего достоинств и меньше всего недостатков.
+В итоге среди других алгоритмов выделяется алгоритм Дейкстры, у него больше всего достоинств и меньше всего недостатков, это:
 [[Категория:ТГУ]]
 [[Категория:TEO2]]

@@ Строка 22: / Строка 22: @@
 [[Изображение:graph.jpg]]
-Алгоритм Форда-Беллмана позволяет решить задачу о кратчайшем пути из фиксированного истока в общем случае, когда вес любого ребра может быть отрицательным. Этот алгоритм отличается своей простотой. К его достоинствам также относится то, что он определяет, содержится ли в графе цикл с отрицательным весом, достижимый из истока. Также в проекте описывается алгоритм Дейкстры, который характеризуется меньшим временем выполнения, чем алгоритм Форда-Беллмана, и менее претезателен чем другие алгоритмы. Кроме того, приведен алгоритм динамического программирования — алгоритм Флойда-Уоршалла (Floyd-Warshall), который позволяет решить задачу о поиске кратчайших путей между всеми парами вершин.
+Алгоритм Форда-Беллмана позволяет решить задачу о кратчайшем пути из фиксированного истока в общем случае, когда вес любого ребра может быть отрицательным. Этот алгоритм отличается своей простотой. К его достоинствам также относится то, что он определяет, содержится ли в графе цикл с отрицательным весом, достижимый из истока. Алгоритм Дейкстры характеризуется меньшим временем выполнения, чем алгоритм Форда-Беллмана, и менее претезателен чем другие алгоритмы. Кроме того, приведен алгоритм динамического программирования — алгоритм Флойда-Уоршалла (Floyd-Warshall), который позволяет решить задачу о поиске кратчайших путей между всеми парами вершин, он очень прост в освоении и с него начинают изучение темы алгоритмов поиска кратчайшего пути, но у него очень низкая скорость работы и в нем не предусмотрен просчет ребер с отрицательным весом.
 [[Категория:ТГУ]]
 [[Категория:TEO2]]

← Предыдущая		Версия 17:15, 29 декабря 2011
Строка 14:		Строка 14:

	== Раскрытие вопроса ==		== Раскрытие вопроса ==
		+	Кратчайший путь рассматривается при помощи некоторого математического объекта, называемого графом.
		+	Существуют несколько наиболее эффективных алгоритмов нахождения кратчайшего пути:
		+	#алгоритм Дейкстры (используется для нахождения оптимального маршрута между двумя вершинами);
		+	#алгоритм Форда-Беллмана;
		+	#алгоритм Шимбелла.

		+	Алгоритм Форда-Беллмана позволяет решить задачу о кратчайшем пути из фиксированного истока в общем случае, когда вес любого ребра может быть отрицательным. Этот алгоритм отличается своей простотой. К его достоинствам также относится то, что он определяет, содержится ли в графе цикл с отрицательным весом, достижимый из истока. Также в проекте описывается алгоритм Дейкстры, который характеризуется меньшим временем выполнения, чем алгоритм Форда-Беллмана, и менее претезателен чем другие алгоритмы. Кроме того, приведен алгоритм динамического программирования — алгоритм Флойда-Уоршалла (Floyd-Warshall), который позволяет решить задачу о поиске кратчайших путей между всеми парами вершин.
		+	[[Изображение:graph.jpg]]

@@ Строка 7: / Строка 7: @@
 == Тема исследования группы ==
-  Преимущества и недостатки алгоритмов
+  Преимущества и недостатки алгоритмов поиска кратчайшего пути
 == Проблемный вопрос (вопрос для исследования) ==

@@ Строка 20: / Строка 20: @@
 #алгоритм Шимбелла.
 [[Изображение:graph.jpg]]
+Алгоритм Форда-Беллмана позволяет решить задачу о кратчайшем пути из фиксированного истока в общем случае, когда вес любого ребра может быть отрицательным. Этот алгоритм отличается своей простотой. К его достоинствам также относится то, что он определяет, содержится ли в графе цикл с отрицательным весом, достижимый из истока. Также в проекте описывается алгоритм Дейкстры, который характеризуется меньшим временем выполнения, чем алгоритм Форда-Беллмана, и менее претезателен чем другие алгоритмы. Кроме того, приведен алгоритм динамического программирования — алгоритм Флойда-Уоршалла (Floyd-Warshall), который позволяет решить задачу о поиске кратчайших путей между всеми парами вершин.
-<table>
-−
-<tr>
-<td>[[Изображение:2u43s.gif]]</td>
-    <td>
-"Искра" - кодовое наименование плана операции советских войск по прорыву блокады Ленинграда. План предусматривал одновременными встречными ударами войск Ленинградского фронта с запада и Волховского с востока в направлении на Синявино и Рабочий поселок № 5 во взаимодействии с Балтийским флотом разгромить группировку противника южнее Ладожского озера, ликвидировать шлиссельбургско-синявинский выступ и тем самым обеспечить сухопутное сообщение Ленинграда со страной...
-−
-января 1943 соединения 67-й армии Ленинградского фронта (командующий генерал-лейтенант Л. А. Говоров), 2-й ударной и части сил 8-й армии Волховского фронта (командующий генерал армии К. А. Мерецков) по приказу Ставки ВГК приступили к осуществлению операции "Искра"...
-−
-января 1943 года войска фронта соединились в районах Рабочих поселков № 5 и № 1. Блокада Ленинграда была прорвана. Между Ладожским озером и линией фронта образовался коридор шириной 8-11 км.
-−
-- 30 января 1943 г.
-−
-Стратегическая наступательная операция по прорыву блокады Ленинграда проводилась силами ударных группировок Ленинградского и Волховского фронтов при содействии части сил Балтийского флота и авиации дальнего действия.
-−
-Продолжительность - 19 суток. Ширина фронта боевых действий - 45 км.
-−
-Глубина продвижения советских войск - 60 км. Среднесуточные темпы наступления - 3-3,5 км.
-</td>
-</tr>
-−
-</table>
-−
-<center>'''Боевой состав, численность войск и людские потери'''</center>
-<TABLE cellSpacing=1 cellPadding=2 border=1 width=760 align=center>
-<TR vAlign=top align=center><TD rowSpan=2><B>Наименование объединений и сроки их участия в операции</B></TD>
-<TD colSpan=2><B>Боевой состав и численность войск к началу операции</B></TD>
-<TD colSpan=4><B>Людские потери в операции (чел.)</B></TD></TR>
-<TR vAlign=top align=center><TD><B>Количество соединений</B></TD>
-<TD><B>Численность</B></TD><TD><B>Безвозвратные</B></TD><TD><B>Санитарные</B></TD><TD><B>Всего</B></TD><TD><B>Среднесуточные</B></TD></TR>
-<TR vAlign=top align=center>
-<TD align=left>Ленинградский фронт (весь период) - 67-я армия - 13-я воздушная армия (летный состав)</TD>
-<TD>сд-6, сбр-7, тбр-3, УР-1</TD>
-<TD>133300</TD><TD>12320</TD><TD>28944</TD><TD>41264</TD><TD>2172</TD></TR>
-<TR vAlign=top align=center>
-<TD align=left>Волховский фронт (весь период) - 2-я ударная армия - 8-я армия - 14-я воздушная армия (летный состав)</TD>
-<TD>сд-15 сбр-7 тбр-4</TD><TD>169500</TD><TD>21620</TD><TD>52198</TD><TD>73818</TD><TD>3885</TD></TR>
-<TR vAlign=top align=center>
-<TD>Итого</TD><TD>Дивизий-21, бригад-21, УР-1</TD><TD>302800</TD><TD>33940 <BR>11,2%</TD><TD>81142</TD><TD>115082</TD><TD>6057</TD></TR>
-</TABLE>
-−
-'''Результаты операции'''. В ходе наступления войска Ленинградского и Волховского фронтов прорвали вражескую блокаду Ленинграда, создав коридор, шириной 8-11 км, позволивший восстановить сухопутные коммуникации города со страной. Южное побережье Ладожского озера было очищено от противника. Несмотря на то, что дальнейшее наступление советских войск развития не получило, операция по прорыву блокады имела важное стратегическое значение и явилась переломным моментом в битве за Ленинград. Замысел врага задушить голодом защитников и жителей города был сорван. Инициатива ведения боевых действий на этом направлении перешла к Красной Армии.
 [[Категория:ТГУ]]
 [[Категория:TEO2]]