"Поиск кратчайшего пути"
Содержание |
Название проекта
Поиск кратчайшего пути
Авторы и участники проекта
Абашин Павел
Тема исследования группы
Преимущества и недостатки алгоритмов
Проблемный вопрос (вопрос для исследования)
Каковы преимущества и недостатки алгоритмов поиска кратчайшего пути?
Раскрытие вопроса
Кратчайший путь рассматривается при помощи некоторого математического объекта, называемого графом. Существуют несколько наиболее эффективных алгоритмов нахождения кратчайшего пути:
- алгоритм Дейкстры (используется для нахождения оптимального маршрута между двумя вершинами);
- алгоритм Форда-Беллмана;
- алгоритм Шимбелла.
Алгоритм Форда-Беллмана позволяет решить задачу о кратчайшем пути из фиксированного истока в общем случае, когда вес любого ребра может быть отрицательным. Этот алгоритм отличается своей простотой. К его достоинствам также относится то, что он определяет, содержится ли в графе цикл с отрицательным весом, достижимый из истока. Также в проекте описывается алгоритм Дейкстры, который характеризуется меньшим временем выполнения, чем алгоритм Форда-Беллмана, и менее претезателен чем другие алгоритмы. Кроме того, приведен алгоритм динамического программирования — алгоритм Флойда-Уоршалла (Floyd-Warshall), который позволяет решить задачу о поиске кратчайших путей между всеми парами вершин.
| Файл:2u43s.gif |
"Искра" - кодовое наименование плана операции советских войск по прорыву блокады Ленинграда. План предусматривал одновременными встречными ударами войск Ленинградского фронта с запада и Волховского с востока в направлении на Синявино и Рабочий поселок № 5 во взаимодействии с Балтийским флотом разгромить группировку противника южнее Ладожского озера, ликвидировать шлиссельбургско-синявинский выступ и тем самым обеспечить сухопутное сообщение Ленинграда со страной... 12 января 1943 соединения 67-й армии Ленинградского фронта (командующий генерал-лейтенант Л. А. Говоров), 2-й ударной и части сил 8-й армии Волховского фронта (командующий генерал армии К. А. Мерецков) по приказу Ставки ВГК приступили к осуществлению операции "Искра"... 18 января 1943 года войска фронта соединились в районах Рабочих поселков № 5 и № 1. Блокада Ленинграда была прорвана. Между Ладожским озером и линией фронта образовался коридор шириной 8-11 км. 12 - 30 января 1943 г. Стратегическая наступательная операция по прорыву блокады Ленинграда проводилась силами ударных группировок Ленинградского и Волховского фронтов при содействии части сил Балтийского флота и авиации дальнего действия. Продолжительность - 19 суток. Ширина фронта боевых действий - 45 км. Глубина продвижения советских войск - 60 км. Среднесуточные темпы наступления - 3-3,5 км. |
| Наименование объединений и сроки их участия в операции | Боевой состав и численность войск к началу операции | Людские потери в операции (чел.) | ||||
| Количество соединений | Численность | Безвозвратные | Санитарные | Всего | Среднесуточные | |
| Ленинградский фронт (весь период) - 67-я армия - 13-я воздушная армия (летный состав) | сд-6, сбр-7, тбр-3, УР-1 | 133300 | 12320 | 28944 | 41264 | 2172 |
| Волховский фронт (весь период) - 2-я ударная армия - 8-я армия - 14-я воздушная армия (летный состав) | сд-15 сбр-7 тбр-4 | 169500 | 21620 | 52198 | 73818 | 3885 |
| Итого | Дивизий-21, бригад-21, УР-1 | 302800 | 33940 11,2% | 81142 | 115082 | 6057 |
Результаты операции. В ходе наступления войска Ленинградского и Волховского фронтов прорвали вражескую блокаду Ленинграда, создав коридор, шириной 8-11 км, позволивший восстановить сухопутные коммуникации города со страной. Южное побережье Ладожского озера было очищено от противника. Несмотря на то, что дальнейшее наступление советских войск развития не получило, операция по прорыву блокады имела важное стратегическое значение и явилась переломным моментом в битве за Ленинград. Замысел врага задушить голодом защитников и жителей города был сорван. Инициатива ведения боевых действий на этом направлении перешла к Красной Армии.
