реализовать задачу китайского почтальона

[Лила]

Очень нужна помощь в реализации "задачи китайского почтальона на Си(Си++)"
Суть задачи в том, что задается граф матрицей смежности, с весами каждого ребра.
нужно найти минимальный путь обхода всех ребер графа,по ребрам можно идти по нескольку раз.
По примеру...если смотреть в учебнике он состоит из 3 алгоритмов. Алгоритма Дейкстра, алгоритма минимального паросочетания ,
и алгоритма нахождения Эйлерова цикла.

[Лила]

у меня готовые есть Эйлера

#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[i][j]);
		}
	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);
	for (int i=1;i< w;i++)
		printf("%i ",way[i]);
}

//---------------------------------------------------
void no(){
	printf("Эйлеров цикл не существует!");
	exit(0);
}
//---------------------------------------------------
void komponenta(int i){
	int j;
	flag[i]=count;
	for (int j=1;j<=n;j++)
		if ((a[i][j])&&(flag[j]==0))
			komponenta(j);
 }

//---------------------------------------------------
void poisk(int i){
int  j;
 for (int j=1;j<=n;j++)
 	 if (a[i][j]){ 
    a[i][j]=0;
    a[j][i]=0;
    poisk(j);
	 }
  w++;
 way[w]=i;
}

[Лила]

и Дейкстра .

// deykstra.cpp : Defines the entry point for the console application.
//

//С-матрица смежности,с расстониями 
//xn-начальная точка
//xk-конечная точка
#include "stdafx.h"
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include "locale.h"
#define word unsigned int
using namespace std;
void deikstra();
int i, j, n, p, xn, xk,z,Mas[100][100][100],k=1;
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<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[])
{
	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<<":";//введите расстояние от x1 до X2
		    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; }//бесконечность
	/*cout<<"Ќ*з*«м**п в®зЄ*: ";//начальная точка
	cin>>xn;//запомнинаем начальную и конечную точку
	cout<<"Љ®*Ґз**п в®зЄ*: ";//конечноая точка
	cin>>xk;
	xk--;
	xn--;
	if(xn==xk)
	{
		cout<<"Ќ*з*«м**п Ё Є®*Ґз**п в®зЄЁ б®ўЇ*¤*ов."<<endl;//гачальная и конечная точка совпадают
		getch();
		//return;
	}*/
	
	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][0]=i;//сохраняем номера этих вершин
			Mas[0][k][0]=i;
			k++;
		}

	}
	
	for(int m=1;m<k;m++){
		xn=Mas[0][m][0];
		for(j=m;j<k-1;j++)
		{
			xk=Mas[j+1][0][0];
			if(xn!=xk)
			deikstra();
		}
	}
	for(int l=0;l<k;l++){
for(int j=0;j<k;j++)
	printf("%i ",&Mas[l][j][0]);
	printf("\n");
	}

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)
	{
		cout<<"Џгвм: "<<path[p+1]<<endl;//путь
		cout<<"„«Ё** ЇгвЁ: "<<l[p]<<endl;//длина пути
		Mas[xn][xk][0]=(int)l[p];
		//Mas[xn][xk][p]=(int)path[p+1];
		//cout<<"Џгвм: "<<Mas[xn][xk][0]<<endl;//путь
		//cout<<"„«Ё** ЇгвЁ: "<<Mas[xn][xk][p]<<endl;//длина пути
	}
	else
		cout<<"ЇгвЁ *Ґв!"<<endl;
}

[Лила]

если кто-то может помочь написать-помогите.Я в долгу не останусь...в разумных пределах конечно))))

[Лила]

так же есть Венгерский алгоритм...но он не мой...я его не понимаю совсем...и он через вектора решает...что очень печально...но может вам это что то скажет
#include <vector>
#include <limits>
using namespace std;

typedef pair<int, int> PInt;
typedef vector<int> VInt;
typedef vector<VInt> VVInt;
typedef vector<PInt> VPInt;

const int inf = numeric_limits<int>::max();

/*
* Решает задачу о назначениях Венгерским методом.
* matrix: прямоугольная матрица из целых чисел (не обязательно положительных).
* Высота матрицы должна быть не больше ширины.
* Возвращает: Список выбранных элементов, по одному из каждой строки матрицы.
*/
VPInt hungarian(const VVInt &matrix) {

// Размеры матрицы
int height = matrix.size(), width = matrix[0].size();

// Значения, вычитаемые из строк (u) и столбцов (v)
VInt u(height, 0), v(width, 0);

// Индекс помеченной клетки в каждом столбце
VInt markIndices(width, -1);

// Будем добавлять строки матрицы одну за другой
for(int i = 0; i < height; i++) {
VInt links(width, -1);
VInt mins(width, inf);
VInt visited(width, 0);

// Разрешение коллизий (создание "чередующейся цепочки" из нулевых элементов)
int markedI = i, markedJ = -1, j;
while(markedI != -1) {
// Обновим информацию о минимумах в посещенных строках непосещенных столбцов
// Заодно поместим в j индекс непосещенного столбца с самым маленьким из них
j = -1;
for(int j1 = 0; j1 < width; j1++)
if(!visited[j1]) {
if(matrix[markedI][j1] - u[markedI] - v[j1] < mins[j1]) {
mins[j1] = matrix[markedI][j1] - u[markedI] - v[j1];
links[j1] = markedJ;
}
if(j==-1 || mins[j1] < mins[j])
j = j1;
}

// Теперь нас интересует элемент с индексами (markIndices[links[j]], j)
// Произведем манипуляции со строками и столбцами так, чтобы он обнулился
int delta = mins[j];
for(int j1 = 0; j1 < width; j1++)
if(visited[j1]) {
u[markIndices[j1]] += delta;
v[j1] -= delta;
} else {
mins[j1] -= delta;
}
u[i] += delta;

// Если коллизия не разрешена - перейдем к следующей итерации
visited[j] = 1;
markedJ = j;
markedI = markIndices[j];
}

// Пройдем по найденной чередующейся цепочке клеток, снимем отметки с
// отмеченных клеток и поставим отметки на неотмеченные
for(; links[j] != -1; j = links[j])
markIndices[j] = markIndices[links[j]];
markIndices[j] = i;
}

// Вернем результат в естественной форме
VPInt result;
for(int j = 0; j < width; j++)
if(markIndices[j] != -1)
result.push_back(PInt(markIndices[j], j));
return result;
}

[Лила]

так же есть Венгерский алгоритм...но он не мой...я его не понимаю совсем...и он через вектора решает...что очень печально...но может вам это что то скажет
#include <vector>
#include <limits>
using namespace std;

typedef pair<int, int> PInt;
typedef vector<int> VInt;
typedef vector<VInt> VVInt;
typedef vector<PInt> VPInt;

const int inf = numeric_limits<int>::max();

/*
* Решает задачу о назначениях Венгерским методом.
* matrix: прямоугольная матрица из целых чисел (не обязательно положительных).
* Высота матрицы должна быть не больше ширины.
* Возвращает: Список выбранных элементов, по одному из каждой строки матрицы.
*/
VPInt hungarian(const VVInt &matrix) {

// Размеры матрицы
int height = matrix.size(), width = matrix[0].size();

// Значения, вычитаемые из строк (u) и столбцов (v)
VInt u(height, 0), v(width, 0);

// Индекс помеченной клетки в каждом столбце
VInt markIndices(width, -1);

// Будем добавлять строки матрицы одну за другой
for(int i = 0; i < height; i++) {
VInt links(width, -1);
VInt mins(width, inf);
VInt visited(width, 0);

// Разрешение коллизий (создание "чередующейся цепочки" из нулевых элементов)
int markedI = i, markedJ = -1, j;
while(markedI != -1) {
// Обновим информацию о минимумах в посещенных строках непосещенных столбцов
// Заодно поместим в j индекс непосещенного столбца с самым маленьким из них
j = -1;
for(int j1 = 0; j1 < width; j1++)
if(!visited[j1]) {
if(matrix[markedI][j1] - u[markedI] - v[j1] < mins[j1]) {
mins[j1] = matrix[markedI][j1] - u[markedI] - v[j1];
links[j1] = markedJ;
}
if(j==-1 || mins[j1] < mins[j])
j = j1;
}

// Теперь нас интересует элемент с индексами (markIndices[links[j]], j)
// Произведем манипуляции со строками и столбцами так, чтобы он обнулился
int delta = mins[j];
for(int j1 = 0; j1 < width; j1++)
if(visited[j1]) {
u[markIndices[j1]] += delta;
v[j1] -= delta;
} else {
mins[j1] -= delta;
}
u[i] += delta;

// Если коллизия не разрешена - перейдем к следующей итерации
visited[j] = 1;
markedJ = j;
markedI = markIndices[j];
}

// Пройдем по найденной чередующейся цепочке клеток, снимем отметки с
// отмеченных клеток и поставим отметки на неотмеченные
for(; links[j] != -1; j = links[j])
markIndices[j] = markIndices[links[j]];
markIndices[j] = i;
}

// Вернем результат в естественной форме
VPInt result;
for(int j = 0; j < width; j++)
if(markIndices[j] != -1)
result.push_back(PInt(markIndices[j], j));
return result;
}

[pswd]

Готов решить данную проблему. напиши мне на почту и договоримся обо всем
roman.tarabanov (собака) live.ru

[Лила]

474322419
если есть возможность, пишите в ICQ)

[pswd]

Код на C++
#include <stdlib.h>
#include <time.h>
#include <stdio.h>

int wpchk(int w, int *wpts)
{
int i=0;
int flg=0;
while(wpts[i]!=-1)
{
if(wpts[i]==w){flg=1;}
i++;
}

if (flg==0) {return 0;} else return 1;
}

void main()
{
srand( (unsigned)time( NULL ) );

//int prices[10][10];
int waypoint[11]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,1};
int way[11]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
int start=-1;
int end=-1;
int min;
int imin;

*/// 0 1 2 3 4 5 6 7 8 9
int prices[10][10]={0, 0, 0, 0, 0, 0, 0, 0, 0, 0, //0
0, 0, 2, 9, 8, 0, 0, 0, 0, 0, //1
0, 2, 0, 3, 0, 20,0, 0, 0, 0, //2
0, 9, 3, 0, 7, 4, 0, 0, 0, 0, //3
0, 8, 0, 7, 0, 11,0, 0, 0, 0, //4
0, 0, 20,4, 11,0, 0, 0, 0, 0, //5
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, //6
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, //7
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, //8
0, 0, 0, 0, 0, 0, 0, 0, 0, 0};//9

printf("Enter № of start location:");
scanf("%i",&start);
printf("Enter № of finish location:");
scanf("%i",&end);
waypoint[0]=start;
int n=0;
int w;
while(waypoint[n]!=end)
{
min=0;
w=waypoint[n];
for(int i=0;i<10;i++)
{
if(((min==0)||((prices[w][i]<min)&&(prices[w][i]>0)))&&wpchk(i,waypoint)==0) {min=prices[w][i];imin=i;}
}
n++;
waypoint[n]=imin;
}

printf("\nThe way is:\n");
int i=0;
while(waypoint[i]!=-1)
{
printf("%i ",waypoint[i]);
i++;
}
getchar();
getchar();
}

[Лила]

просьба все еще в силе.
P.S. задача комевояжера и почтальона совершенно разнвые вещи.