p align="left">Повторять процедуру (шаги 1-4) до тех пор, пока назначение не станет возможным. 2. Проектный раздел 2.1 Словесная постановка задачи:Реализовать известный алгоритм для задачи китайского почтальона.2.2 Формальная постановка задачи:Входные данные:n-количество вершин графа C[50][50]-символьная матрица смежности Выходные данные:Путь обхода графа. Суммарный вес пройденных дуг Метод решения :Программа состоит из 2 основных подпрограмм 1)Программа реализующая алгоритм Дейкстры( описанный в разделе 1) 2)Алгоритм Флёри (раздел 1) содержащий в себе часть венгерского алгоритма. 2.3 Алгоритм решения задачи в графическом видеKomponenta()Poisk()Main()Deikstra()Eiler()3. Программный разделvoid main(int argc, char* argv[])Главная функция программы. В ней происходит ввод данных с клавиатуры:n-числа вершин C[i][j]-расстояние между конкретными вершинами i и jВ результате чего формируется матрица смежности wordC[n][n].В этой функции происходит вызов функции deikstra() и eiler();В функцию deikstra() передаются номера вершин с нечетной степенью в всевозможных попарных сочетаниях .void deikstra()Функция нахождения кратчайшего расстояния между переданными точками.Функция ничего не возврящает, но при каждом вызове выводит на экран путь между заданными вершинами и длину этого пути.Для работы данной функции необходимо подключить функции int min(int n) и word minim(word x, word y)· int min(int n)- возвращает номер ближайшей не пройденной вершины · wordminim(wordx, wordy)-возвращает самое короткое из 2 переданных слов void eiler() Функция нахождения эйлерова цикла в заданом графе. В случае если данный цикл не может быть найден ,цикл ищеться с добавлением необходимых ребер, после чего необходимое ребро заменяеться самой короткой цепью из возвращаемых функцией Deikstra(). Так же в этой функции просчитывется суммарный вес обхода. Для работы данной функции необходимо подключение 3 функций: · void poisk(int i)- динамическая функция непосредственного поиска пути. В ней же происходит обнуления рабочей матрицы смежности A[50][50] · void komponenta(int i)- проверяет наличие пустых ячеек в регистре флагов. В данной программе не обязательна и не используется · void no()-функция выводящая сообщение о невозможности нахождения эйлерова цикла в данном графе( если граф не связан) 4.Эксперементальный раздел Данная программа работает только с графами количество вершин меньше 50. (Это число было задано при разработке , и по этому в случае необходимости может варьироваться )Но так как программа основана не на динамическом распределении памяти а н хранении элементов (матрицы смежности) в виде массива, но верхний порог значений всегда будет иметь место. Так же данная программа не работает с отрицательными значениями в матрице смежности. Это связанно с основой поставленной задачи. Данная задача может иметь множество разных решений, так как единственный метод получения достоверного ответа сводиться к полному перебору вариантов. Данный метод в этой работе не рассматривается. Пример работы программы в нормальных условиях не описанных выше: При введённых значения (которые указаны на рисунке выше) сформировалась матрица смежности. Как видно, единственные вершины с нечетными степенями -это вершины х1 (3 ребра),и x4(3 ребра). Они были самый короткий путь между ними х1-х4 ,вес этого пути равен 3. После был составлен путь по граням: всего девять переходов. Дважды встречается переход по грани (4-1), так как степени этих вершин нечетные. Минимальный путь обхода складывается из: 1+2+3+5+6+4+1+2=24- длина эйлерова цикла( его можно просчитать сложив все числа над главной диагональю) 24+3=27(3-путь (4-1),который повторяется) Заключение Были выполнены все поставленные задачи. Было разобрано понятие эйлеровых задач, и именно задачи «китайского почтальона», решение которой базируется на понятии эйлерова цикла. Был изучен известный алгоритм решения данной задачи, и на основе этого была создана программная реализация. Приложения 1 Исходныйкод: //С-матрица смежности,с расстониями //xn-начальная точка //xk-конечнаяточка #include"locale.h" #include"stdafx.h" #include<iostream> #include<string.h> #include<stdio.h> #include<stdlib.h> #include<conio.h> #include"locale.h" #define word unsignedint usingnamespace std; void deikstra(); void no(); void komponenta(int i); void eiler(); void poisk(int i); int a[50][50]; int i, j, p, xn, xk,z,k=1,Mas[100][100],ch=0; int vert[10000];//степеньвершин int way [10000];//Эйлеровцикл int flag[10000];//компоненты связности int x,y,w; int n,m;// m - число дуг, n - число вершин int count;// число компонент связности word c[50][50], l[50]; char s[80], path[80][50]; struct st{ char put[50]; int x1; int x2; int ves; }; st mas[100]; int min(int n) { int i, result; for(i=0;i<n;i++) if(!(flag[i])) result=i; for(i=0;i<n;i++) if((l[result]>l[i])&&(!flag[i])) result=i; return result; } word minim(word x, word y) { if(x<y) return x; return y; } void main(int argc, char* argv[]) { setlocale(LC_ALL, "Russian"); cout<<"введитечислоточек: ";// cin>>n; for(i=0;i<n;i++) for(j=0;j<n;j++) c[i][j]=0; for(i=0;i<n;i++) for(j=i+1;j<n;j++) { cout<<"введите расстояние x"<<i+1<<" до x"<<j+1<<":";// cin>>c[i][j];//записываем расстояния в матрицу с } cout<<" "; for(i=0;i<n;i++) cout<<" X"<<i+1; cout<<endl<<endl; for(i=0;i<n;i++) { printf("X%d",i+1); for(j=0;j<n;j++) { printf("%6d",c[i][j]); c[j][i]=c[i][j]; } printf("\n\n"); } for(i=0;i<n;i++){ for(j=0;j<n;j++) if(c[i][j]==0) c[i][j]=65535; }//бесконечность for(i=0;i<n;i++) { z=0; for(j=0;j<n;j++){ if(c[i][j]!=65535) z++; } if(z%2==1)//ищем вершины с нечетными степенями { Mas[k][0]=i;//сохраняем номера этих вершин Mas[0][k]=i; k++; } } for(int m=1;m<k;m++){ xn=Mas[0][m]; for(j=m;j<k-1;j++) { xk=Mas[j+1][0]; if(xn!=xk) deikstra(); } } eiler(); getch(); } //---------------------------------------------------------------------- void deikstra() { for(i=0;i<n;i++) { flag[i]=0; l[i]=65535; } l[xn]=0; flag[xn]=1; p=xn; itoa(xn+1,s,10);//преобразование числа в символы for(i=1;i<=n;i++) { strcpy(path[i],"X"); strcat(path[i],s); } do { for(i=0;i<n;i++) if((c[p][i]!=65535)&&(!flag[i])&&(i!=p)) { if(l[i]>l[p]+c[p][i]) { itoa(i+1,s,10); strcpy(path[i+1],path[p+1]); strcat(path[i+1],"-X"); strcat(path[i+1],s); } l[i]=minim(l[i],l[p]+c[p][i]); } p=min(n); flag[p]=1; } while(p!=xk); if(l[p]!=65535) { mas[p].ves=(int)l[p]; i=0; while(path[p+1][i]!='\0'){ mas[ch].put[i]=path[p+1][i]; i++; } mas[ch].x1=xk; mas[ch].x2=xn; printf("%i вес\n",mas[p].ves); printf("%s путь \n",mas[ch].put); } else cout<<"ЇгвЁ Ґв!"<<endl; ch++; } //----------------------------------------------------------------------------------------- void eiler() { int sum=0; for(i=0;i<n;i++) for(j=0;j<n;j++){ a[i+1][j+1]=(int) c[i][j]; if(a[i+1][j+1]==65535) a[i+1][j+1]=0; } count=0; for (int i=1;i<n;i++) { if (flag[i]==0) count++; if (count>1 ) no();// графнесвязен //komponenta(i); } for (int i=1;i< n;i++) if (vert[i]%2==1) no(); // есть вершины нечётной степени w=0; poisk(1); way[0]=way[1]; for (int i=1;i<=w;i++){ if((int)c[way[i]-1][way[i+1]-1]==65535){ for(j=0;j<ch;j++){ if((mas[j].x1+1==way[i]&&mas[j].x2+1==way[i+1])||(mas[j].x2+1==way[i]&&mas[j].x1+1==way[i+1])){ printf("%s-",mas[p].put); sum=sum+mas[p].ves; way[0]=mas[p].x1; } } } else printf("X%i-",way[i]); } if(way[0]!=way[w]){ if((int)c[way[1]-1][way[w]-1]!=65535){ printf("X%i",way[1]); sum=sum+(int)c[way[i]-1][way[w]-1]; } else{ for(j=0;j<ch;j++){ if(mas[p].x1==way[1]&&mas[p].x2==way[w-1]){ printf("%s-",mas[p].put); sum=sum+mas[p].ves; } } } } for (int i=0;i<=w;i++){ if((int)c[way[i]-1][way[i+1]-1]!=65535) sum=(int)c[way[i]-1][way[i+1]-1]+sum; } printf("\n"); printf("веспути %i ",sum); } //--------------------------------------------------- void no(){ printf("Эйлеров цикл не существует!"); exit(0); } //--------------------------------------------------- void komponenta(int i){ int z; flag[i]=count; for (int z=1;p<=n;j++) if ((a[i][z])&&(flag[z]==0)) komponenta(z); } //--------------------------------------------------- void poisk(int i){ int j; for (int j=1;j<=n;j++) if (a[i][j]!=0){ a[i][j]=0; a[j][i]=0; poisk(j); } w++; way[w]=i; } Список использованной литературы 1. В.М. Бондарев, В.И. Рублинецкий, Е.Г. Качко. Основы программирования, 1998 г. 2. Н. Кристофидес. Теория графов: алгоритмический подход, Мир, 1978 г. 3. Ф.А. Новиков. Дискретная математика для программистов, Питер, 2001 г. 4. В.А. Носов. Комбинаторика и теория графов, МГТУ, 1999 г. 5. О. Оре. Теория графов, Наука, 1982 г.
Страницы: 1, 2, 3, 4
|