hamilton.cpp

简单写了个一个哈密顿回路

#include <iostream>
#include <stdlib.h> 
#include <stdio.h> 
#include <time.h> 
#include "windows.h"
// #include <mmsystem.h>
// #pragma comment(lib,"winmm.lib") 
// 


using namespace std;
#define MAX  15

int **a;
int *visited = new int[MAX];
int * path = new int[MAX];
int sum = 99999;
int v;
int *minipath = new int[MAX];



void DFSBack()
{
	int s = 0;
	for (int i = 1; i < MAX; i++)
	{
		s+= a[path[i-1]][path[i]];
	}
	s+= a[path[i-1]][path[0]];
	if (s < sum)
	{
		sum = s;
		for (int j = 0; j < MAX; j++)
		{
			minipath[j] = path[j];
		}
	}
}


void DFS(int index)
{
	if (index == MAX)
	{
		DFSBack();
		return;
	}
	else
	{
		for (int i = 0; i < MAX; i++)
		{
			if (visited[i]==0 && a[index][i]!=0)
			{
				path[index] = i;

				v+=a[path[index-1]][i];
				if (v > sum)
				{
					v -= a[path[index-1]][i];
					continue;
				}

				visited[i] = 1;				
				DFS(index+1);
				visited[i] = 0;
				
				v -= a[path[index-1]][i];
			}
		}
	}
}



void main()
{
//	DWORD start = timeGetTime(); 

	int i;
	a = new int*[MAX];
	for (i = 0; i < MAX; i++)
	{
		a[i] = new int[MAX];
		visited[i] = path[i] = 0;
	}

	int array[][MAX] = {{1,2,3,4,6,8},
		{1,2,3,1,5,4},
		{3,2,1,2,3,1},
		{1,2,3,1,5,4},
		{1,2,3,1,5,4},
		{1,2,3,1,5,4}};
// 
// 	for (i = 0; i < MAX; i++)
// 	{
// 		for (int j = 0; j <MAX; j++)
// 		{
// 			a[i][j] = array[i][j];
// 		}		
// 	}
// 	
	srand(time(NULL)); 
	for (i = 0; i < MAX; i++)
	{
		for (int j = 0; j <MAX; j++)
		{			
			int r = 1 + rand()%MAX;
			a[i][j] = r;
		}
	}



	path[0] = 0;
	visited[0] = 1;

	DFS(1);

	for (i = 0; i < MAX; i++)
	{
		cout<<minipath[i]<<" ";
	}
	cout<<endl;
	
	for (i = 0; i < MAX; i++)
	{
		cout<<a[minipath[i]][minipath[(i+1+MAX)%MAX]]<<" ";
	}
	cout<<endl;
	cout<<sum;

// 	DWORD end = timeGetTime(); 
//	cout<< "Past Time: "<< (end - start)<<endl; 

	FILETIME f1,f2,f3,f4; 
	SYSTEMTIME s1,s2,s3,s4; 
	GetProcessTimes(GetCurrentProcess(),&f1,&f2,&f3,&f4);//注意传递进取的是地址，有& 
	FileTimeToSystemTime(&f4,&s4);//还是地址，转换时间类型 
	//cout<<f4.dwLowDateTime<<endl;//输出的是64位的地位 
	cout<<s4.wSecond*1000+s4.wMilliseconds<<endl;//这里我把时间转化成毫秒了 


}