演算法 - 售貨員旅行問題 (traveling salesman problem)

售貨員旅行問題是一種最佳化的問題，可以利用回溯或動態規劃來解決，在蔡宗翰譯的「演算法--使用C++虛擬碼」書中(碁峯資訊，2004年)，第六章「BRANCH-AND-BOUND」，分枝界限修剪法之最佳優先搜尋的方法能更快地解決問題。

在許多個城市中，售貨員必須節省他的時間走訪美一個城市去銷售他的物品，最後再回到原本的城市中，但城市與城市之災來回的時間不一樣，這可能是因為城市與城市之間的高速公路常常塞車，亦或是可能碰到一些單行道....等，所以依照時間的不確定性，找出一個最有效率的走法，這類問題稱之為售貨員旅行問題。

利用回溯，可先求出一段路徑作為比較基準，比之大就不再走下去，比之小就已它作為基準繼續再找更小的路徑，一直找到最後，最佳路徑即會出現，建構 TravelingSalesperson 類別傳入 W 陣列，W[i][j] 代表從城市 i 到城市 j 所花的時間，最後 bestPath 紀錄最佳路徑的走法，minlength 則是最佳路徑的時間長度，以下為 C# 範例程式碼：

class TravelingSalesperson
{
    int n;
    int[,] W;
    public int[] recordPath, bestPath;
    public int length, minlength;
    public TravelingSalesperson(int[,] W)
    {
        this.W = W;
        length = 0;
        minlength = int.MaxValue;
        n = W.GetLength(0);

        recordPath = new int[n];
        bestPath = new int[n];

        for (int i = 0; i < n; i++)
        {
            recordPath[i] = i;
            bestPath[i] = i;
        }
    }

    public void teavel(int i)
    {
        if (i > n - 1)
        {
            length += W[recordPath[n - 1], 0];
            if (length < minlength)
            {
                minlength = length;
                for (int k = 0; k < n; k++)
                    bestPath[k] = recordPath[k];
            }
            length -= W[recordPath[n - 1], 0];
            return;
        }

        for (int j = i; j < n; j++)
        {
            swapRecordPath(j, i);
            length += W[recordPath[i - 1], recordPath[i]];

            if (length < minlength)
                teavel(i + 1);

            length -= W[recordPath[i - 1], recordPath[i]];
            swapRecordPath(j, i);
        }
    }

    public void swapRecordPath(int i, int j)
    {
        int temp = recordPath[i];
        recordPath[i] = recordPath[j];
        recordPath[j] = temp;
    }
}

而分枝界限修剪法之最佳優先搜尋的方法，則提供 C# 原始碼，有興趣可以買書來參考，傳入 W 陣列，W[i][j] 代表從城市 i 到城市 j 所花的時間，minlength 則是傳入一個大於任何最佳解的數即可：

struct node
{
    public int level, bound;
    public string path;
    public bool[] isUse;
}

class Travel
{
    int[,] W;
    public node init;
    public int minlength;
    public string opttour;
    int num;

    public Travel(int[,] W, int minlength)
    {
        this.W = W;
        num = W.GetLength(0);

        init = new node();
        init.isUse = new bool[num];

        init.level = 0;
        init.path = "0";
        init.isUse[0] = true;
        init.bound = bound(init);

        this.minlength = minlength;
    }

    public void solve(node n)
    {
        List<node> PQ = new List<node>();
        node v = new node();
       

        if (n.bound < minlength)
        {
            if (n.level == num - 2)
            {
                int i;
                for (i = 0; n.isUse[i]; i++) ;
                n.path += string.Format(",{0}", i);

                int temp = length(n);
                if (temp < minlength)
                {
                    minlength = temp;
                    opttour = n.path;
                }

            }
            else
            {
                for (int i = 1; i < num; i++)
                {
                    if (n.isUse[i]) continue;


                    v.level = n.level + 1;
                    v.path = n.path + string.Format(",{0}", i);
                    v.isUse = new bool[num];
                    for (int j = 0; j < num; j ++)
                        v.isUse[j] = n.isUse[j];

                    v.isUse[i] = true;
                    v.bound = bound(v);

                    PQ.Add(v);
                    for (int j = PQ.Count - 1; j >= 1; j--)
                        if (PQ[j].bound < PQ[j - 1].bound)
                        {
                            node temp = PQ[j];
                            PQ[j] = PQ[j - 1];
                            PQ[j - 1] = temp;
                        }
                        else break;
                }
            }


            for (int i = 0; i < PQ.Count; i++)
                solve(PQ[i]);
        }
    }

    public int bound(node n)
    {
        int intBound = 0;
        int[] aIntPath = readPath(n.path);
        int intPathLen = aIntPath.Length;

        for (int i = 0; i < intPathLen - 1; i++)
            intBound += W[aIntPath[i], aIntPath[i + 1]];

        for (int i = 0; i < num; i++)
        {
            if (n.isUse[i] && i != aIntPath[intPathLen - 1]) 
                continue;

            int min = int.MaxValue;

            for (int j = 0; j < num; j++)
            {
                if (intPathLen > 1 && aIntPath[intPathLen - 1] == i 
                    && aIntPath[0] == j) continue;

                if (n.isUse[j] && j != aIntPath[0]) continue;

                if (i != j && W[i, j] < min)
                    min = W[i, j];
            }
            intBound += min;
        }
        aIntPath = null;
        return intBound;
    }

    public int length(node n)
    {
        int intLength = 0;
        int[] aIntPath = readPath(n.path);
        int intPathLen = aIntPath.Length;

        for (int i = 0; i < intPathLen - 1; i++)
            intLength += W[aIntPath[i], aIntPath[i + 1]];

        intLength += W[aIntPath[intPathLen - 1], aIntPath[0]];

        return intLength;
    }

    int[] readPath(string strPath)
    {
        string[] aStrPath = strPath.Split(new char[] { ',' },
            StringSplitOptions.RemoveEmptyEntries);

        int intPathLen = aStrPath.Length;

        int[] aIntPath = new int[intPathLen];
        for (int i = 0; i < intPathLen; i++)
            aIntPath[i] = Convert.ToInt32(aStrPath[i]);

        aStrPath = null;
        return aIntPath;
    }
}

回首頁