Алгоритм Прима (Уже не знаю куда бежать :))
Модератор: Модераторы разделов
Алгоритм Прима
Проблема следующая. Задали нам СРС (самост.раб.студента)
Мне по счастливой случайности достался алгоритм Прима (поиска минимального остовного дерева). И даже сказали где брать информацию по теме - книга Хезфилда. Но вот не задача - в этой книге есть расплывчатое описание самого алгоритма, а далее код программы. Я уже перерыл пол рунета - так и не смог найти нормального словесного описания этого алгоритма.
Буду очень благодарен, если кто-то поделится либо описанием тут, либо файликом с описанием. А то сроки уже поджимают, а воз и ныне там
Мне по счастливой случайности достался алгоритм Прима (поиска минимального остовного дерева). И даже сказали где брать информацию по теме - книга Хезфилда. Но вот не задача - в этой книге есть расплывчатое описание самого алгоритма, а далее код программы. Я уже перерыл пол рунета - так и не смог найти нормального словесного описания этого алгоритма.
Буду очень благодарен, если кто-то поделится либо описанием тут, либо файликом с описанием. А то сроки уже поджимают, а воз и ныне там
"Так не возможно
Не оступиться,
Не избежать высоты.
Остановиться нам еще можно,
Есть еще шаг до черты." © А.Горшенев
Не оступиться,
Не избежать высоты.
Остановиться нам еще можно,
Есть еще шаг до черты." © А.Горшенев
Re: Алгоритм Прима
Я на память знаю только "жадный" алгоритм посика. Может это он?
В каждом из нас спит гений... и с каждым днем все крепче...
Re: Алгоритм Прима
А может попробуем попроще?
Запости-ка сюда то описание алгоритма, что есть в книге (именно то, которое в виде текста программы, хотя и словесное не помешает, если это возможно). А общими усилиями расшифруем и доведём до ума. имхо это куда реальнее, полезнее, интереснее и надёжнее.
ЗЫ: Просто в своё время тоже писал реализацию какого-то алгоритма. Посмотрел на псевдо-код сначала: нифига не понял. Посидел, поковырял, подумал - разобрался.
Запости-ка сюда то описание алгоритма, что есть в книге (именно то, которое в виде текста программы, хотя и словесное не помешает, если это возможно). А общими усилиями расшифруем и доведём до ума. имхо это куда реальнее, полезнее, интереснее и надёжнее.
ЗЫ: Просто в своё время тоже писал реализацию какого-то алгоритма. Посмотрел на псевдо-код сначала: нифига не понял. Посидел, поковырял, подумал - разобрался.
Re: Алгоритм Прима
Поддерживаю. :thumbsup:(JaGoTerr @ Четверг, 21 Октября 2004, 15:41) писал(а):А может попробуем попроще?
Запости-ка сюда то описание алгоритма, что есть в книге (именно то, которое в виде текста программы, хотя и словесное не помешает, если это возможно). А общими усилиями расшифруем и доведём до ума. имхо это куда реальнее, полезнее, интереснее и надёжнее.
¡иɯʎdʞ ин ʞɐʞ 'ɐнɔɐdʞǝdu qнεиж
Re: Алгоритм Прима
Да в том то и дело - времени нет на глубокие вдумки
Описание:
Алгоритм Прима создает минимальное остовное дерево путем добавления единственного ребра (а также вершин) в дерево после определенного количества итераций. Вершины в графе разделяются на два набора: один, являющийся частью дерева, а другой нет. Во время каждой итерации ребро с минимальными затратами связывает любую вершину, являющуюся частью решения, с любой вершиной, которая еще не добавлена в это решение. Это происходит до тех пор пока в решение не будут добавлены все вершины, другими словами пока не будет выбрано V-1 ребер.
Шаги:
1. Выбрать корневую вершину V
2. Пометить V как посещенную
3. Для каждой смежной с V вершины установить затраты кратчайшего ребра
4. Выбрать непосещенную вершину с наименьшими затратами ребра в качестве текущей вершины V и добавить связывающее ребро в остовное дерево.
5. Повторить все шаги со второго, пока не будут посещены все вершины.
Вобщем я немного не понял - что происходит с вершинами, которые могли оказаться на более тяжелых ребрах и к которым потом не найдется пути??? И вообще - прошу поподробней делится мыслями.
ЗЫ: Листинг пока не привожу - он длинный и написан в общем виде.... на сях
Описание:
Алгоритм Прима создает минимальное остовное дерево путем добавления единственного ребра (а также вершин) в дерево после определенного количества итераций. Вершины в графе разделяются на два набора: один, являющийся частью дерева, а другой нет. Во время каждой итерации ребро с минимальными затратами связывает любую вершину, являющуюся частью решения, с любой вершиной, которая еще не добавлена в это решение. Это происходит до тех пор пока в решение не будут добавлены все вершины, другими словами пока не будет выбрано V-1 ребер.
Шаги:
1. Выбрать корневую вершину V
2. Пометить V как посещенную
3. Для каждой смежной с V вершины установить затраты кратчайшего ребра
4. Выбрать непосещенную вершину с наименьшими затратами ребра в качестве текущей вершины V и добавить связывающее ребро в остовное дерево.
5. Повторить все шаги со второго, пока не будут посещены все вершины.
Вобщем я немного не понял - что происходит с вершинами, которые могли оказаться на более тяжелых ребрах и к которым потом не найдется пути??? И вообще - прошу поподробней делится мыслями.
ЗЫ: Листинг пока не привожу - он длинный и написан в общем виде.... на сях
"Так не возможно
Не оступиться,
Не избежать высоты.
Остановиться нам еще можно,
Есть еще шаг до черты." © А.Горшенев
Не оступиться,
Не избежать высоты.
Остановиться нам еще можно,
Есть еще шаг до черты." © А.Горшенев
Re: Алгоритм Прима
Это оно! Описываю:
1. Берешь любую вершину.
2. Среди всех ребер исходящих из выбраных тобою вершин выбираешь самое короткое
note: каждое ребро имеет числовую хар-ку - вес или длину. Нужно выбирать минимальную.
3. Добавляешь к списку выбраных тобою вершин ту, к которой ведет это самое короткое ребро.
4. goto 2 пока не перебеорешь всех вершин.
note: ты гарантированно переберешь все, если граф односвязный.
note: пофиг до стартовой вершины - дерево все-равно выйдет одно и то же.
1. Берешь любую вершину.
2. Среди всех ребер исходящих из выбраных тобою вершин выбираешь самое короткое
note: каждое ребро имеет числовую хар-ку - вес или длину. Нужно выбирать минимальную.
3. Добавляешь к списку выбраных тобою вершин ту, к которой ведет это самое короткое ребро.
4. goto 2 пока не перебеорешь всех вершин.
note: ты гарантированно переберешь все, если граф односвязный.
note: пофиг до стартовой вершины - дерево все-равно выйдет одно и то же.
В каждом из нас спит гений... и с каждым днем все крепче...
Re: Алгоритм Прима
Поправка: забыли написать "среди ведущих в непосещённые вершины", а то так можно и зациклиться.(flook @ Пятница, 22 Октября 2004, 9:30) писал(а):2. Среди всех ребер исходящих из выбраных тобою вершин выбираешь самое короткое
¡иɯʎdʞ ин ʞɐʞ 'ɐнɔɐdʞǝdu qнεиж
Re: Алгоритм Прима
Значит так:
как я понял исходный граф взвешенный???
и еще - а если граф не связный что делать?
или если например получили граф в виде звезды и изначально стояли в центре??
По-поводу последних двух пунктов - я думаю нужно в случае отсутствия соседов непосещенных выбирать вершину среди остальных непосещенных случайно??? не так ли???
"Так не возможно
Не оступиться,
Не избежать высоты.
Остановиться нам еще можно,
Есть еще шаг до черты." © А.Горшенев
Не оступиться,
Не избежать высоты.
Остановиться нам еще можно,
Есть еще шаг до черты." © А.Горшенев
Re: Алгоритм Прима
Зависит от того, что имеется ввиду делать, если нельзя наложить связный маршрут. Если перейти к набору связных маршрутов, то так.(shulik @ Пятница, 22 Октября 2004, 15:13) писал(а):По-поводу последних двух пунктов - я думаю нужно в случае отсутствия соседов непосещенных выбирать вершину среди остальных непосещенных случайно??? не так ли???
¡иɯʎdʞ ин ʞɐʞ 'ɐнɔɐdʞǝdu qнεиж
Re: Алгоритм Прима
(t.t @ Пятница, 22 Октября 2004, 16:18) писал(а):Зависит от того, что имеется ввиду делать, если нельзя наложить связный маршрут. Если перейти к набору связных маршрутов, то так.(shulik @ Пятница, 22 Октября 2004, 15:13) писал(а):По-поводу последних двух пунктов - я думаю нужно в случае отсутствия соседов непосещенных выбирать вершину среди остальных непосещенных случайно??? не так ли???
а если не лес строить. то есть я ж говорю - шел я по графу - и вдруг забрел на лист. Выходов в непосещенные вершины нет - а вершины еще остались... как тут быть??? опять же случайным образом из непосещенных выбирать или есть иной вариант???
"Так не возможно
Не оступиться,
Не избежать высоты.
Остановиться нам еще можно,
Есть еще шаг до черты." © А.Горшенев
Не оступиться,
Не избежать высоты.
Остановиться нам еще можно,
Есть еще шаг до черты." © А.Горшенев
Re: Алгоритм Прима
На каждом шаге выбирается кратчайшее ребро не из текущей вершины, а из всех посещённых. Так что связный граф (или каждую связную компоненту в случае несвязного графа) мы в итоге обойдём целиком всегда.(shulik @ Пятница, 22 Октября 2004, 15:30) писал(а):а если не лес строить. то есть я ж говорю - шел я по графу - и вдруг забрел на лист. Выходов в непосещенные вершины нет - а вершины еще остались... как тут быть??? опять же случайным образом из непосещенных выбирать или есть иной вариант???
¡иɯʎdʞ ин ʞɐʞ 'ɐнɔɐdʞǝdu qнεиж
Re: Алгоритм Прима
(t.t @ Пятница, 22 Октября 2004, 16:46) писал(а):На каждом шаге выбирается кратчайшее ребро не из текущей вершины, а из всех посещённых. Так что связный граф (или каждую связную компоненту в случае несвязного графа) мы в итоге обойдём целиком всегда.(shulik @ Пятница, 22 Октября 2004, 15:30) писал(а):а если не лес строить. то есть я ж говорю - шел я по графу - и вдруг забрел на лист. Выходов в непосещенные вершины нет - а вершины еще остались... как тут быть??? опять же случайным образом из непосещенных выбирать или есть иной вариант???
Ясно. Спасибо за помощь. Как будет что-нибудь готово постараюсь не забыть запостить сюда результат
"Так не возможно
Не оступиться,
Не избежать высоты.
Остановиться нам еще можно,
Есть еще шаг до черты." © А.Горшенев
Не оступиться,
Не избежать высоты.
Остановиться нам еще можно,
Есть еще шаг до черты." © А.Горшенев