匿名使用者
匿名使用者 發問時間: 電腦與網際網路程式設計 · 7 年前

traveling salesman problem

我想要一份使用B&B(Branch and bound)解決traveling salesman problem的程式碼

本來想下手了 突然看到一些很精簡的程式碼 不過輸入幾組測試數據卻沒找到最短路徑

請手邊有code的分享一下 可以的話c優先~

已更新項目:

可以傳到kamtupo371@yahoo.com.tw 或者上傳至免空,知識家可能擺不下~

2 個已更新項目:

我發現我看不太懂... 可以說明一下步驟嗎?

還有我問一下 Branch and Bound 不是currCost較低先做 其餘保留 這部分要怎去解決它?

3 個已更新項目:

對於這部分if (cheapest <= currCost) return;

這樣不會導致他可能只是現在cost較多 但是之後可能是比較少的

直接return不是表示不管這條路了嗎?

4 個已更新項目:

看來看去 大家的code幾乎都是跟這部分很像if (cheapest <= currCost) return;

看來B&B好像是這樣 這樣比我當初想的好寫很多

不過我現在又產生新的疑惑..

就是假設 選A→B的下限是17,不選擇則是20

照這演算法他一定會選17,這樣不會發生選17後,後面付出的cost反而比較多的情況嗎?

5 個已更新項目:

剛剛拋棄我原本的想法.. 照著你的code跑一次

才發現原來branch and bound是會先找到一組解(但可能不是最佳解)

然後再用這組解的cost下去剃除掉cost比他多的任何步驟

所以是我把branch and bound看得太難了...

我原本的想法是每次都挑目前這棵樹中還沒延展過cost最小的

所以深度有可能變小,然後我就想說這樣不就要把每次的矩陣都記錄下來

在放到queue裡去挑

GOOD~

6 個已更新項目:

你英文真得很好說.. 我最不方便的就是英文不好 每次看到一堆英文資料我都會先略過...

有空我會找演算法老師問問B&B到底是怎樣跑~

7 個已更新項目:

今天去問了一下演算法老師 他說的B&B好像就是原本我想的那樣

所以你這應該是屬於Depth-First Search(DFS)

那應該沒問題了~ 有空我在自己試看看怎做

很感謝你的回答 我第一次看到這麼精簡的code 讓我學到不少~

1 個解答

評分
  • 7 年前
    最佳解答

    #include <stdio.h>

    #include <string.h>

    #include <math.h>

    #include <stdlib.h>

    #define X (18) // number of cities

    int fee[X][X];

    int cheapest;

    int sol[X];

    void

    dump(

    int *arr,

    int sz

    ){

    int *strt = arr;

    for(;--sz > 0;++arr) printf(" %2d (%2d)", *arr, fee[arr[0]][arr[1]]);

    printf(" %2d (%2d) %2d:%d\n", *arr, fee[*arr][*strt], *strt, cheapest);

    }

    void

    mov(

    int *visited, // have visited

    int *toVisit, // not yet

    int noVisit, // number of city visited

    int max, // max city

    int currCost // current cost

    ){

    int i, arr[X];

    if (cheapest <= currCost) return;

    if (noVisit >= max) {

    i = fee[visited[noVisit-1]][visited[0]];

    if ((currCost + i) < cheapest) {

    cheapest = currCost + i;

    memcpy(sol, visited, sizeof(sol));

    }

    return;

    }

    memcpy(arr, toVisit, sizeof(arr[0]) * (max - noVisit));

    for(i = max - noVisit - 1; i >= 0; --i){

    arr[i] = arr[0];

    arr[0] = toVisit[i];

    visited[noVisit] = arr[0];

    mov(visited, &arr[1], noVisit+1, max, currCost + fee[visited[noVisit-1]][visited[noVisit]]);

    // switch back

    arr[i] = toVisit[i];

    arr[0] = toVisit[0];

    }

    } // end of mov

    int main(

    int argc,

    char *argv[]

    ){

    int i, j, k;

    int t[X], v[X];

    for(i = X-1; i >= 0; --i)

    for(j = X-1; j >= 0; --j)

    fee[i][j] = rand()%100; // random travel cost

    for(k = X-1; k >= 0; --k){

    for(i = X-1; i >= 0; --i) t[i] = (i+k)%X;

    v[0] = t[0]; // the start city

    cheapest = 101*X; // the impossible cost

    mov(v,&t[1],1,X,0); // start moving

    dump(sol, X); // dump the solution

    }

    return 0;

    }

    2013-04-27 02:37:37 補充:

    Very slow, though. It took ~3sec to run 18 cities on my 2.3ghz Opteron 8378.

    2013-04-27 10:51:55 補充:

    這是很基本的寫法。我沒有branch 只用了很簡單的bound:

       if (cheapest <= currCost) return;

    2013-04-27 10:54:25 補充:

    要用branch的話 你可以在這裡

    memcpy(arr, toVisit, sizeof(arr[0]) * (max - noVisit));

    把arr[] sort一下

    2013-04-27 21:05:21 補充:

    這樣不會導致他可能只是現在cost較多 但是之後可能是比較少的

    旅行費用只會漸增吧?

    直接return不是表示不管這條路了嗎?

    是的

    2013-04-28 03:53:13 補充:

    妳好像很聰明耶 想這麼多

    等我開始上algorithms的課我再來悔想你的說法吧!

    2013-04-29 03:04:56 補充:

    Most B&B for TSP are just heuristic that cannot be proven optimal. but anything in polynomial time might worth trying as long as you have time to implement it.

    Also, I really hate to take 數學系開的algorithms的課, most boys there are uncool.

    2013-05-02 00:31:23 補充:

    B&B never specifies how to branch and how to bound the solution tree so DFS can also be categorized as B&B by adding more heuristics on branching.

    My code actually reduced the call to mov() from 20! to about 300M.

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