IPB
ЛогинПароль:

> Внимание!

1. Пользуйтесь тегами кода. - [code] ... [/code]
2. Точно указывайте язык, название и версию компилятора (интерпретатора).
3. Название темы должно быть информативным.
В описании темы указываем язык!!!

Наладить общение поможет, если вы подпишитесь по почте на новые темы в этом форуме.

 
 Ответить  Открыть новую тему 
> Алгоритм Прима, нахождение МОД
сообщение
Сообщение #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];//матрица смежности графа
int sm[matrixSize][matrixSize];//матрица МОД
int used[matrixSize];//использованные вершины
int count=0;
int min ;

for (int i=0; i< matrixSize; ++i)
{
used[i]=0;
for(int j=0;j< matrixSize;++j)
sm[i][j]=0;
}

used[0]=1;
do {
min=std::numeric_limits<int>::max();
for(int i=0;i<matrixSize;++i)
{
if (used[i]!=0)
{
for(int j=0;j<matrixSize;++j)
if ( (dm[j][i] < min) && (dm[j][i]!=0) && (used[j])==0)
min=dm[j][i];
}
}
for(int i=0;i < matrixSize;++i)
for(int j=0;j<matrixSize;++j)
if( (dm[j][i]== min) && (used[j]==0))
{
used[j] =1;
sm[j][i]= sm[i][j] = min;
count++;
i=matrixSize;
break;
}
}while(count < matrixSize-1);

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






Цитата
вот код неправильно работающего алгоритма Прима
Кто сказал, что это неправильно работает? Проверяем:
    const int matrixSize = 6;
int dm[matrixSize][matrixSize] =
{
{ 0, 6, 1, 5, 0, 0 },
{ 6, 0, 5, 0, 3, 0 },
{ 1, 5, 0, 5, 6, 4 },
{ 5, 0, 5, 0, 0, 2 },
{ 0, 3, 6, 0, 0, 6 },
{ 0, 0, 4, 2, 6, 0 }
}; // матрица смежности графа из Ахо/Хопкрофта/Ульмана, стр. 211
// ...
// выводим полученную матрицу:
for(int i = 0; i < matrixSize; i++)
{
for(int j = 0; j < matrixSize; j++)
{
std::cout << sm[i][j] << " ";
}
std::cout << std::endl;
}
Вот чего выдает твой код:
0 0 1 0 0 0
0 0 5 0 3 0
1 5 0 0 0 4
0 0 0 0 0 2
0 3 0 0 0 0
0 0 4 2 0 0

Абсолютно совпадает с решением вышеперечисленных авторов. Это именно остовное дерево минимальной стоимости. Что не так?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Бывалый
***

Группа: Пользователи
Сообщений: 222
Пол: Мужской
Реальное имя: Andrew

Репутация: -  0  +


Для большой матрицы(17х17), вот такой вот :
0 , 465 , 2545 , 396 , 1465 , 1320 , 281 , 676 , 776 , 2652 , 438 , 2385 , 134 , 2553 , 295 , 869 , 2486
465 , 0 , 2080 , 69 , 1000 , 855 , 184 , 1141 , 311 , 2187 , 27 , 1920 , 331 , 2088 , 170 , 404 , 2021
2545 , 2080 , 0 , 2149 , 1080 , 1225 , 2264 , 3221 , 1769 , 107 , 2107 , 160 , 2411 , 8 , 2250 , 1676 , 59
396 , 69 , 2149 , 0 , 1069 , 924 , 115 , 1072 , 380 , 2256 , 42 , 1989 , 262 , 2157 , 101 , 473 , 2090
1465 , 1000 , 1080 , 1069 , 0 , 145 , 1184 , 2141 , 689 , 1187 , 1027 , 920 , 1331 , 1088 , 1170 , 596 , 1021
1320 , 855 , 1225 , 924 , 145 , 0 , 1039 , 1996 , 544 , 1332 , 882 , 1065 , 1186 , 1233 , 1025 , 451 , 1166
281 , 184 , 2264 , 115 , 1184 , 1039 , 0 , 957 , 495 , 2371 , 157 , 2104 , 147 , 2272 , 14 , 588 , 2205
676 , 1141 , 3221 , 1072 , 2141 , 1996 , 957 , 0 , 1452 , 3328 , 1114 , 3061 , 810 , 3229 , 971 , 1545 , 3162
776 , 311 , 1769 , 380 , 689 , 544 , 495 , 1452 , 0 , 1876 , 338 , 1609 , 642 , 1777 , 481 , 93 , 1710
2652 , 2187 , 107 , 2256 , 1187 , 1332 , 2371 , 3328 , 1876 , 0 , 2214 , 267 , 2518 , 99 , 2357 , 1783 , 166
438 , 27 , 2107 , 42 , 1027 , 882 , 157 , 1114 , 338 , 2214 , 0 , 1947 , 304 , 2115 , 143 , 431 , 2048
2385 , 1920 , 160 , 1989 , 920 , 1065 , 2104 , 3061 , 1609 , 267 , 1947 , 0 , 2251 , 168 , 2090 , 1516 , 101
134 , 331 , 2411 , 262 , 1331 , 1186 , 147 , 810 , 642 , 2518 , 304 , 2251 , 0 , 2419 , 161 , 735 , 2352
2553 , 2088 , 8 , 2157 , 1088 , 1233 , 2272 , 3229 , 1777 , 99 , 2115 , 168 , 2419 , 0 , 2258 , 1684 , 67
295 , 170 , 2250 , 101 , 1170 , 1025 , 14 , 971 , 481 , 2357 , 143 , 2090 , 161 , 2258 , 0 , 574 , 2191
869 , 404 , 1676 , 473 , 596 , 451 , 588 , 1545 , 93 , 1783 , 431 , 1516 , 735 , 1684 , 574 , 0 , 1617
2486 , 2021 , 59 , 2090 , 1021 , 1166 , 2205 , 3162 , 1710 , 166 , 2048 , 101 , 2352 , 67 , 2191 , 1617 , 0


Получается оборванный граф :

0 , 0 , 0 , 0 , 0 , 0 , 0 , 676 , 0 , 0 , 0 , 0 , 134 , 0 , 0 , 0 , 0 ,
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 311 , 0 , 27 , 0 , 0 , 0 , 0 , 0 , 0 ,
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 8 , 0 , 0 , 59 ,
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 42 , 0 , 0 , 0 , 101 , 0 , 0 ,
0 , 0 , 0 , 0 , 0 , 145 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
0 , 0 , 0 , 0 , 145 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 451 , 0 ,
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 147 , 0 , 14 , 0 , 0 ,
676 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
0 , 311 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 93 , 0 ,
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 99 , 0 , 0 , 0 ,
0 , 27 , 0 , 42 , 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 , 0 , 0 , 0 , 101 ,
134 , 0 , 0 , 0 , 0 , 0 , 147 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
0 , 0 , 8 , 0 , 0 , 0 , 0 , 0 , 0 , 99 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
0 , 0 , 0 , 101 , 0 , 0 , 14 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
0 , 0 , 0 , 0 , 0 , 451 , 0 , 0 , 93 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
0 , 0 , 59 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 101 , 0 , 0 , 0 , 0 , 0 ,


идет разрыв в(считая от 1) [5] [12] и [12] [5] соотвественно, там должно стоять значение 920..
Пример правильного вычисления МОД для данной матрицы можно глянуть на http://el-niko.ru/lab/1/ ,
выбрав параметр "Затраты на накопление и переработку" и кол-во записей 17...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






Цитата
идет разрыв в(считая от 1) [5] [12] и [12] [5] соотвественно, там должно стоять значение 920..
А ты остов-то нарисуй, который получается, полюбопытствуй, а не слепо верь тому, что тебе сайт подсовывает. Я вот нарисовал, никакого разорванного графа не вижу, там именно остов. Какая вершина вырвана, можешь мне рассказать?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Бывалый
***

Группа: Пользователи
Сообщений: 222
Пол: Мужской
Реальное имя: Andrew

Репутация: -  0  +


Ну смотри, я ребра вот так нашел:
из аргыз->каменск-уральский->орехово-юдино->смычка. И все ни смыча, ни агрыз не связаны с ост вершинами..
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Гость






rolleyes.gif Второй цикл, надо бы условие добавить:
for(int i=0;i < matrixSize;++i)
for(int j=0;j<matrixSize;++j)
if( (dm[j][ i ]== min) && (used[j]==0) && (used[ i ] == 1)) {
used[j] =1;
sm[j][ i ]= sm[ i ][j] = min;
count++;
i=matrixSize;
break;
}
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Бывалый
***

Группа: Пользователи
Сообщений: 222
Пол: Мужской
Реальное имя: Andrew

Репутация: -  0  +


Цитата(volvo @ 23.11.2009 20:19) *

rolleyes.gif Второй цикл, надо бы условие добавить:
for(int i=0;i < matrixSize;++i)
for(int j=0;j<matrixSize;++j)
if( (dm[j][ i ]== min) && (used[j]==0) && (used[ i ] == 1)) {
used[j] =1;
sm[j][ i ]= sm[ i ][j] = min;
count++;
i=matrixSize;
break;
}


Вольво.. Огромное спасибо!

Сообщение отредактировано: Andrewshkovskii -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #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 -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #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, нет в помине. Не могут же ВСЕ методы нахождения остовных деревьев ошибаться? Что-то не так значит в алгоритме кластеризации.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Бывалый
***

Группа: Пользователи
Сообщений: 222
Пол: Мужской
Реальное имя: Andrew

Репутация: -  0  +


Весомые доводы.Я понял! буду пытаться придумать нормальный алгоритм.. (как же мне надоела эта задача.. )
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 23.10.2020 7:34
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name