大连理工大学算法分析与设计算法总结

《大连理工大学算法分析与设计算法总结》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一，马步程序简要算法描述：算法从1号节点作为当前节点开始进行搜索。从小到大深度优先尝试所有相连的节点，并把它作为下一次搜索的当前节点，如果最终能够回到起始点，并且每个节点经过且仅经过一次，则存在一条哈密顿回路。否则不存在哈密顿回路。优化：1，  如果走一步之后发现，存在度数小于2的未走过的节点，则没有必要继续搜索，只能尝试其他节点。2，  如果发现，当前存在大于等于两个度数为2的节点，则直接回溯到上一层节点，没有必要继续搜索。3，  回溯到第一个节点后，如果没找到哈密顿回路则直接退出，没有必要尝试其他走法，因为另一条路径与当前遍历过的路径是对称的。

2、#include#include#includeusing namespace std;const int Maxn = 10000;int dirx[] = {-1, -2, -2, -1, 1, 2, 2, 1};int diry[] = {-2, -1, 1, 2, 2, 1, -1, -2};int n1, n2, n;bool used[Maxn];int ans[Maxn];int degree[Maxn], deg[Maxn];int graph[Maxn][8];bool val

3、id(int x, int y){   return x >= 0 && x < n1 && y >= 0 && y < n2;}void getGraph(){   for (int i = 0; i 

4、col + diry[j];           if (!valid(x, y)) continue;           graph[i][degree[i]++] = x * n2 + y;       }       deg[i] = degree[i];   }}void resume(int cur){   for (int i = 0; i < degree[cur]; ++i)   {       int next = graph[cur][i];       if (used[next]) continue;       deg[

5、next]++;   }}bool update(int cur){   bool ret = true;   for (int i = 0; i < degree[cur]; ++i)   {       int next = graph[cur][i];       if (used[next]) continue;       deg[next]--;       if (deg[next] < 2 && next != graph[0][1]) ret = false;   }   if (!ret)   {       resume(cu

6、r);       return false;   }   return true;}bool dfs(int step, int cur)//递归版{   ans[step] = cur;   if (step == n - 1)   {       if (graph[0][1] != cur) return false;       for (int i = 0; i 

7、nt i = 0; i < degree[cur]; ++i)   {       if (cur == 0 && i) break;       int next = graph[cur][i];       if (used[next]) continue;       used[next] = true;       if (!update(cur))       {           used[next] = false;           continue;       }       if (dfs(step + 1, next))

8、 return true;       resume(cur);       used[next] = false;