回溯法--旅行售货员问题--排列树

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

回溯法有点类似于暴力枚举的搜索过程,回溯法的基本思想是按照深度优先搜索的策略,从根节点出发深度搜索解空间树,当搜索到某一节点时,如果该节点可能包含问题的解,则继续向下搜索;反之回溯到其祖先节点,尝试其他路径搜索。

第一类问题:只要求求得一个可行解,那么搜索到问题的一个解即可结束;

第二类问题:求最优解,那么需要搜索整个解空间树,得到所有解之后择最优作为问题的解。

回溯法与暴力搜索的区别:在搜索到叶子节点之前已经能确定该路径不为最优解时就可以进行剪枝,节省搜索时间。

回溯法有两种模板:子集树和排列树。旅行售货员问题时典型的排列树。

子集树: 所给的问题是从n个元素的集合中找出满足某种性质的子集时, 相应的解空间称为子集树.
  子集树通常有个叶结点, 遍历子集树的任何算法均需Ω()的计算时间.

  例如: 0-1背包问题的解空间为一棵子集树.

排列树: 当所给的问题是确定n个元素满足某种性质的排列时, 相应的解空间称为排列树.
  排列树通常有(n-1)!个叶结点, 遍历排列树需要Ω(n!)的计算时间.

  例如: 旅行售货员问题的解空间为一棵排列树.

问题描述

排列空间树问题,算法笔记,算法,回溯法

 某售货员要到若干城市去推销商品,已知各城市之间的路程,他要选定一条从驻地出发,经过每个城市一遍,最后回到住地的路线,使总的路程最短。

 排列空间树问题,算法笔记,算法,回溯法

 由于只有4个城市,如果规定售货员总是从城市1出发,那么依据排列组合可以得到6种不同的旅行方案,比如12341、13241等等。在这些排列组合基础上可以很容易绘制出一棵排列树,也是该问题的解空间树,排列树如下:

排列空间树问题,算法笔记,算法,回溯法

 我们可以得到如下信息:

根据解空间树可以得到一些有用的信息:

  • 该树的深度为5
  • 两个节点之间路径上的标识数组代表所走城市
  • 树上没有体现出回到城市1的路径,但实际上计算要考虑这段路程

问题分析

排列空间树问题,算法笔记,算法,回溯法

 

假设起点为 1。

算法开始时 x = [1, 2, 3, …, n]

x[1 : n]有两重含义 x[1 : i]代表前 i 步按顺序走过的城市, x[i + 1 : n]代表还未经过的城市。利用Swap函数进行交换位置。

i = n 时,处在排列树的叶节点的父节点上,此时算法检查图G是否存在一条从顶点x[n-1] 到顶点x[n] 有一条边,和从顶点x[n] 到顶点x[1] 也有一条边。若这两条边都存在,则发现了一个旅行售货员的回路(即:新旅行路线),算法判断这条回路的费用是否优于已经找到的当前最优回路的费用bestcost,若是,则更新当前最优值bestcost和当前最优解bestx。

i < n 时,检查x[i - 1]至x[i]之间是否存在一条边, 若存在,则x [1 : i ] 构成了图G的一条路径,若路径x[1: i] 的耗费小于当前最优解的耗费,则算法进入排列树下一层,否则剪掉相应的子树。

伪代码

定义变量:图的基本信息(邻接矩阵、顶点数、边数),当前解,最优解,标记有边无边(方便初始化和判断)

排列空间树问题,算法笔记,算法,回溯法

 回溯主函数

排列空间树问题,算法笔记,算法,回溯法

 

代码

//旅行商问题--排列树
#include<iostream>
#include<cstring>
using namespace std;
#define maxn 0x3f3f3f
const int NoEdge = -1;      //两个点之间没有边
int citynum;                //城市数
int edgenum;                //边数
int currentcost;            //记录当前的路程
int bestcost;               //记录最小的路程(最优)
int Graph[100][100];        //图的边距记录
int x[100];                 //记录行走顺序
int bestx[100];             //记录最优行走顺序

void InPut(){
    int pos1, pos2, len;     //点1 点2 距离

    cout<<"请输入城市数和边数(c e):";
    cin>>citynum>>edgenum;

    memset(Graph, NoEdge, sizeof(Graph));

    cout<<"请输入两座城市之间的距离(p1 p2 l):"<<endl;
    for(int i = 1; i <= edgenum; ++i)
    {
        cin>>pos1>>pos2>>len;
        Graph[pos1][pos2] = Graph[pos2][pos1] = len;
    }
}

//初始化
void Initilize(){
    currentcost = 0;
    bestcost = maxn;
    //初始化行走顺序,第i步走的城市
    for(int i = 1; i <= citynum; i++) x[i] = i;
}


void Swap(int &a, int &b){
    int temp;
    temp = a;
    a = b;
    b = temp;
}


void BackTrack(int i) //这里的i代表第i步去的城市而不是代号为i的城市
{
    if(i == citynum)
    {
        //进行一系列判断,注意的是进入此步骤的层数应是叶子节点的父节点,而不是叶子节点
        if(Graph[x[i - 1]][x[i]] != NoEdge && Graph[x[i]][x[1]] != NoEdge && (currentcost + Graph[x[i - 1]][x[i]] + Graph[x[i]][x[1]] < bestcost || bestcost == maxn))
        {
            //最小(优)距离=当前的距离+当前城市到叶子城市的距离+叶子城市到初始城市的距离
            bestcost = currentcost + Graph[x[i - 1]][x[i]] + Graph[x[i]][x[1]];
            for(int j = 1; j <= citynum; ++j)
                bestx[j] = x[j];
        }
    }
    else
    {
        for(int j =  i; j <= citynum; ++j)
        {
            if(Graph[x[i - 1]][x[j]] != NoEdge && (currentcost + Graph[x[i - 1]][x[j]] < bestcost || bestcost == maxn))
            {
                Swap(x[i], x[j]);  //这里i 和 j的位置交换了, 所以下面的是currentcost += Graph[x[i - 1]][x[i]];
                currentcost += Graph[x[i - 1]][x[i]];
                BackTrack(i + 1);   //递归进入下一个城市
                currentcost -= Graph[x[i - 1]][x[i]];
                Swap(x[i], x[j]);
            }
        }
    }
}

void OutPut()
{
    cout<<"最短路程为:"<<bestcost<<endl;
    cout << "路线为:" << endl;
    for(int i = 1; i <= citynum; ++i)
        cout << bestx[i] << " ";
    cout << "1" << endl;
}


int main()
{
    InPut();
    Initilize();
    BackTrack(2);
    OutPut();
}
/*假设起点为 1。
算法开始时 x = [1, 2, 3, …, n]
x[1 : n]有两重含义 x[1 : i]代表前 i 步按顺序走过的城市, 
x[i + 1 : n]代表还未经过的城市。利用Swap函数进行交换位置。
i = n 时,处在排列树的叶节点的父节点上,
此时算法检查图G是否存在一条从顶点x[n-1] 到顶点x[n] 有一条边,
和从顶点x[n] 到顶点x[1] 也有一条边。若这两条边都存在,
则发现了一个旅行售货员的回路(即:新旅行路线),
算法判断这条回路的费用是否优于已经找到的当前最优回路的费用bestcost,
若是,则更新当前最优值bestcost和当前最优解bestx。
i < n 时,检查x[i - 1]至x[i]之间是否存在一条边, 
若存在,则x [1 : i ] 构成了图G的一条路径
若路径x[1: i] 的耗费小于当前最优解的耗费,
则算法进入排列树下一层,否则剪掉相应的子树。*/

以前面的样例示范

排列空间树问题,算法笔记,算法,回溯法

输入

请输入城市数和边数(c e):4 6
请输入两座城市之间的距离(p1 p2 l):
1 2 30
1 3 6
1 4 4
2 4 10
2 3 5
3 4 20

输出
最短路程为:25
路线为:
1 3 2 4 1文章来源地址https://www.toymoban.com/news/detail-754974.html

到了这里,关于回溯法--旅行售货员问题--排列树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • (3)回溯算法团灭子集、组合、排列问题 -- 元素无重可复选

    回溯算法团灭子集、组合、排列问题 根据元素是否重复和是否可复选,分为以下三种变体: 1、元素无重不可复选 2、元素有重不可复选 3、元素无重可复选 该篇给出第三种情况的代码,另外两种的实现见上方变体链接。

    2024年02月09日
    浏览(31)
  • 【C/C++练习】经典的排列组合问题(回溯算法)——电话号码的字母组合

    📖题目描述 题目出处 :电话号码的字母组合 示例: 📖题解  这是一道典型的排列组合问题,根据输入,我们需要找到所有的组合。下面以输入字符串 digits = \\\"23\\\" 为例来讲解这道题目。 图解: 分析:  首先要知道输入的字符串 \\\"23\\\" 中的数字字符分别对应哪些字符串,其中

    2024年02月16日
    浏览(40)
  • 旅行商问题(枚举,回溯,动态规划,贪心,分支界限)

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

    2024年02月04日
    浏览(45)
  • 回溯算法篇-01:全排列

    这道题属于上一篇——“回溯算法解题框架与思路”中的 “元素不重复不可复用” 那一类中的 排列类问题。 我们来回顾一下当时是怎么说的: 排列和组合的区别在于,排列对“顺序”有要求。比如 [1,2] 和 [2,1] 是两个不同的结果。 这就导致了同一个元素 在同一条路径中不

    2024年01月20日
    浏览(31)
  • 力扣--深度优先算法/回溯算法47.全排列 Ⅱ

    思路分析: 使用DFS算法进行全排列,递归地尝试每个可能的排列方式。 使用 path 向量保存当前正在生成的排列,当其大小达到输入数组的大小时,将其加入结果集。 使用 numvisited 向量标记每个数字是否已经被访问过,以确保每个数字在一个排列中只使用一次。 在递归过程中

    2024年03月13日
    浏览(51)
  • leetcode--回溯算法.全排列(java)

    leetcode 46 原题链接-- 全排列 题目描述: 给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 示例1: 输入:nums = [1,2,3] 输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 示例2: 输入:nums = [0,1] 输出:[[0,1],[1,0]] 示例3: 输入:nums = [1

    2024年02月08日
    浏览(35)
  • leetcode46. 全排列(回溯算法-java)

    来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/permutations 给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 示例 1: 输入:nums = [1,2,3] 输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 示例 2: 输入:nums = [0,1] 输出:[[0,1],[1,0]]

    2024年02月11日
    浏览(41)
  • DFS:深搜+回溯+剪枝解决排列、子集问题

                                        创作不易,感谢三连支持!!  . - 力扣(LeetCode) . - 力扣(LeetCode)  方案1:不合法就continue 方案2:合法才能进循环 . - 力扣(LeetCode) . - 力扣(LeetCode)  策略1:决策树以选不选作为参考,结果为叶子节点 策略2:决策树以选几个

    2024年04月16日
    浏览(65)
  • 代码随想录 - Day34 - 回溯:递增子序列+排列问题

    如果有相等的整数也算递增序列 递增子序列中 至少有两个元素 (遍历的时候不用遍历 nums 中最后一个元素) 题目说了数值范围,所以还可以用哈希表去重,速度比 set() 快很多。 但是,个人觉得没必要,因为放在实际情况中一般不会给数值范围。 全排列,即 [1,2] 和 [2,1] 算作

    2024年02月09日
    浏览(76)
  • 【数据结构】回溯算法公式化解题 leetcode经典题目带刷:全排列、组合、子集

    一、什么是回溯算法 回溯算法(Backtracking Algorithm)是一种解决 组合问题 、 排列问题 、 选择问题 等一类问题的常用算法。它通过尝试所有可能的选择来找到问题的解,当发现当前选择不符合要求时,就回溯到之前的状态,然后尝试其他的选择。 1、基本思想: 从问题的起

    2024年02月11日
    浏览(45)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包