蛮力法解决旅行商问题（穷举查找求最短路径）含解析与代码实现

【数据结构与算法】专题正在持续更新中，各种数据结构的创建原理与运用，经典算法的解析都在这儿，欢迎大家前往订阅本专题，获取更多详细信息哦

🪔本系列专栏 -  数据结构与算法_勾栏听曲_0

欢迎大家    点赞  评论  收藏️

个人主页 - 勾栏听曲_0的博客

希望本文能对你有所帮助，如有不足请指正，共同进步吧

君子之道，暗然而日章；小人之道，明然而日亡。

目录

蛮力算法

蛮力算法的初步运用

旅行商问题

问题解析

代码实现

        普通程序运行时间计时

        高精度程序运行时间计时

        随机数生成（一秒内）

        解决旅行商问题

有需要其他算法来解决最短路径，可看这篇文章 最短路径之基于贪心算法的迪杰斯特拉dijkstra算法（有图解，含码源

蛮力算法

        在算法运用之前，我们先来了解一下蛮力算法

什么是蛮力法？

是一种简单直接地解决问题的方法，常常基于问题的描述和所涉及的概念定义，没有特别巧妙的设计策略。

例如：计算
a
n
值的蛮力法就是乘上
n
次的
a
。

蛮力法的缺点：通常效率很低

蛮力算法的初步运用

        选择排序和冒泡排序是解决排序问题最直截了当的方法。而选择排序和冒泡排序也正是使用蛮力算法的思想。

        选择排序每次扫描数组，找到最小（或最大）元素，并与扫描开始处的元素进行交换。每次都会从当前位置将整个数组扫描一遍，这就是蛮力算法的思想。

        冒泡排序比较相邻元素，如果逆序就交换它们的位置，每次将最大的元素沉到最后位置（相对地，较小/轻的元素往上冒）。如此扫描数组n-1次即可排序完成。同样的，每一次扫描也会从当前位置将整个数组扫描一遍。

        我们以选择排序来举个例子：对数组89, 45, 68, 90, 29, 34, 17进行选择排序（标黄为已排序好了的）

        每次将数组遍历一遍，找到当前最小的数，排序好这个数后，重复这个过程，直到全部排完。

旅行商问题

问题解析

        旅行商问题：给定n个城市，从一个城市出发找出一条连通n个城市的最短路径，且回到出发城市前，对每个城市都只访问一次。

        旅行商问题可以用加权图来建模，即顶点代表城市，边代表城市间的距离。这样，旅行商问题实际就可以表述为求一个图的最短哈密顿回路（注：对图的每个顶点只穿越一次的回路）问题。

        哈密顿回路可定义为n+1个相邻顶点v(i0 ),v(i1 ),…,v(in-1 ),v(i0 )的序列，其中，中间的n-1个顶点互不相同。一旦中间的n-1个顶点的顺序确定，哈密顿回路及其线路长度就确定了。

        穷举查找解决旅行商问题：首先穷举n-1个顶点的所有排列组合并计算路径长度，然后从中查找出线路最短的一个。

代码实现

        普通程序运行时间计时

        使用库中的函数来完成计时，不过精度只有毫秒‘

#include <time.h>　　　//引入头文件
int main()
{
    clock_t start,end;　　　//定义clock_t变量
    start = clock();  　　　//开始时间

    fun()  //需计时的函数

    end = clock();   //结束时间
    cout<<"time = "<<double(end-start)/CLOCKS_PER_SEC<<"s"<<endl;  //输出时间（单位：ｓ）
}

        高精度程序运行时间计时

        这个高精度计数的方法想要用到<windows.h>的头文件，是以微秒为单位，但是QueryPerformanceCounter()确切的精确计时的最小单位是与系统有关的。

#include <windows.h>　　　//引入头文件
int main()
{
    LARGE_INTEGER t1,t2,tc;
    QueryPerformanceFrequency(&tc);
    QueryPerformanceCounter(&t1);

    fun()  //需计时的函数

    QueryPerformanceCounter(&t2);
    time=(double)(t2.QuadPart-t1.QuadPart)/(double)tc.QuadPart; 
    cout<<"time = "<<time<<endl;  //输出时间（单位：ｓ）
}

        随机数生成（一秒内）

        生成随机数最常见的方法是用内置的函数rand()函数，再由srand()函数（用于给rand()函数设定种子）配合time() 函数获取不同的种子，由此来生成随机数。但是有一个缺点，那就是time()获取的时间是秒，而程序运行速度较快时，在同一秒中生生成了多个随机数，那么他们的种子就都是相同的，生成的随机数也是一样的。所以这个方法并不是特别实用。

        在这里我们来介绍一种利用硬件可以在一秒内生成多个随机数的方法，其原理与上面类似，不过这个取的种子的精度并不是秒，而是微秒，这样就能最大程度的保障每一次生成随机数的种子都是不同的。

/*
Random：一秒内生成不同随机数
参数： 
	@n : 为精度,即运算中保留小数点后几位
	@min:随机数的最小取值 
	@max: 随机数的最大取值
*/ 
int Random(int n,int min,int max)
{
	LARGE_INTEGER seed;
	QueryPerformanceFrequency(&seed);//返回硬件支持的高精度计数器的频率
	QueryPerformanceCounter(&seed);//函数返回高精确度性能计数器的值,它可以以微妙为单位计
	srand(seed.QuadPart);    //初始化一个以微秒为单位的时间种子
    int Precision = pow(10,n) - 1;
   
    return (int)((rand() % Precision / (float)(Precision + 1))*pow(10,n)) % max + min;
}

        解决旅行商问题

        先看视频解析：

        代码实现：

#include <iostream>
#include <cstdio>
#include <cstring>

#include <iostream>
#include <profileapi.h>
#include <Math.h>

#include <windows.h>

using namespace std;
#define maxx 9999
int l[maxx][maxx];    //存储两个城市之间的距离
int n，min_l = 65535; //城市数量，最短路径
int sum[maxx];        //标记每条路线的路程总长度
int go_city = 0;      //标记从第go_city个城市出发
int visited[maxx];    //visited[i]=1时，第i个城市已经去过;反之则为visited[i]=0;
int path_index = 1;   //已经去过的城市数目。
int path[maxx][maxx]; //存储经过城市的路线
int route = 0;        //存储第几条路线
int min_path[maxx];   //存储最短路径 

int recursion(int index)
{
    if(path_index != n)
    {
        for(int i=1;i <= n;i++)
        {
            if(visited[i] == 0)
            {
                visited[i] = 1;
                path[route][path_index] = index;
                path_index++;
                recursion(i);
                //回溯
                path_index--;
                visited[i] = 0;
            }
        }
    }
    else
    {
        path[route][path_index] = index;
        path[route][path_index + 1] = go_city;
        //计算每条路线的路程总长度
        sum[route] = 0;
        for(int i=1;i<=n;i++)
        {
            sum[route] += l[ path[route][i] ][ path[route][i+1] ];
            //当route+1后，path[route][i]的前面需要保持，后面变化。
            path[route+1][i] = path[route][i];
        }
        if(min_l > sum[route])        //如果线路长度小于最小值，则更新最短路径和最短距离
        {
        	for(int i=1;i<=n;i++)
	        {
	            min_path[i] = path[route][i];
	        }
            min_l = sum[route];
        }
        route++;
    }
    return 0;
}


/*
Random：一秒内生成不同随机数
参数： 
	@n : 为精度,即运算中保留小数点后几位
	@min:随机数的最小取值 
	@max: 随机数的最大取值
*/ 
int Random(int n,int min,int max)
{
	LARGE_INTEGER seed;
	QueryPerformanceFrequency(&seed);//返回硬件支持的高精度计数器的频率
	QueryPerformanceCounter(&seed);//函数返回高精确度性能计数器的值,它可以以微妙为单位计
	srand(seed.QuadPart);    //初始化一个以微秒为单位的时间种子
    int Precision = pow(10,n) - 1;
   
    return (int)((rand() % Precision / (float)(Precision + 1))*pow(10,n)) % max + min;
}


/*int Random(int l,int r)//生成范围在l~r的随机数 
{	
	srand(time(0));  //设置时间种子
	return rand()%(r-l+1)+l;//生成区间r~l的随机数 
}*/

int main()
{
    memset(visited,0,sizeof(visited));
    cout << "请输入城市数量：";
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            //printf("请输入%d号城市到%d号城市之间的距离:",i,j);
            //cin >> l[i][j];
            
            l[i][j] = Random(5,0,100);
            l[j][i] = l[i][j];
        }
    }
    printf("\n\n");
    for(int a = 1;a < n+1;a++)
    {
    	for(int b= 1;b < n+1;b++)
    	{
    		printf("%d\t",l[a][b]);
		}
		printf("\n");
	}
    
    cout << "请输入出发的城市是第几个城市：";
    cin >> go_city;
    visited[go_city] = 1;
    
    
	LARGE_INTEGER t1,t2,tc;
    QueryPerformanceFrequency(&tc);		//返回每秒嘀哒声的个数 
    QueryPerformanceCounter(&t1);		//返回的嘀哒声的频率 
    
    recursion(go_city);
    
    cout << "最短路程的线路为: ";
    for(int i=1;i<=n;i++)
    {
        cout << min_path[i] << " --> ";
        min_path[i] = min_path[i];
        if(i == n)
        {
        	cout << min_path[1] << endl;
		}
    }
    cout << "最短路程长度为: ";
    cout << min_l << endl;
    
    QueryPerformanceCounter(&t2);
    double time=(double)(t2.QuadPart-t1.QuadPart)/(double)tc.QuadPart; 
    cout<<"time = "<<time<<endl;  //输出时间（单位：）
    
    return 0;
}