旅行商问题 python 不同算法实现

这篇具有很好参考价值的文章主要介绍了旅行商问题 python 不同算法实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

货郎问题/旅行商问题(TSP)

一个网络上的最优路线问题,它寻求货郎走过网络上的所有点的路线最短。

定义:

  • 输入 : 有穷个城市的集合 C = { c 1 , c 2 , . . . , c n } , 距 离 d ( c i , c j ) = d ( c j , c i ) ∈ Z + , 1 ≤ i < j ≤ n C=\{c_1,c_2,...,c_n\},距离d(c_i,c_j)=d(c_j,c_i)\in Z^+,1 \le i< j \le n C={c1,c2,...,cn},d(ci,cj)=d(cj,ci)Z+,1i<jn
  • 1 , 2 , . . . , n 1,2,...,n 1,2,...,n 的排列 k 1 , k 2 , . . . , k n k_1,k_2,...,k_n k1,k2,...,kn 使得: m i n { ∑ i = 1 n − 1 d ( c k i , c k i + 1 ) + d ( c k n , c k 1 ) } min\{ \sum\limits _{i=1} ^{n-1} d(c_{k_i},c_{k_{i+1}})+d(c_{k_n,c_{k_1}})\} min{i=1n1d(cki,cki+1)+d(ckn,ck1)}

问题描述:

​ 旅行商问题(Travelling Salesman Problem,TSP)又称为旅行推销员问题、货郎担问题,它是数学领域著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是使求得的路径长度为所有路径长度为所有路径之中的最小值。

旅行商问题,即TSP问题,是数学领域中著名问题之一。

给定 n n n个城市,每个城市之间存在一定的距离,具体而言,第 i i i号城市到第 j j j号城市的距离为 a i j a_{ij} aij

python旅行商问题动态规划,算法,python,算法,python,深度优先

1.采用蛮力法求TSP问题

1.1 蛮力法

一种简单直接地解决问题的方法,常常直接基于问题的描述,所以蛮力法也是最容易应用的方法。蛮力法所依赖的基本技术是遍历,也称扫描,即采用一定的策略依次理待求解问题的所有元素,从而找出问题的解。依次处理所有元素是蛮力法的关键,为了避免陷人重复试探,应保证处理过的元素不再被处理。

本题算法:求全排列算法

1.2代码实现

def dfs(position):
    global count, temp_dist, min_cost, min_index
    # 递归出口
    if position == len(arr):
        if temp[0] == start:
            count += 1
            temp.append(start)
            for i in range(3):
                temp_dist += distance[temp[i]][temp[i + 1]]
            temp_dist = temp_dist + distance[temp[3]][start]
            print(f"方案{count}为:", temp, f"路程为:{temp_dist}")
            if min_cost > temp_dist:
                min_cost = temp_dist
                min_index = count
            temp_dist = 0
            temp.pop()
        return
    # 递归主体
    for index in range(0, len(arr)):
        if not visit[index]:
            temp[position] = arr[index]
            visit[index] = True  # 试探
            dfs(position + 1)
            visit[index] = False  # 回溯。


if __name__ == "__main__":
    visit = [False, False, False, False]
    temp = ["" for x in range(0, 4)]
    count = 0 # 方案数
    temp_dist = 0 #临时路程
    min_cost = float("inf")
    min_index = None
    distance = [
        [0, 8, 5, 36],
        [6, 0, 8, 5],
        [8, 9, 0, 5],
        [7, 7, 8, 0]]  # 存储两个城市之间的距离
    arr = [0, 1, 2, 3]
    start = int(input("请输入开始结点:"))
    dfs(0)
    print(f"最佳方案为:{min_index},最优路程为:{min_cost}")

1.3 运行结果

python旅行商问题动态规划,算法,python,算法,python,深度优先

1.4复杂度分析

当使用蛮力法解决TSP问题时,需要考虑从某个城市出发的所有路线。由于城市之间彼此互通,城市拓扑是个完全图,因此所有路线的数量规模是 n − 1 n-1 n1 个城市的全排列。求1~n-1全排列的时间为 O ( n ∗ n ! ) O(n*n!) O(nn!), 对于 O ( n ! ) O(n!) O(n!) 的路径,求每条路径的长度的时间为 O ( n ) O(n) O(n), 所以该算法的复杂度为 O ( n ∗ n ! ) O(n*n!) O(nn!)

2.采用动态规划求解TSP问题

3、 采用回溯法求解TSP问题

代码实现

4、 采用分枝限界法求解TSP问题

算法设计

解向量为 < 1 , i 1 , i 2 , . . . , i n − 1 > <1,i_1,i_2,...,i_{n-1}> <1,i1,i2,...,in1>, 其中 i 1 , i 2 , . . . , i n − 1 i_1,i_2,...,i_{n-1} i1,i2,...,in1 { 2 , 3 , . . . , n } \{2,3,...,n\} {2,3,...,n} 的排列。

搜索空间为排列树, 结点 < 1 , i 1 , i 2 , . . . , i k > <1,i_1,i_2,...,i_{k}> <1,i1,i2,...,ik> 表示得到 k k k 步路线。

约束条件: 令 B = { i 1 , i 2 , . . . , i k } B=\{i_1,i_2,...,i_{k}\} B={i1,i2,...,ik}, 则 i k + 1 ∈ { 2 , . . . , n } − B i_{k+1} \in \{2,...,n\}-B ik+1{2,...,n}B 即每个结点只能访问一次。

代价函数与界

界:当前得到的最短巡回路线长度

代价函数: 设顶点 c i c_i ci 出发的最短边长度为 l i l_i li d j d_j dj 为选定巡回路线中第 j j j 段的长度
L = ∑ j = 1 k d j + l i k + ∑ i j ∉ B l i j L=\sum \limits _{j=1} ^k d_j +l_{i_k} + \sum \limits _{i_j \notin B} l_{i_j} L=j=1kdj+lik+ij/Blij
其中 : 为已走过路径长 ; 为剩余长度下界;

python旅行商问题动态规划,算法,python,算法,python,深度优先

搜索树

python旅行商问题动态规划,算法,python,算法,python,深度优先

过程分析

  • 第一个界: < 1, 2, 3, 4 >,长度为 29
  • 第二个界: < 1, 2, 4, 3 >,长度为 23
  • 结点 < 1, 3, 2 >: 代价函数值 26 > 23,不再搜索,返回 < 1, 3 >
  • 结点 < 1, 3, 4 >, 代价函数值 9 + 7 + 2 + 2 = 20,继续,得到可行解 < 1, 3, 4, 2 > , 长度 23.
  • 回溯到结点 < 1 >,沿着 < 1, 4 >向下…

最优解为 < 1, 2, 4, 3 > 或 < 1, 3, 4, 2 >,长度 23.

约束条件:只能选没有走过的结点代价函数:走过长度+后续长度的下界

时间复杂度:O(n!)

代码:

#include<iostream>  
using namespace std;
#define MAX 1000  
int g[100][100], x[100], bestx[100];
 
int cl = 0, bestl = MAX, n;
 
//界定函数,按照屈婉玲老师的算法公开课视频讲解的给出的实现,这与网上绝大多数版本的界定函数不同,可以更精确的削减分支
double Bound(int t, int cl)
{
	double min1 = 0, min2 = 0, tempSum=0;
	for (int j = t; j <= n; j++)
	{
		if (g[x[t - 1]][x[j]] != -1 && g[x[t - 1]][x[j]] < min1)
		{
			min1 = g[x[t - 1]][x[j]];
		}
		for (int i = 1; i <= n; ++i)
		{
			if (g[x[j]][x[i]] != -1 && g[x[j]][x[i]] < min2)
			{
				min2 = g[x[j]][x[i]];
			}
		}
		tempSum += min2;
	}
 
	return cl + min1 + tempSum;
 
}
 
 
void Traveling(int t)
{
	int j;
	if (t>n) //到达叶子结点  
	{
		
		if (g[x[n]][1] != -1 && (cl + g[x[n]][1]<bestl))//推销员到的最后一个城市与出发的城市之间有路径,且当前总距离比当前最优值小  
		{
			for (j = 1; j <= n; j++)
				bestx[j] = x[j];
			bestl = cl + g[x[n]][1];
		}
	}
	else    //没有到达叶子结点  
	{
		for (j = t; j <= n; j++)//搜索扩展结点的左右分支,即所有与当前所在城市临近的城市  
		{
			if (g[x[t - 1]][x[j]] != -1 && Bound(t, cl)<bestl)
			//if (g[x[t - 1]][x[j]] != -1 && (cl + g[x[t - 1]][x[j]]<bestl))//若果第t-1个城市与第t个城市之间有路径且可以得到更短的路线  
			{
 
				swap(x[t], x[j]);     //保存要去的第t个城市到x[t]中  
				cl += g[x[t - 1]][x[t]]; //路线长度增加  
				Traveling(t + 1);      //搜索下一个城市  
				cl -= g[x[t - 1]][x[t]];
				swap(x[t], x[j]);
			}
		}
	}
}
int main()
{
	int i, j;
	cout << "请输入一共有几个城市:" << endl;
	cin >> n;
	cout << "请输入城市之间的距离" << endl;
 
	for (i = 1; i <= n; i++)
		for (j = 1; j <= n; j++)
			cin >> g[i][j];
 
	for (i = 1; i <= n; i++)
	{
		x[i] = i;
		bestx[i] = 0;
	}
 
	Traveling(2);
	cout << "城市路线:" << endl;
	for (i = 1; i <= n; i++)
		cout << bestx[i] << ' ';
	cout << bestx[1];
	cout << endl;
	cout << "最短路线长度:" << endl;
	cout << bestl << endl;
	return 0;
}

5.采用贪心法求解TSP问题

5.1 分析

实际上TSP问题不满足贪心法的最优子结构性质,所以采用贪心法不一定得到最优解,但可以采用合理的贪心策略,如可以采用最近邻点策略,即从任意城市出发,每次在没有到过的城市中选择最近的一个,直到经过了所有的城市,最后回到出发城市。

5.2 代码实现

5.2 代码实现

5.3 时间复杂度

O ( n 2 ) O(n^2) O(n2)文章来源地址https://www.toymoban.com/news/detail-740745.html

6.时间复杂度分析

  • 搜索树的树叶个数: O ( ( n − 1 ) ! ) O((n-1)!) O((n1)!) ,每片树叶对应 1 条路径,每条路径有 n 个结点.
  • 每个结点代价函数计算时间 O ( 1 ) O(1) O(1),每条路径的计算时间为 O ( n ) O(n) O(n)
  • 最坏情况下算法的时间 O ( n ! ) O(n!) O(n!) (蛮力算法)

到了这里,关于旅行商问题 python 不同算法实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 旅行商问题(枚举,回溯,动态规划,贪心,分支界限)

    假设有一个货郎担要拜访n个城市,他必须选择所要走的路程,路程的限制时每个城市只能拜访一次,而且最后要走到原来出发的城市,要求路径长度。 旅行商问题将要走过的城市建立成一个完全图。稠密图,所以用临接矩阵来存。 由于路径的特殊性,可以正走也可以反着走

    2024年02月04日
    浏览(38)
  • C++动态规划解决TSP(旅行商)问题

    题目描述: 某旅行商希望从某城市出发经过一系列的城市最后再回到出发的城市。这些城市之间均可直航,他希望只经过这些城市一次且旅行的总线路最短。设有n个城市,城市的编号从1到n。 输入第一行为整数n,表示城市的数量。其后n行,每行有n个整数,用空格隔开,表

    2024年02月03日
    浏览(37)
  • [动态规划,二进制状态压缩] 旅行商问题

    题目描述 一个国家有 n 个城市,每两个城市之间都开设有航班,从城市 i 到城市 j 的航班价格为 cost[i, j] ,而且往、返航班的价格相同。 售货商要从一个城市出发,途径每个城市 1 次(且每个城市只能经过 1 次),最终返回出发地,而且他的交通工具只有航班,请求出他旅

    2024年01月24日
    浏览(41)
  • 整数规划——分支界定算法(旅行商问题,规约矩阵求解)

    一、普通优化问题分枝定界求解 题目的原问题为   在计算过程中,利用MATLAB中的linprog()函数进行求解最优解,具体的计算步骤如下: A为约束系数矩阵,B为等式右边向量,C为目标函数的系数向量。   进行第一次最优求解以A=[2 9;11 -8],B=[40;82],C=[-3,-13]利用linprog函数求解。解

    2024年02月16日
    浏览(37)
  • 量子退火算法入门(5):旅行商问题的QUBO建模「下篇之Python实现」

    提示:上篇已经讲过了旅行商问题的QUBO建模,这里直接讲两种编程实现: 看过上篇的读者应该已经注意到,因为旅行商问题需要最终返回到初始点的。所以,下面👇的目标函数里,循环进行到 N N N 时,最后一个 x j , t + 1 x_{j,t+1} x j , t + 1 ​ 应该确定回到初始点的。 针对这

    2023年04月14日
    浏览(34)
  • 算法 |【实验5.2】1-深度优先搜索暴力求解旅行商问题

    商品推销员要去n个城市推销商品,城市从1至n编号,任意两个城市间有一定距离,该推销员从城市1出发,需要经过所有城市并回到城市1,求最短总路径长度。 把旅行商问题看作一种排列问题,不难想出,这道题的蛮力做法即穷举所有路线。选定起点有n种选法,选定起点后的

    2023年04月08日
    浏览(69)
  • 【算法每日一练]-动态规划(保姆级教程 篇13)POJ2686马车旅行 #POJ3254 玉米田 #POJ1185:炮兵阵地

    目录 今天知识点 dp每个票的使用情况,然后更新此票状态下的最优解,dp到没有票就行了 把状态压缩成j,dp每行i的种植状态,从i-1行进行不断转移 把状态压缩成j,dp每行i的布置状态,从i-1和i-2行进行不断转移 POJ2686马车旅行 思路: POJ3254 玉米田 思路: POJ1185:炮兵阵地 思路:

    2024年02月04日
    浏览(51)
  • 【Python算法】实验8-动态规划与背包问题

    目录 实验内容 1.数塔dp -A 2.骨牌铺方格 3.一只小蜜蜂

    2023年04月19日
    浏览(66)
  • 【Python算法】实验12-动态规划与背包问题

    目录 实验内容 1.数塔dp -A 2.骨牌铺方格 3.一只小蜜蜂

    2024年02月15日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包