欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

js回溯法計算最佳旅行線路代碼實例

 更新時間:2019年09月11日 10:30:43   作者:muamaker  
這篇文章主要介紹了js回溯法計算最佳旅行線路代碼實例,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下

回溯法

假如有 A,B,C,D四個城市,他們之間的距離用 G[V][E] 表示,為 無窮大,則表示兩座城市不相通

現在從計算從某一個城市出發(fā),把所有的城市不重復旅行一次,最短路徑

其中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城市開始,則需要探索 剩下的幾個城市,剩下的幾個城市再往里探索,如果失敗了,就廢棄,回到之前的狀態(tài)

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;     //規(guī)劃過程中記錄的距離
  var bestl = Infinity; //當前最優(yōu)解
  var bestx = [0,0,0,0,0]; //當前最優(yōu)解的路徑
  //var t = 0; //當前需要到達的城市
  var n = x.length-1;
  function Traveling(t){
    if(t > n ){
      //搜索到底部,如果滿足最優(yōu)解則記錄
      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);       //搜索下一下節(jié)點
          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)

以上就是本文的全部內容,希望對大家的學習有所幫助,也希望大家多多支持腳本之家。

相關文章

  • JavaScript?管道運算符及工作原理

    JavaScript?管道運算符及工作原理

    這篇文章主要介紹了JavaScript?管道運算符,管道運算符為我們的代碼添加了大量上下文,并簡化了操作,以便以后可以擴展它們,本文結合示例代碼給大家介紹的非常詳細,需要的朋友可以參考下
    2023-05-05
  • JS判斷空對象的幾個方法大盤點

    JS判斷空對象的幾個方法大盤點

    在做數據交互的時候,我們經常需要判斷數據或者對象是不是為空,避免當接口異常時候前端頁面崩潰,下面這篇文章主要給大家介紹了關于JS判斷空對象的幾個方法,需要的朋友可以參考下
    2022-02-02
  • 解析javascript中鼠標滾輪事件

    解析javascript中鼠標滾輪事件

    這篇文章主要給大家詳細介紹了javascript中鼠標滾輪事件,圖文并茂,十分的詳細,有需要的小伙伴可以參考下。
    2015-05-05
  • JS優(yōu)化冗余代碼的技巧分享

    JS優(yōu)化冗余代碼的技巧分享

    這篇文章主要為大家整理了18個JavaScript優(yōu)化冗余代碼的技巧,文中的示例代碼簡潔易懂,具有一定的借鑒價值,感興趣的小伙伴可以了解一下
    2023-08-08
  • 解析ES6中的解構賦值(數組,對象,嵌套,默認值)

    解析ES6中的解構賦值(數組,對象,嵌套,默認值)

    解構賦值是一種特殊的語法,它使我們可以將數組或對象“拆包”至一系列變量中,因為有時這樣更方便,接下來通過本文給大家介紹ES6中的解構賦值(數組,對象,嵌套,默認值),需要的朋友可以參考下
    2022-11-11
  • 使用javascript做時間倒數讀秒功能的實例

    使用javascript做時間倒數讀秒功能的實例

    今天小編就為大家分享一篇關于使用javascript做時間倒數讀秒功能的實例,小編覺得內容挺不錯的,現在分享給大家,具有很好的參考價值,需要的朋友一起跟隨小編來看看吧
    2019-01-01
  • javascript之水平橫向滾動歌詞同步的應用

    javascript之水平橫向滾動歌詞同步的應用

    javascript之水平橫向滾動歌詞同步的應用...
    2007-05-05
  • javascript實現頁面內關鍵詞高亮顯示代碼

    javascript實現頁面內關鍵詞高亮顯示代碼

    關鍵詞高亮想必大家對它都不陌生吧,應用也比較廣泛的,下面為大家介紹下通過javascript是如何實現頁面內關鍵詞高亮顯示
    2014-04-04
  • JavaScript之ECharts用法講解

    JavaScript之ECharts用法講解

    這篇文章主要介紹了JavaScript之ECharts用法講解,本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下
    2021-08-08
  • js如何判斷不同系統(tǒng)的瀏覽器類型

    js如何判斷不同系統(tǒng)的瀏覽器類型

    正如標題所言使用js如何判斷不同系統(tǒng)的瀏覽器類型,下面有個不錯的示例,感興趣的朋友可以參考下
    2013-10-10

最新評論