js回溯法计算最佳旅行线路代码实例

回溯法

假如有 A,B,C,D四个城市，他们之间的距离用 G[V][E] 表示，为 无穷大，则表示两座城市不相通

现在从计算从某一个城市出发，把所有的城市不重复旅行一次，最短路径

其中G为： （Infinity表示城市不相通）

var g = [
  [Infinity,3    ,Infinity,8    ,9],
  [ 3   ,Infinity,3    ,10   ,5],
  [Infinity, 3   ,Infinity,4    ,3],
  [8    ,10   ,4    ,Infinity,20],
  [9    ,5    ,3    ,20   ,Infinity]
]

分析，如果确定从 A城市开始，则需要探索 剩下的几个城市，剩下的几个城市再往里探索，如果失败了，就废弃，回到之前的状态

var g = [
    [Infinity,3    ,Infinity,8    ,9],
    [ 3   ,Infinity,3    ,10   ,5],
    [Infinity, 3   ,Infinity,4    ,3],
    [8    ,10   ,4    ,Infinity,20],
    [9    ,5    ,3    ,20   ,Infinity]
  ]

  var x = [0,1,2,3,4]; //城市的编号
  var cl = 0;     //规划过程中记录的距离
  var bestl = Infinity; //当前最优解
  var bestx = [0,0,0,0,0]; //当前最优解的路径
  //var t = 0; //当前需要到达的城市
  var n = x.length-1;
  function Traveling(t){
    if(t > n ){
      //搜索到底部，如果满足最优解则记录
      if(g[x[n]][0] < Infinity && (cl + g[x[n]][0] < bestl)){
        for(var j = 0; j <= n; j++){
          bestx[j] = x[j];
        }
        bestl = cl + g[x[n]][0];
      }
    }else{
      for(var j = t ; j <= n; j++){
        if(g[x[t-1]][x[j]] < Infinity && (cl + g[x[t-1]][x[j]] < bestl )){
          swap(x,t,j);        //交换位置，将j点作为 当前需要到达的城市
          cl = cl + g[x[t-1]][x[t]]; //加上选中的点
          Traveling(t+1);       //搜索下一下节点
          cl = cl - g[x[t-1]][x[t]]; //还原搜索之前
          swap(x,t,j);        //还原
        }
      }
    }
  }
  function swap(arr,x,y){
    var temp = arr[x];
    arr[x] = arr[y];
    arr[y] = temp;
  }
  Traveling(1);
  console.log(bestx);
  console.log(bestl)

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • 编写高质量的js之正确理解正则表达式回溯

    当一个正则表达式扫描目标字符串时,从左到右逐个扫描正则表达式的组成部分,在每个位置上测试能不能找到一个匹配.对于每一个量词和分支,都必须确定如何继续进行.如果是一个量词(如*.+?或者{2,}),那么正则表达式必须确定何时尝试匹配更多的字符:如果遇到分支(通过|操作符),那么正则表达式必须从这些选项中选择一个进行尝试. 当正则表达式做出这样的决定时,如果有必要,它会记住另一个选项,以备返回后使用.如果所选方案匹配成功,正则表达式将继续扫描正则表达式模板,如果其余部分匹配也成功了,那么匹配就结束了

  • JS trim去空格的最佳实践

    JS trim去空格的最佳实践

    刚好上次有同学提出疑问.刚好可以自测一下.先来看看老道在<JavaScript 精粹>P33 写的吧.他对 String 对象扩展了一个 trim() 方法: 复制代码 代码如下: Function.prototype.method = function(name, func) { this.prototype[name] = func; return this; }; String.method('trim', function() { return this.replace(/^\s+|\

  • 通过百度地图获取公交线路的站点坐标的js代码

    最近做百度地图的模拟数据,需要获取某条公交线路沿途站点的坐标信息,貌似百度没有现成的API,因此做了一个模拟页面,工具而已,IE6/7/8不支持 复制代码 代码如下: <!DOCTYPE html> <html> <head> <meta charset="utf-8" /> <title>获取公交站点坐标</title> <style type="text/css"> html,b

  • 正则中的回溯定义与用法分析【JS与java实现】

    本文实例分析了正则中的回溯定义与用法.分享给大家供大家参考,具体如下: 关于"回溯"我也是第一次接触,对它也不算很了解.下面就把我所了解的做为一个心德记录下来,以备查看. 我们所使用的正则表达式的匹配基础大概分为:优先选择最左端(最靠开头)的匹配结果和标准的匹配量词(*.+.?和{m, n})是匹配优先的. "优先选择最左端的匹配"顾名思义就是从字符串的起始位置开始匹配直到匹配结束这是基础:"标准匹配量词"又分为"非确定型有穷自动机(N

  • Javascript模块化编程(一)模块的写法最佳实践

    Javascript模块化编程(一)模块的写法最佳实践

    随着网站逐渐变成"互联网应用程序",嵌入网页的Javascript代码越来越庞大,越来越复杂.  网页越来越像桌面程序,需要一个团队分工协作.进度管理.单元测试等等......开发者不得不使用软件工程的方法,管理网页的业务逻辑. Javascript模块化编程,已经成为一个迫切的需求.理想情况下,开发者只需要实现核心的业务逻辑,其他都可以加载别人已经写好的模块. 但是,Javascript不是一种模块化编程语言,它不支持"类"(class),更遑论"模块&

  • 5个最佳的Javascript日期处理类库分享

    5个最佳的Javascript日期处理类库分享

    在大家日常网站开发和web应用开发中,我们往往需要有效的调用Javascript处理日期和时间格式相关的函数,在Javascript中已经包含了部分最基本的内建处理方法.当然如果大家有时间的话,完全可以自己开发和编写需要的方法,但是有效的使用别人已经开发好的类库肯定是一个更好的处理方式,没有必要什么都原创吧,君子善假于物也.今天这里我们收集了5个最佳的日期处理函数类库,希望对于大家有帮助,如果你喜欢我们的文章,请大家给我们留言,谢谢! 1. XDate 这个类库是javascript本地日期对象

  • 最佳的JavaScript错误处理实践

    最佳的JavaScript错误处理实践

    不管你的技术水平如何,错误或异常是应用程序开发者生活的一部分.Web开发的不连贯性留下了许多错误能够发生并确实已经发生的地方.解决的关键在于处理任何不可预见的(或可预见的错误),来控制用户的体验.利用JavaScript,就有多种技术和语言特色可以用来正确地解决任何问题. 在 JavaScript 中处理错误很危险.如果你相信墨菲定律,会出错的终究会出错!在这篇文章中,我会深入研究 JavaScript 中的错误处理.我会涉及到一些陷阱和好的实践.最后我们会讨论异步代码处理和 Ajax. 我认为

  • javascript递归回溯法解八皇后问题

    下面给大家分享的是回溯法解八皇后, 带详细注解,这里就不多废话了. function NQueens(order) { if (order < 4) { console.log('N Queens problem apply for order bigger than 3 ! '); return; } var nQueens = []; var backTracking = false; rowLoop: for (var row=0; row<order; row++) { //若出现ro

  • js回溯法计算最佳旅行线路代码实例

    js回溯法计算最佳旅行线路代码实例

    回溯法 假如有 A,B,C,D四个城市,他们之间的距离用 G[V][E] 表示,为 无穷大,则表示两座城市不相通 现在从计算从某一个城市出发,把所有的城市不重复旅行一次,最短路径 其中G为: (Infinity表示城市不相通) var g = [ [Infinity,3 ,Infinity,8 ,9], [ 3 ,Infinity,3 ,10 ,5], [Infinity, 3 ,Infinity,4 ,3], [8 ,10 ,4 ,Infinity,20], [9 ,5 ,3 ,20 ,Inf

  • 基于c++计算矩形重叠面积代码实例

    在图像处理中,经常需要计算两个矩形的重叠面积,在 python 中,可以使用 shapely 包中的 Polygon 函数,但是到了 c++ 没有想象中的那么简单. 查阅了很多资料,基本上都是判断两个矩形是否包含来计算,但是两个矩形的相交情况太多了,每个方法我都担心考虑不全,所以想了一个在画布上画出矩形框,然后通过计算白点数或者轮廓的方法来计算面积. 但是就算用了这个方法,求取真正的重叠面积还差一个像素点,是否要加数值为1这个偏移量需要根据矩形的重叠情况来确定,这里不写的那么精细,不考虑1个像素

  • 基于JS实现计算24点算法代码实例解析

    前言 休息的时候无意间看到群里有人发出了华为的校招题,一开始看题目的时候觉得很简单,于是晚上就试着写了一下,结果写的过程中打脸,不断的整理逻辑不断的重写,但我的性格又是不做出来晚上睡不好的那种,于是在做出来的时候就分享给大家(快凌晨三点了有木有,这校招题难度都达到这级别了?o(╥﹏╥)o) 题目描述 审题要注意:1+2+3*4是前面三个已经相加为6再乘4,没有括号!! 代码: <!DOCTYPE html> <html lang="en"> <head&g

  • js贪心算法 钱币找零问题代码实例

    js贪心算法 钱币找零问题代码实例

    给定一组硬币的面额,以及要找零的钱数,计算出符合找零钱数的最少硬币数量. 例如,美国硬币面额有1.5.10.25这四种面额,如果要找36美分的零钱,则得出的最少硬币数应该是1个25美分.1个10美分和1个10美分共三个硬币.这个算法要解决的就是诸如此类的问题.我们来看看如何用动态规划的方式来解决. 对于每一种面额,我们都分别计算所需要的硬币数量.具体算法如下: 如果全部用1美分的硬币,一共需要36个硬币 如果用5美分的硬币,则需要7个5美分的硬币 + 1个1美分的硬币 = 8个硬币 如果用10美

  • 原生js实现获取form表单数据代码实例

    本文实例为大家分享了原生js实现获取form表单数据的具体代码,供大家参考,具体内容如下 //获取指定form中的所有的<input>对象 function getElements(formId) { var form = document.getElementById(formId); var elements = new Array(); var tagElements = form.getElementsByTagName('input'); for (var j = 0; j <

  • js获取 gif 的帧数的代码实例

    使用 javascript 获取 GIF 图的帧数,如果帧数过大,则不让传到服务器 这里是使用一个插件: github地址为: https://github.com/buzzfeed/libgif-js <!DOCTYPE html> <html> <head> <meta charset="utf-8"> <title></title> <meta name="viewport" con

  • Python基于回溯法子集树模板解决找零问题示例

    Python基于回溯法子集树模板解决找零问题示例

    本文实例讲述了Python基于回溯法子集树模板解决找零问题.分享给大家供大家参考,具体如下: 问题 有面额10元.5元.2元.1元的硬币,数量分别为3个.5个.7个.12个.现在需要给顾客找零16元,要求硬币的个数最少,应该如何找零?或者指出该问题无解. 分析 元素--状态空间分析大法:四种面额的硬币看作4个元素,对应的数目看作各自的状态空间,遍历状态空间,其它的事情交给剪枝函数. 解的长度固定:4 解的编码:(x1,x2,x3,x4) 其中x1∈[0,1,2,3], x2∈[0,1,2,3,4

  • Python基于回溯法子集树模板实现图的遍历功能示例

    Python基于回溯法子集树模板实现图的遍历功能示例

    本文实例讲述了Python基于回溯法子集树模板实现图的遍历功能.分享给大家供大家参考,具体如下: 问题 一个图: A --> B A --> C B --> C B --> D B --> E C --> A C --> D D --> C E --> F F --> C F --> D 从图中的一个节点E出发,不重复地经过所有其它节点后,回到出发节点E,称为一条路径.请找出所有可能的路径. 分析 将这个图可视化如下: 本问题涉及到图,那首

  • Python基于回溯法子集树模板解决m着色问题示例

    Python基于回溯法子集树模板解决m着色问题示例

    本文实例讲述了Python基于回溯法子集树模板解决m着色问题.分享给大家供大家参考,具体如下: 问题 图的m-着色判定问题 给定无向连通图G和m种不同的颜色.用这些颜色为图G的各顶点着色,每个顶点着一种颜色,是否有一种着色法使G中任意相邻的2个顶点着不同颜色? 图的m-着色优化问题 若一个图最少需要m种颜色才能使图中任意相邻的2个顶点着不同颜色,则称这个数m为该图的色数.求一个图的最小色数m的问题称为m-着色优化问题. 分析 解的长度是固定的,n.若x为本问题的一个解,则x[i]表示第i个节点的

  • Python基于回溯法子集树模板解决马踏棋盘问题示例

    Python基于回溯法子集树模板解决马踏棋盘问题示例

    本文实例讲述了Python基于回溯法子集树模板解决马踏棋盘问题.分享给大家供大家参考,具体如下: 问题 将马放到国际象棋的8*8棋盘board上的某个方格中,马按走棋规则进行移动,走遍棋盘上的64个方格,要求每个方格进入且只进入一次,找出一种可行的方案. 分析 说明:这个图是5*5的棋盘. 类似于迷宫问题,只不过此问题的解长度固定为64 每到一格,就有[(-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1)]顺时针8个方向可以选择. 走到一

随机推荐