на тему рефераты Информационно-образоательный портал
Рефераты, курсовые, дипломы, научные работы,
на тему рефераты
на тему рефераты
МЕНЮ|
на тему рефераты
поиск
Эйлеровы циклы. Задача "Китайского почтальона"
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



© 2003-2013
Рефераты бесплатно, курсовые, рефераты биология, большая бибилиотека рефератов, дипломы, научные работы, рефераты право, рефераты, рефераты скачать, рефераты литература, курсовые работы, реферат, доклады, рефераты медицина, рефераты на тему, сочинения, реферат бесплатно, рефераты авиация, рефераты психология, рефераты математика, рефераты кулинария, рефераты логистика, рефераты анатомия, рефераты маркетинг, рефераты релиния, рефераты социология, рефераты менеджемент.