1. 构建基本的穷举搜索骨架

int n;int dst[100][100];int best;const int INF = 987654321;// 初始状态下，path 存入第一节点，visited 全部元素为 false，curLen = 0;void search(vector
    
     & path, vector
     
      & visited, int curLen){    if (best <= curLen)        return;    int here = path.back();    if (path.size() == n) {        best = min(best, curLen+dst[here][0]);        return;    }    for (int next = 0; next < n; ++next){        if (visited[next])            continue;        visited[next] = true;        path.push_back(next);        search(path, visited, curLen + dst[here][next]);        visited[next] = false;        path.pop_back();    }}double solve(){    best = INF;    vector
      
        visited(n, false);    vector
       
         path(1, 0);    visited[0] = true;    search(path, visited, 0);    return best;}
       
      
     
    

2. 剪枝法初步：不如最优解就当即结束

只需在 search() 函数的开头部分加入如下一行代码：

// best 初始化为INF，// 只有在 if (path.size() == n)... 才对其进行更新；if (best <= curLen)    return;

3. 剪枝法进阶：利用启发式算法的剪枝法

“不如最优解”就终止搜索的剪枝法，虽然比较有用，但比起动态规划还差很远，“利用启发式方法估计剩余部分”的剪枝法就相对巧妙得多。

比如设计这样的启发式函数，会在未访问的城市相连路径中选择最短的路径相加。

int minEdge;double simpleHeur(const vector
    
     & visited){    double ret = minEdge[0];    for (int i = 0; i < visited.size(); ++i)        if (!visited[i])            ret += minEdge[i];                                    // 城市结点之间彼此互通    return ret;}void search(vector
     
      & path, vector
      
       & visited, int curLen){    if (best <= curLen + simpleHeur(visited)) return;    //...} double solve(){     for (int i = 0; i < n; ++i){         minEdge[i] = INF;         for (int j = 0; j < n; ++j){             if (i != j)                 minEdge[i] = min(minEdge[i], dst[i][j]);         }     } }