Алгоритм Прима, нахождение МОД |
1. Пользуйтесь тегами кода. - [code] ... [/code]
2. Точно указывайте язык, название и версию компилятора (интерпретатора).
3. Название темы должно быть информативным.
В описании темы указываем язык!!!
Алгоритм Прима, нахождение МОД |
Andrewshkovskii |
23.11.2009 13:06
Сообщение
#1
|
Бывалый Группа: Пользователи Сообщений: 222 Пол: Мужской Реальное имя: Andrew Репутация: 0 |
Давно не виделись..всем привет! вот код неправильно работающего алгоритма Прима ( http://www.software.unn.ac.ru/cluster/cgi-...work=10&topic=1 ). Помогите найти ошибку, он не правильно считает минимальное остовное дерево (мод http://ru.wikipedia.org/wiki/Остовное_дерево ).
Код строго на с++. МОД необходимо представлять ввиде матрицы. Уже не знаю что делать, глаза ошибки не могут найти.. int dm[matrixSize][matrixSize];//матрица смежности графа |
volvo |
23.11.2009 14:37
Сообщение
#2
|
Гость |
Цитата вот код неправильно работающего алгоритма Прима Кто сказал, что это неправильно работает? Проверяем:const int matrixSize = 6;Вот чего выдает твой код: 0 0 1 0 0 0 Абсолютно совпадает с решением вышеперечисленных авторов. Это именно остовное дерево минимальной стоимости. Что не так? |
Andrewshkovskii |
23.11.2009 15:49
Сообщение
#3
|
Бывалый Группа: Пользователи Сообщений: 222 Пол: Мужской Реальное имя: Andrew Репутация: 0 |
Для большой матрицы(17х17), вот такой вот :
0 , 465 , 2545 , 396 , 1465 , 1320 , 281 , 676 , 776 , 2652 , 438 , 2385 , 134 , 2553 , 295 , 869 , 2486 Получается оборванный граф :
идет разрыв в(считая от 1) [5] [12] и [12] [5] соотвественно, там должно стоять значение 920.. Пример правильного вычисления МОД для данной матрицы можно глянуть на http://el-niko.ru/lab/1/ , выбрав параметр "Затраты на накопление и переработку" и кол-во записей 17... |
volvo |
23.11.2009 17:53
Сообщение
#4
|
Гость |
Цитата идет разрыв в(считая от 1) [5] [12] и [12] [5] соотвественно, там должно стоять значение 920.. А ты остов-то нарисуй, который получается, полюбопытствуй, а не слепо верь тому, что тебе сайт подсовывает. Я вот нарисовал, никакого разорванного графа не вижу, там именно остов. Какая вершина вырвана, можешь мне рассказать? |
Andrewshkovskii |
23.11.2009 18:31
Сообщение
#5
|
Бывалый Группа: Пользователи Сообщений: 222 Пол: Мужской Реальное имя: Andrew Репутация: 0 |
Ну смотри, я ребра вот так нашел:
из аргыз->каменск-уральский->орехово-юдино->смычка. И все ни смыча, ни агрыз не связаны с ост вершинами.. |
volvo |
23.11.2009 20:19
Сообщение
#6
|
Гость |
Второй цикл, надо бы условие добавить:
for(int i=0;i < matrixSize;++i) |
Andrewshkovskii |
23.11.2009 20:45
Сообщение
#7
|
Бывалый Группа: Пользователи Сообщений: 222 Пол: Мужской Реальное имя: Andrew Репутация: 0 |
Второй цикл, надо бы условие добавить: for(int i=0;i < matrixSize;++i) Вольво.. Огромное спасибо! Сообщение отредактировано: Andrewshkovskii - 23.11.2009 20:46 |
Andrewshkovskii |
25.11.2009 15:06
Сообщение
#8
|
Бывалый Группа: Пользователи Сообщений: 222 Пол: Мужской Реальное имя: Andrew Репутация: 0 |
Я тут сейчас сравнивал значения, и наткнулся на ошибку(или это не в этом алгоритме ошибка..) в общем, опять же , с того же сайта моего однокурсника МОД получается не такой, при 19 значениях и параметр "Транзит без переработки" , в строке Курган X Егоршино, стоит 134, а в нашем случае там 0 , и 92 на Курган х Омск, хотя остов получается нормальным, но при кластеризации по тем же самым параметрам появляются 2 одинаковых кластера
Вот исходные данные матрицы... Размер 19 Цитата { 0,177,171,642,981,15,403,1315,689,1119,311,1201,420,1103,595,930,89,311,1020}, { 177,0,348,465,804,192,226,1138,866,942,134,1024,243,926,772,753,88,134,1197}, { 171,348,0,813,1152,156,574,1486,518,1290,482,1372,591,1274,424,1101,260,482,849} , { 642,465,813,0,339,657,239,673,1331,477,331,559,222,461,1237,288,553,331,1662}, { 981,804,1152,339,0,996,578,334,1670,138,670,220,561,122,1576,51,892,670,2001}, { 15,192,156,657,996,0,418,1330,674,1134,326,1216,435,1118,580,945,104,326,1005}, { 403,226,574,239,578,418,0,912,1092,716,92,798,17,700,998,527,314,92,1423}, { 1315,1138,1486,673,334,1330,912,0,2004,196,1004,114,895,212,1910,385,1226,1004,2 335}, { 689,866,518,1331,1670,674,1092,2004,0,1808,1000,1890,1109,1792,94,1619,778,1000, 331}, { 1119,942,1290,477,138,1134,716,196,1808,0,808,82,699,16,1714,189,1030,808,2139}, { 311,134,482,331,670,326,92,1004,1000,808,0,890,109,792,906,619,222,0,1331}, { 1201,1024,1372,559,220,1216,798,114,1890,82,890,0,781,98,1796,271,1112,890,2221} , { 420,243,591,222,561,435,17,895,1109,699,109,781,0,683,1015,510,331,109,1440}, { 1103,926,1274,461,122,1118,700,212,1792,16,792,98,683,0,1698,173,1014,792,2123}, { 595,772,424,1237,1576,580,998,1910,94,1714,906,1796,1015,1698,0,1525,684,906,425 }, { 930,753,1101,288,51,945,527,385,1619,189,619,271,510,173,1525,0,841,619,1950}, { 89,88,260,553,892,104,314,1226,778,1030,222,1112,331,1014,684,841,0,222,1109}, { 311,134,482,331,670,326,92,1004,1000,808,0,890,109,792,906,619,222,0,1331}, { 1020,1197,849,1662,2001,1005,1423,2335,331,2139,1331,2221,1440,2123,425,1950,110 9,1331,0} А вот и остов : Цитата {0,0,0,0,0,15,0,0,0,0,0,0,0,0,0,0,89,0,0}, {0,0,0,0,0,0,0,0,0,0,134,0,0,0,0,0,88,0,0}, {0,0,0,0,0,156,0,0,0,0,0,0,0,0,424,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0,0,222,0,0,288,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0,0,0,122,0,51,0,0,0}, {15,0,156,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,92,0,17,0,0,0,0,92,0}, {0,0,0,0,0,0,0,0,0,0,0,114,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0,0,0,0,94,0,0,0,331}, {0,0,0,0,0,0,0,0,0,0,0,82,0,16,0,0,0,0,0}, {0,134,0,0,0,0,92,0,0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,114,0,82,0,0,0,0,0,0,0,0,0}, {0,0,0,222,0,0,17,0,0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,122,0,0,0,0,16,0,0,0,0,0,0,0,0,0}, {0,0,424,0,0,0,0,0,94,0,0,0,0,0,0,0,0,0,0}, {0,0,0,288,51,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {89,88,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,92,0,0,0,0,0,0,0,0,0,0,0,0}, << вот здесь {0,0,0,0,0,0,0,0,331,0,0,0,0,0,0,0,0,0,0} А вот Сообщение отредактировано: Andrewshkovskii - 25.11.2009 15:07 |
volvo |
25.11.2009 16:57
Сообщение
#9
|
Гость |
Цитата или это не в этом алгоритме ошибка.. Скорее всего, что не в этом. Проверил заданный граф Крускалом (и обычным алгоритмом, и с системой непересекающихся множеств), и алгоритмом Борувки, ни один из алгоритмов не дал того MST, что приведено на сайте, все дают то, что получается с помощью алгоритма Прима:0, 5 9, 13 6, 12 4, 15 9, 11 1, 16 0, 16 6, 10 6, 17 8, 14 7, 11 4, 13 1, 10 2, 5 3, 12 3, 15 8, 18 2, 14 (список ребер, образующих MST). Как видишь, ребро <6, 17> присутствует, а значит 92 никуда не девается, равно как ребра <1, 17>, чтоб фигурировало 134, нет в помине. Не могут же ВСЕ методы нахождения остовных деревьев ошибаться? Что-то не так значит в алгоритме кластеризации. |
Andrewshkovskii |
25.11.2009 17:01
Сообщение
#10
|
Бывалый Группа: Пользователи Сообщений: 222 Пол: Мужской Реальное имя: Andrew Репутация: 0 |
Весомые доводы.Я понял! буду пытаться придумать нормальный алгоритм.. (как же мне надоела эта задача.. )
|
Текстовая версия | 16.05.2024 20:34 |