california Опубликовано 22 декабря, 2010 Жалоба Поделиться Опубликовано 22 декабря, 2010 Очень нужна помощь в реализации "задачи китайского почтальона на Си(Си++)"Суть задачи в том, что задается граф матрицей смежности, с весами каждого ребра.нужно найти минимальный путь обхода всех ребер графа,по ребрам можно идти по нескольку раз.По примеру...если смотреть в учебнике он состоит из 3 алгоритмов. Алгоритма Дейкстра, алгоритма минимального паросочетания ,и алгоритма нахождения Эйлерова цикла.Добавлено спустя 1 минуту 59 секунд:Добавлено спустя 1 минуту 11 секунд:Добавлено спустя 1 минуту 27 секунд:у меня начало есть...то есть Алгоритм Дейкстра// deykstra.cpp : Defines the entry point for the console application.////С-матрица смежности,с расстониями//xn-начальная точка//xk-конечная точка#include "stdafx.h"#include#include#include#include#include#include "locale.h"#define word unsigned intusing namespace std;void deikstra();int i, j, n, p, xn, xk,z,a[100],k=0;int flag[50];word c[50][50], l[50];char s[80], path[80][50];//setlocale(LC_ALL, "Russian");int min(int n){ int i, result; for(i=0;i if(!(flag)) result=i; for(i=0;i if((l[result]>l)&&(!flag)) result=i; return result;}word minim(word x, word y){ if(x return y;}void main(int argc, char* argv[]){ cout<<"‚ўҐ¤ЁвҐ зЁб«® в®зҐЄ: ";//введите число точек cin>>n; for(i=0;i for(j=0;j for(i=0;i for(j=i+1;j { cout<<"‚ўҐ¤ЁвҐ а ббв®пЁҐ ®в x"< cin>>c[j];//записываем расстояния в матрицу с } cout<<" "; for(i=0;i cout< for(i=0;i { printf("X%d",i+1); for(j=0;j { printf("%6d",c[j]); c[j]=c[j]; } printf("\n\n"); } for(i=0;i for(j=0;j if(c[j]==0) c[j]=65535; } for(i=0;i { z=0; for(j=0;j if(c[j]!=65535) z++; } if(z%2==1)//ищем вершины с нечетными степенями { a[k]=i;//сохраняем номера этих вершин k++; } } for(i=0;i { z=a; a=a[0]; a[0]=z; for(j=1;j { xn=a[j]; xk=a[0]; deikstra(); } }} //------------------------------------------------------------------------------------------------------------------void deikstra(){ for(i=0;i { flag=0; l=65535; } l[xn]=0; flag[xn]=1; p=xn; itoa(xn+1,s,10); for(i=1;i<=n;i++) { strcpy(path,"X"); strcat(path,s); } do { for(i=0;i if((c[p]!=65535)&&(!flag)&&(i!=p)) { if(l>l[p]+c[p]) { itoa(i+1,s,10); strcpy(path[i+1],path[p+1]); strcat(path[i+1],"-X"); strcat(path[i+1],s); } l=minim(l,l[p]+c[p]); } p=min(n); flag[p]=1; } while(p!=xk); if(l[p]!=65535) { cout<<"Џгвм: "< cout<<"„«Ё ЇгвЁ: "< } else cout<<"ЇгвЁ Ґв!"< //getch();}Добавлено спустя 2 минуты 15 секунд:еще есть алгоритм Эйлера, но я его запустить не могу((он не воспринимаетЦитата:procedure FindEulerPath (V)1. перебрать все рёбра, выходящие из вершины V;каждое такое ребро удаляем из графа, ивызываем FindEulerPath из второго конца этого ребра;2. добавляем вершину V в ответ.Несмотря на кажущуюся на простоту, этот алгоритм выполняет все требуемые действия: находит все циклы, объединяя их в один эйлеров цикл. Сложность алгоритма, очевидно, является линейной относительно числа рёбер.Далее, этот же алгоритм мы можем записать в нерекурсивном варианте:Цитата:stack St;в St кладём любую вершину (стартовая вершина);пока St не пустойпусть V - значение на вершине St;если степень(V) = 0, тодобавляем V к ответу;снимаем V с вершины St;иначенаходим любое ребро, выходящее из V;удаляем его из графа;второй конец этого ребра кладём в St;Несложно проверить эквивалентность этих двух форм алгоритма. Однако вторая форма, очевидно, быстрее работает и пишется быстрее.Итак, реализация всего алгоритма:(ищет эйлеров цикл или путь в графе, или выводит -1, если его не существует)Код:typedef vector < vector > graph;bool connected (const graph & g, const vector & degree, int n){int first;for (first=0; firstif (degree[first])break;if (first == n)return false;vector used (n);vector q (n);int h=0, t=0;q[t++] = first;used[first] = true;while (h < t){int v = q[h++];for (int i=0; iif (g[v] && !used){used = true;q[t++] = i;}}for (int i=0; iif (!used && degree > 0)return false;return true;}void find_euler_cycle (graph&g, vector°ree, int n, vector&result){stack st;st.push (0);while (!st.empty()){int v = st.top();if (degree[v] == 0){st.pop();result.push_back (v);}else{for (int i=0; iif (g[v]){--g[v], --g[v];--degree[v], --degree;st.push (i);break;}}}}int main(){int n;graph g (n, vector (n));vector degree (n);... чтение графа ...int odd_count = 0;for (int i=0; iif (degree % 2 == 1)++odd_count;if (!connected (g, degree, n) || odd_count > 2)cout << -1;else{int im_v1 = -1, im_v2 = -1;if (odd_count){for (int i=0; iif (degree % 2 == 1)if (im_v1 == -1)im_v1 = i;elseim_v2 = i;++g[im_v1][im_v2];++g[im_v2][im_v1];++degree[im_v1];++degree[im_v2];}vector result;find_euler_cycle (g, degree, n, result);if (odd_count)for (size_t i=1; iif (result[i-1] == im_v1 && result == im_v2 ||result[i-1] == im_v2 && result == im_v1){vector new_res;copy (result.begin()+i, result.end()-1, back_inserter (new_res));copy (result.begin(), result.begin()+i, back_inserter (new_res));result.swap (new_res);break;}cout << result.size();for (size_t i=0; icout << result+1;}}Добавлено спустя 1 минуту 35 секунд:а как это все в кучу собрать....и паросочетание найти я не знаю(((помогите пожалуйста....у меня идей уже нет никаких( Ссылка на комментарий
danger Опубликовано 22 декабря, 2010 Жалоба Поделиться Опубликовано 22 декабря, 2010 дали задачу довольно таки не простую задачу человеку который даже векторы подинклудить не может... Ссылка на комментарий
california Опубликовано 22 декабря, 2010 Автор Жалоба Поделиться Опубликовано 22 декабря, 2010 спасибо за комментарий..но все же.. Ссылка на комментарий
0xDEADBEEF Опубликовано 22 декабря, 2010 Жалоба Поделиться Опубликовано 22 декабря, 2010 Лезем на e-maxx.ru и смотрим алгоритмы.Нормальная реализация алгоритма Дейкстры (Dijkstra)Паросочетание можно искать любым потоковым алгоритмом (они на мой взгляд проще), или Венгерским алгоритмом (он быстрее).Эйлеров цикл - самым обычным способом. К стати впервые вижу у этого алгоритма имя.Вообще это типичная задача спортивного программирования. Финалисты ACM такие вещи пишут по утрам, в качестве зарядки =)Вообще у нас в регионе создается сообщество людей, которые стремятся совершенствовать свои программисткие навыки, эрудицию и мыслительный процесс самым лучшим для этого способом - занятием спортивным программированием.Подробнее - Группа ВКотакте Ссылка на комментарий
california Опубликовано 23 декабря, 2010 Автор Жалоба Поделиться Опубликовано 23 декабря, 2010 я в роде бы нахождение Эйлерова пути написала...только понять не могу...он правильно или нет работает....если не сложно,пожалуйста посмотрите...я вообще то, что надо написала...или нет.#include "stdio.h"#include "stdafx.h"#include "stdlib.h"#include "locale.h"void no();void komponenta(int i);void poisk(int i);int a[100][100];//матррица смежностиint vert[10000];//степень вершинint way [10000];//Эйлеров циклint flag[10000];//компоненты связностиint x,y,w;int n,m;// m - число дуг, n - число вершинint count;// число компонент связностиvoid main(){//возможно нужно вставить обнуление setlocale(LC_ALL, "Russian"); printf("Введите n-число вершин"); scanf("%i",&n); printf("Введите матрицу смежности"); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) scanf("%i",&a[j]); } count=0; for (int i=1;i { if (flag==0) count++; if (count>1 ) no();// граф не связен komponenta(i); } for (int i=1;i< n;i++) if (vert%2==1) no(); // есть вершины нечётной степени w=0; poisk(1); for (int i=1;i< w;i++) printf("%i ",way);}//---------------------------------------------------void no(){ printf("Эйлеров цикл не существует!"); exit(0);}//---------------------------------------------------void komponenta(int i){ int j; flag=count; for (int j=1;j<=n;j++) if ((a[j])&&(flag[j]==0)) komponenta(j); }//---------------------------------------------------void poisk(int i){int j; for (int j=1;j<=n;j++) if (a[j]){ a[j]=0; a[j]=0; poisk(j); } w++; way[w]=i;}Добавлено спустя 33 минуты 30 секунд:я вообще не понимаю как паросочитания находить...что бы их пути давали полную группу....и то что после идет у меня провал...я уже сотни раз алгоритм прочитала...ну если это для вас простая задача..ну помогите пожалуйста... Ссылка на комментарий
0xDEADBEEF Опубликовано 23 декабря, 2010 Жалоба Поделиться Опубликовано 23 декабря, 2010 Паросочетание искать либо Венгерским алгоритмом, либо любым алгоритмом максимального потока минимальной стоимости.Поиск Эйлерова цикла написан правильно, за исключением проверки степени вершин - массив степеней банально не заполняется. Ссылка на комментарий
california Опубликовано 24 декабря, 2010 Автор Жалоба Поделиться Опубликовано 24 декабря, 2010 а что делать ... с Эйлеровым циклом...если по условию мы передаем туда нечетные вершины? Ссылка на комментарий
0xDEADBEEF Опубликовано 24 декабря, 2010 Жалоба Поделиться Опубликовано 24 декабря, 2010 1. В исходном графе Г' находятся все вершины нечетной степени, если таковых нет то п. 6.2. Для каждой такой вершины находятся кратчайшие пути до всех остальных, эти пути запоминаются.3. На этих вершинах строится двудольный граф Г' с весами, равными кратчайшему расстоянию (на рисунке 2 видна соответствующая матрица смежности для сэмпла)4. Ищем максимальное паросочетание минимального веса.5. По паросочетанию добавляем в исходный граф дополнительные ребра. Т.е. если у нас в паросочетании Г' есть ребро (A,, то в Г добавляется цепь кратчайшего пути м/у вершинами А и В. Получаем эйлеров граф.6. Находим эйлерову цепь.7. ....8. PROFIT!Вот примерно так это должно выглядеть.Можно узнать где такие задачи дают? Ссылка на комментарий
california Опубликовано 24 декабря, 2010 Автор Жалоба Поделиться Опубликовано 24 декабря, 2010 можно, в ВСГТУ по Дискретной математике Ссылка на комментарий
california Опубликовано 29 декабря, 2010 Автор Жалоба Поделиться Опубликовано 29 декабря, 2010 0xDEADBEEFогромное спасибо))я таки прогу дописала, и защитила ))спасибо за алгоритм...иначе бы в жизнь не поняла, что делать вообще надо!) Ссылка на комментарий
Max4406 Опубликовано 29 декабря, 2010 Жалоба Поделиться Опубликовано 29 декабря, 2010 девушка программист? *85 Ссылка на комментарий
D_Master Опубликовано 29 декабря, 2010 Жалоба Поделиться Опубликовано 29 декабря, 2010 девушка программист? *85 Встречаются) И теперь уже можно не удивляться :-) Ссылка на комментарий
0xDEADBEEF Опубликовано 29 декабря, 2010 Жалоба Поделиться Опубликовано 29 декабря, 2010 californiaНя1 незачто.Спортивным программированием не желаете заняться?Люди умеющие писать такие вещи у нас, к сожалению, редкость. Ссылка на комментарий
california Опубликовано 1 января, 2011 Автор Жалоба Поделиться Опубликовано 1 января, 2011 да...я как бы занимаюсь уже потихоньку...новичок, но стараюсь))еще раз спасибо . Ссылка на комментарий
Рекомендуемые сообщения
Пожалуйста, войдите, чтобы комментировать
Вы сможете оставить комментарий после входа в
Войти