全部资源
全部资源
C/C++
C#
PHP
Java
Python
VB
ASP
Html/CSS
Matlab
JavaScript
数据库
模板
其他

满足三角不等式的TSP问题的近似算法

收藏(0)
  • 大小: 5.37MB
    文件类型: .zip
    金币: 2
    下载: 0 次
    发布日期: 2023-10-23
  • 语言: 其他
  • 标签: 算法  C++  欧拉图  
高速下载

资源简介

完美版满足三角不等式的TSP问题的近似算法，内部含有课程设计报告和源程序，适合大学数据与算法分析课程学习。 满足三角不等式的TSP问题的近似算法： (1)描述及输入原始数据模块 (2)求解最小生成树模块 (3)构造欧拉图模块 (4)搜索欧拉回路模块 (5)抄近路计算模块 (6)存储及输出结果模块

资源截图

小图 大图

代码片段和文件信息 

#include 
#include
#include
#include
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define PI acos（-1.0）
#define mem（ab） memset（absizeof（a））
#define sca（a） scanf（“%d“&a）
#define pri（a） printf（“%d\n“a）
#define M 202
#define INF 100000001
using namespace std;
int v0[10000];
int u0[10000];;
int m = 0;
int n = 0;
int cout0 = 0;
typedef long long ll;
struct stack
{
	int top node[M];
}s;
int e[M][M];
int suiji[3][10000];

void RAND（int max int min int n）
{
	srand（（unsigned）time（NULL））;
	for （int i = 1; i <= max; ++i）
	{
		for （int j = 1; j <= i; ++j）
			if （i != j）
			{
				suiji[0][cout0] = j;
				suiji[1][cout0] = i;
				cout0++;
			}
	}
	int c = 2;
	int j = 0;
	int c1 = 0;
	srand（（unsigned）time（NULL））;
	for （int i = 0; i	{
		suiji[2][i] = 3;
	}
	suiji[2][0] = 2;
	while （j	{

		suiji[2][j + c] = 2;
		j = j + c;
		c1++;
		c++;
		if （c1 == max - 2）
		{
			suiji[0][n - 1] = 2;
		}
	}


}

void dfs（int x）
{
	int i;
	s.node[++s.top] = x;

	for （i = 0; i	{
		if （e[i][x]>0）
		{
			e[i][x] = e[x][i] = 0;  //删除这条边
			dfs（i）;
			break;
		}
	}
}
void fleury（int x）
{
	int i flag;
	s.top = 0; s.node[s.top] = x;
	while （s.top >= 0）
	{
		flag = 0;
		for （i = 0; i		{
			if （e[s.node[s.top]][i]>0）
			{
				flag = 1;
				break;
			}
		}
		if （!flag） printf（“%d “ s.node[s.top--] + 1）;
		else dfs（s.node[s.top--]）;
	}
	puts（““）;

}
//检验输入边数和顶点数的值是否有效，可以自己推算为啥：
//顶点数和边数的关系是：（（Vexnum*（Vexnum - 1）） / 2） < edge
bool check（int Vexnum int edge） {
	if （Vexnum <= 0 || edge <= 0 || （（Vexnum*（Vexnum - 1）） / 2） < edge）
		return false;
	return true;
}

//顶点从1开始编号
bool check_edge（int Vexnum int start int end int weight） {
	if （start<1 || end<1 || start>Vexnum || end>Vexnum || weight < 0） {
		return false;
	}
	return true;
}

//边集结构，用于保存每条边的信息
typedef struct edge_tag {
	bool visit; //判断这条边是否加入到了最小生成树中
	int start;   //该边的起点
	int end;   //该边的终点
	int weight; //该边的权重
}Edge;

//创建一个图，但是图是使用边集结构来保存
void createGraph（Edge * &e int Vexnum int edge） {
	e = new Edge[edge];//为每条边集开辟空间
	int start = 0;
	int end = 0;
	int weight = 0;

	int i = 0;

	while （i != edge）
	{
		start = suiji[0][i];
		end = suiji[1][i];
		weight = suiji[2][i];
		cout << start << “ “ << end << “ “ << weight;
		cout << “ | “;
		while （!check_edge（Vexnum start end weight）） {
			cout << “输入的值不合法，请重新输入每条边的起点、终点和权重：“ << endl;
			start = suiji[0][i];
			end = suiji[1][i];
			weight = suiji[2][i];
		}
		e[i].start = start;
		e[i].end = end;
		e[i].weight = weight;
		e[i].visit = false; //每条边都还没被初始化
		++i;

	}
}
int cmp（const void*  first const void * second） {
	return （（Edge *）first）->weight - （（Edge *）second）->weight;
}
int find_root（int 

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2018-07-15 20:53  满足三角不等式的TSP问题的近似算法\
     目录           0  2018-07-15 20:40  满足三角不等式的TSP问题的近似算法\.vs\
     目录           0  2018-07-15 20:40  满足三角不等式的TSP问题的近似算法\.vs\满足三角不等式的TSP问题的近似算法\
     目录           0  2018-07-15 20:41  满足三角不等式的TSP问题的近似算法\.vs\满足三角不等式的TSP问题的近似算法\v15\
     文件       30208  2018-07-15 20:41  满足三角不等式的TSP问题的近似算法\.vs\满足三角不等式的TSP问题的近似算法\v15\.suo
     文件     7073792  2018-07-15 20:41  满足三角不等式的TSP问题的近似算法\.vs\满足三角不等式的TSP问题的近似算法\v15\Browse.VC.db
     目录           0  2018-07-15 20:40  满足三角不等式的TSP问题的近似算法\.vs\满足三角不等式的TSP问题的近似算法\v15\ipch\
     文件     3670016  2018-07-15 20:40  满足三角不等式的TSP问题的近似算法\.vs\满足三角不等式的TSP问题的近似算法\v15\ipch\1833d73b8401f2b2.ipch
     目录           0  2018-07-15 20:45  满足三角不等式的TSP问题的近似算法\Debug\
     文件      429808  2018-07-15 20:40  满足三角不等式的TSP问题的近似算法\Debug\满足三角不等式的TSP问题的近似算法.ilk
     文件      684032  2018-07-15 20:40  满足三角不等式的TSP问题的近似算法\Debug\满足三角不等式的TSP问题的近似算法.pdb
     文件      292352  2018-07-15 20:53  满足三角不等式的TSP问题的近似算法\报告.doc
     目录           0  2018-07-15 20:40  满足三角不等式的TSP问题的近似算法\满足三角不等式的TSP问题的近似算法\
     目录           0  2018-07-15 20:50  满足三角不等式的TSP问题的近似算法\满足三角不等式的TSP问题的近似算法-程序\
     目录           0  2018-07-15 20:40  满足三角不等式的TSP问题的近似算法\满足三角不等式的TSP问题的近似算法-程序\.vs\
     目录           0  2018-07-15 20:40  满足三角不等式的TSP问题的近似算法\满足三角不等式的TSP问题的近似算法-程序\.vs\满足三角不等式的TSP问题的近似算法\
     目录           0  2018-07-15 20:52  满足三角不等式的TSP问题的近似算法\满足三角不等式的TSP问题的近似算法-程序\.vs\满足三角不等式的TSP问题的近似算法\v15\
     文件       20480  2018-07-15 20:52  满足三角不等式的TSP问题的近似算法\满足三角不等式的TSP问题的近似算法-程序\.vs\满足三角不等式的TSP问题的近似算法\v15\.suo
     文件      253952  2018-07-15 20:52  满足三角不等式的TSP问题的近似算法\满足三角不等式的TSP问题的近似算法-程序\.vs\满足三角不等式的TSP问题的近似算法\v15\Browse.VC.db
     目录           0  2018-07-15 20:40  满足三角不等式的TSP问题的近似算法\满足三角不等式的TSP问题的近似算法-程序\.vs\满足三角不等式的TSP问题的近似算法\v15\ipch\
     文件     3670016  2018-07-15 20:40  满足三角不等式的TSP问题的近似算法\满足三角不等式的TSP问题的近似算法-程序\.vs\满足三角不等式的TSP问题的近似算法\v15\ipch\1833d73b8401f2b2.ipch
     目录           0  2018-07-15 20:45  满足三角不等式的TSP问题的近似算法\满足三角不等式的TSP问题的近似算法-程序\Debug\
     文件      429808  2018-07-15 20:40  满足三角不等式的TSP问题的近似算法\满足三角不等式的TSP问题的近似算法-程序\Debug\满足三角不等式的TSP问题的近似算法.ilk
     文件      684032  2018-07-15 20:40  满足三角不等式的TSP问题的近似算法\满足三角不等式的TSP问题的近似算法-程序\Debug\满足三角不等式的TSP问题的近似算法.pdb
     目录           0  2018-07-15 20:40  满足三角不等式的TSP问题的近似算法\满足三角不等式的TSP问题的近似算法-程序\满足三角不等式的TSP问题的近似算法\
     文件       11240  2018-07-15 20:48  满足三角不等式的TSP问题的近似算法\满足三角不等式的TSP问题的近似算法-程序\满足三角不等式的TSP问题的近似算法.cpp
     文件        1558  2018-07-15 20:40  满足三角不等式的TSP问题的近似算法\满足三角不等式的TSP问题的近似算法-程序\满足三角不等式的TSP问题的近似算法.sln
     目录           0  2018-07-15 20:40  满足三角不等式的TSP问题的近似算法\满足三角不等式的TSP问题的近似算法-程序\满足三角不等式的TSP问题的近似算法\Debug\
     文件        7128  2018-07-15 20:40  满足三角不等式的TSP问题的近似算法\满足三角不等式的TSP问题的近似算法-程序\满足三角不等式的TSP问题的近似算法\Debug\stdafx.obj
     文件      191488  2018-07-15 20:40  满足三角不等式的TSP问题的近似算法\满足三角不等式的TSP问题的近似算法-程序\满足三角不等式的TSP问题的近似算法\Debug\vc141.idb
     文件      430080  2018-07-15 20:40  满足三角不等式的TSP问题的近似算法\满足三角不等式的TSP问题的近似算法-程序\满足三角不等式的TSP问题的近似算法\Debug\vc141.pdb
............此处省略42个文件信息

评论

共有 条评论

相关资源