《人工智能导论》
课程设计
深度优先搜索算法解决加法问题
姓名：张三三
班级：计机081
学号：20080999
深度优先搜索算法解决加法问题
1.问题描述
每个字母代表一个数字，且不能重复。

并且要使竖式成立。

s e t d
+ m o r d
---------
m o t e y
2.涉及算法描述
深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。

在深度优先搜索中，对于最新发现的顶点，如果它还有以此为起点而未探测到的边，就沿此边继续汉下去。

当结点v 的所有边都己被探寻过，搜索将回溯到发现结点v有那条边的始结点。

这一过程一直进行到已发现从源结点可达的所有结点为止。

如果还存在未被发现的结点，则选择其中一个作为源结点并重复以上过程，整个进程反复进行直到所有结点都被发现为止。

3.程序伪码或分析流程或结题思路等（全部源码必须另外交，代码需要注释，但不打印）//分析：考虑到m 为s+m 后的进位，则m必为0或1。

//注意：由于题目没有指明m是否可以为0，所以认为m是可以为0的。

20.#include <iostream>
ing namespace std;
22.
23.int main(void)
24.{
25. int s,e,t,d;
26. int m,o,r,y;
27. int sum,tmp,i;
28.
29. for ( m=0; m<=1; m++ )
30. {
31. for ( o=0; o<=9; o++ )
32. {
33. if ( o==m ) continue;
34.
35. for ( r=0; r<=9; r++ )
36. {
37. if ( r==m || r==o ) continue;
38.
39. for ( d=0; d<=9; d++ )
40. {
41. if( d==m || d==o || d==r ) continue;
42.
43. for ( s=0; s<=9; s++ )
44. {
45. if ( s==m || s==o || s==r || s==d ) continue;
46.
47. for ( e=0; e<=9; e++ )
48. {
49. if ( e==m || e==o || e==r || e==d || e==s ) continue;
50.
51. for ( t=0; t<=9; t++ )
52. {
53. if ( t==m || t==o || t==r || t==d || t== s || t==e ) continue;
54.
55. sum = (s*1000+e*100+t*10+d) + (m*1000+o*100+r*10+d);
56. y = sum%10;
57.
58. if ( y%2 != 0 ) continue;
59.
60. if ( y==s || y==e || y==t || y==d || y==m || y==o || y==r ) continue;
61.
62. tmp = sum;
63.
64. for ( i=1; i<=5; i++ )
65. {
66. if ( i==2 && tmp%10 != e ) break;
67. else if ( i==3 && tmp%10 != t ) break;
68. else if ( i==4 && tmp%10 != o ) break;
69. else if ( i==5 && tmp%10 != m ) break;
70.
71. tmp /= 10;
72. }
73.
74. if ( i==6 )
75. {
76. cout<<s<<e<<t<<d<<" + "<<m<<o<<r<<d<<" = "<<m<<o<<t<<e<<y<<endl;
77. }
78. }
79. }
80. }
81. }
82. }
83. }
84. }
85.
86. return 0;
87.}
4.演示结果（包含全部中间结果，也可以制作一个动画进行演示）
2817 + 0367 = 03184
3716 + 0456 = 04172
3718 + 0458 = 04176
3719 + 0459 = 04178
5731 + 0641 = 06372
6419 + 0729 = 07148
6851 + 0731 = 07582
6852 + 0732 = 07584
6524 + 0734 = 07258
7536 + 0816 = 08352
8652 + 0912 = 09564
8762 + 0912 = 09674
8543 + 0913 = 09456
9346 + 1086 = 10432
9456 + 1086 = 10542
9237 + 1087 = 10324
9567 + 1087 = 10654
5.算法分析与结论
对于具有n个顶点和e条边的无向图或有向图，遍历算法DFSTraverse对图中每顶点至多调用一次DFS或DFSM。

从DFSTraverse中调用DFS(或DFSM)及DFS(或DFSM)内部递归调用自己的总次数为n。

当访问某顶点v i时，DFS(的时间主要耗费在从该顶点出发搜索它的所有邻接点上。

用邻接矩阵表示图时，其搜索时间为O(n)；用邻接表表示图时，需搜索第i个边表上的所有结点。

因此，对所有n个顶点访问，在邻接矩阵上共需检查n2个矩阵元素，在邻接表上需将边表中所有O(e)个结点检查一遍。

所以，DFSTraverse的时间复杂度为O(n2) （调用DFSM）或O(n+e)（调用DFS）。