Problem 216 Getting in Line，連線作業

這個問題有點像是銷售員旅行問題(Travelling Salesman Problem, TSP)，但是不用回到出發點，也就是不用將最後一點與第一點再連接，解決 TSP 的方法很多，這裡的題目特別點出最多只有八台電腦要連結，所以可能的解答只有 8! = 40320 種方法，所以最簡單的方式就是將每個可能的答案都算出來，將最小的解答顯示出來，就OK啦。
在這裡，我又用到了回溯的方法，在C語言主程式中的初始呼叫如下：

for (i=0;i<n;i++)
{
    computer[0] = i;
    makeConn(0);
}

然後，makeConn(0)會去呼叫makeConn(1)，呼叫前先將連線的 computer[1]也設定下一個，因為不能重複，所以要用 i_in_conn 來處理，等到了makeConn(7)，表示八台電腦都設完了，就計算一下連線長度，再將最小的解答儲存，這樣就可以了。 makeConn 回溯的程式碼如下，這裡的 minlength, opttour, computer 都是全域變數：

void makeConn(int level)
{
    int i, j, i_in_conn;
    double len;
    if (level == n-1)
    {
        len = connLength(); /* your function to calculate the connection length */
        if (minlength > len)
        {
            minlength = len;
            for (j=0;j<n;j++)
                opttour[j] = computer[j];
        }
    }
    else
    {
        for (i=0;i<n;i++)
        {
            i_in_conn = 0;
            for (j=0;j<=level;j++)
                if (computer[j]==i)
                    i_in_conn = 1;
            if (!i_in_conn)
            {
                computer[level+1] = i;
                makeConn(level+1);
            }
        }
    }
}

p216題目連結
回ACM題庫目錄
回首頁