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

js回溯法計(jì)算最佳旅行線路代碼實(shí)例

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

回溯法

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

現(xiàn)在從計(jì)算從某一個(gè)城市出發(fā),把所有的城市不重復(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城市開始,則需要探索 剩下的幾個(gè)城市,剩下的幾個(gè)城市再往里探索,如果失敗了,就廢棄,回到之前的狀態(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]; //城市的編號(hào)
  var cl = 0;     //規(guī)劃過程中記錄的距離
  var bestl = Infinity; //當(dāng)前最優(yōu)解
  var bestx = [0,0,0,0,0]; //當(dāng)前最優(yōu)解的路徑
  //var t = 0; //當(dāng)前需要到達(dá)的城市
  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點(diǎn)作為 當(dāng)前需要到達(dá)的城市
          cl = cl + g[x[t-1]][x[t]]; //加上選中的點(diǎn)
          Traveling(t+1);       //搜索下一下節(jié)點(diǎn)
          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)

以上就是本文的全部?jī)?nèi)容,希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。

相關(guān)文章

  • JavaScript?管道運(yùn)算符及工作原理

    JavaScript?管道運(yùn)算符及工作原理

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

    JS判斷空對(duì)象的幾個(gè)方法大盤點(diǎn)

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

    解析javascript中鼠標(biāo)滾輪事件

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

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

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

    解析ES6中的解構(gòu)賦值(數(shù)組,對(duì)象,嵌套,默認(rèn)值)

    解構(gòu)賦值是一種特殊的語法,它使我們可以將數(shù)組或?qū)ο蟆安鸢敝烈幌盗凶兞恐校驗(yàn)橛袝r(shí)這樣更方便,接下來通過本文給大家介紹ES6中的解構(gòu)賦值(數(shù)組,對(duì)象,嵌套,默認(rèn)值),需要的朋友可以參考下
    2022-11-11
  • 使用javascript做時(shí)間倒數(shù)讀秒功能的實(shí)例

    使用javascript做時(shí)間倒數(shù)讀秒功能的實(shí)例

    今天小編就為大家分享一篇關(guān)于使用javascript做時(shí)間倒數(shù)讀秒功能的實(shí)例,小編覺得內(nèi)容挺不錯(cuò)的,現(xiàn)在分享給大家,具有很好的參考價(jià)值,需要的朋友一起跟隨小編來看看吧
    2019-01-01
  • javascript之水平橫向滾動(dòng)歌詞同步的應(yīng)用

    javascript之水平橫向滾動(dòng)歌詞同步的應(yīng)用

    javascript之水平橫向滾動(dòng)歌詞同步的應(yīng)用...
    2007-05-05
  • javascript實(shí)現(xiàn)頁面內(nèi)關(guān)鍵詞高亮顯示代碼

    javascript實(shí)現(xiàn)頁面內(nèi)關(guān)鍵詞高亮顯示代碼

    關(guān)鍵詞高亮想必大家對(duì)它都不陌生吧,應(yīng)用也比較廣泛的,下面為大家介紹下通過javascript是如何實(shí)現(xiàn)頁面內(nèi)關(guān)鍵詞高亮顯示
    2014-04-04
  • JavaScript之ECharts用法講解

    JavaScript之ECharts用法講解

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

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

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

最新評(píng)論