1. 回溯法的基本原理：

回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。用回溯算法解决问题的一般步骤为：

1、定义一个解空间，它包含问题的解。

2、利用适于搜索的方法组织解空间。

3、利用深度优先法搜索解空间。

4、利用限界函数避免移动到不可能产生解的子空间。

问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。

2.旅行售货员问题的回溯算法实现

算法具体实现主要代码如下：

// TravelSaler.cpp : 定义控制台应用程序的入口点。

//

//旅行员售货员问题 回溯法求解

#include "stdafx.h"

#include

#include

#include

using namespace std;

ifstream fin("input.txt");

const int N = 4;//图的顶点数

template

class Traveling

{

    template

    friend Type TSP(Type **a, int n);

private:

    void Backtrack(int i);

    int n,         // 图G的顶点数

        *x, // 当前解

        *bestx; // 当前最优解

    Type **a, // 图G的领接矩阵

        cc, // 当前费用

        bestc; // 当前最优值

    int NoEdge; // 无边标记

};

template

inline void Swap(Type &a, Type &b);

template

Type TSP(Type **a, int n);

int main()

{

    cout