задача китайского почтальона

[california]

Очень нужна помощь в реализации "задачи китайского почтальона на Си(Си++)"

Суть задачи в том, что задается граф матрицей смежности, с весами каждого ребра.

нужно найти минимальный путь обхода всех ребер графа,по ребрам можно идти по нескольку раз.

По примеру...если смотреть в учебнике он состоит из 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 int

using 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; first

if (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; i

if (g[v] && !used)

{

used = true;

q[t++] = i;

}

}

for (int i=0; i

if (!used && degree > 0)

return false;

return true;

}

void find_euler_cycle (graph&g, vector&degree, 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; i

if (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; i

if (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; i

if (degree % 2 == 1)

if (im_v1 == -1)

im_v1 = i;

else

im_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; i

if (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; i

cout << result+1;

}

}

Добавлено спустя 1 минуту 35 секунд:

а как это все в кучу собрать....и паросочетание найти я не знаю(((

помогите пожалуйста....у меня идей уже нет никаких(

[danger]

дали задачу довольно таки не простую задачу человеку который даже векторы подинклудить не может...

[california]

спасибо за комментарий..но все же..

[0xDEADBEEF]

Лезем на e-maxx.ru и смотрим алгоритмы.

Нормальная реализация алгоритма Дейкстры (Dijkstra)

Паросочетание можно искать любым потоковым алгоритмом (они на мой взгляд проще), или Венгерским алгоритмом (он быстрее).

Эйлеров цикл - самым обычным способом. К стати впервые вижу у этого алгоритма имя.

Вообще это типичная задача спортивного программирования. Финалисты ACM такие вещи пишут по утрам, в качестве зарядки =)

Вообще у нас в регионе создается сообщество людей, которые стремятся совершенствовать свои программисткие навыки, эрудицию и мыслительный процесс самым лучшим для этого способом - занятием спортивным программированием.

Подробнее - Группа ВКотакте

[california]

я в роде бы нахождение Эйлерова пути написала...только понять не могу...он правильно или нет работает....если не сложно,пожалуйста посмотрите...я вообще то, что надо написала...или нет.

#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]

Паросочетание искать либо Венгерским алгоритмом, либо любым алгоритмом максимального потока минимальной стоимости.

Поиск Эйлерова цикла написан правильно, за исключением проверки степени вершин - массив степеней банально не заполняется.

[california]

а что делать ... с Эйлеровым циклом...если по условию мы передаем туда нечетные вершины?

[0xDEADBEEF]

1. В исходном графе Г' находятся все вершины нечетной степени, если таковых нет то п. 6.

2. Для каждой такой вершины находятся кратчайшие пути до всех остальных, эти пути запоминаются.

3. На этих вершинах строится двудольный граф Г' с весами, равными кратчайшему расстоянию (на рисунке 2 видна соответствующая матрица смежности для сэмпла)

4. Ищем максимальное паросочетание минимального веса.

5. По паросочетанию добавляем в исходный граф дополнительные ребра. Т.е. если у нас в паросочетании Г' есть ребро (A,, то в Г добавляется цепь кратчайшего пути м/у вершинами А и В. Получаем эйлеров граф.

6. Находим эйлерову цепь.

7. ....

8. PROFIT!

Вот примерно так это должно выглядеть.

Можно узнать где такие задачи дают?

[california]

можно, в ВСГТУ по Дискретной математике

[california]

0xDEADBEEF

огромное спасибо))

я таки прогу дописала, и защитила ))

спасибо за алгоритм...иначе бы в жизнь не поняла, что делать вообще надо!)

[Max4406]

девушка программист? *85

[D_Master]

девушка программист? *85

Встречаются) И теперь уже можно не удивляться :-)

[0xDEADBEEF]

california

Ня1 незачто.

Спортивным программированием не желаете заняться?

Люди умеющие писать такие вещи у нас, к сожалению, редкость.

[california]

да...я как бы занимаюсь уже потихоньку...новичок, но стараюсь))

еще раз спасибо .