旭明 張 發問時間: 科學數學 · 10 年前

求解旅行銷售員(tsp)的方法

我想請問一下若要求解旅行銷售員最短路逕的近似解方法,最常用的有哪些方法,現在我有各點到各點的距離(不用畢式定理來算,因為路逕不可能是直線),有沒有已經可以用的matlab程式來運算

4 個解答

評分
  • 10 年前
    最佳解答

    旅行業務員問題 (Traveling Salesman Problem) 是個有名的難題,旅行業務員要到 n 個城市推展業務,n 個城市以 1,2,…,n 表示,從 1 出發,經過每個城市恰只一次,再回到 1,令 Cij 表城市 i 到城市 j 的旅行成本,問題為找出一個最小成本的路徑。在工廠的組合線上,以機器人上緊螺絲帽,機器人從起始的位置出發,做連續的移動,上緊每一個螺絲帽,再回到起始的位置,如何找到一個最短的路徑?這亦是旅行業務員問題。這個問題難在哪裏?我們看以下的四種解法。

    (一)蠻力法(brute force method)(二)分支界定法(branch-and-bound method)

    (三)動態規劃(Dynamic Programming)

    (四)近似法詳細請參考http://episte.math.ntu.edu.tw/articles/mm/mm_11_3_...

  • 匿名使用者
    6 年前

    用心服務"貸"您解決任何債務問題,專業理財規劃一次幫你搞定貸款麻煩事

    YES貸款理財,歡迎您的加入 LINEID: hot777

    銀行貸款 免費諮詢評估 0986、 377、 776

    專辦:

    房屋貸款、房貸轉增貸款、房貸遲繳、銀行二胎貸款、信用貸款、

    民間二胎/三胎代償、代墊、土地貸款、民間二胎借款、

    負債整合、二胎借款、房貸協商、房貸整合降息、

    免費諮詢評估鑑價或協助辦理各類貸款,不事先收取手續費或代辦費

    - -歡迎同業配合- -- -歡迎同業配合- -- -歡迎同業配合- -

    推...推....

  • 匿名使用者
    7 年前

    台灣首家合法娛樂城開幕囉!

    體育博彩、真人對戰、現場遊戲、彩球

    投注高賠率,歡迎您來體驗!

    官方網站 aa777.net

  • Elisha
    Lv 6
    10 年前

    那其實是有可能的, 因為你的距離都非直線

還有問題?馬上發問,尋求解答。