不撞南墙不回头-深度优先搜索
基础部分
关于深度优先搜索和广度优先搜索，很难形象地表现其定义。 从一个例子切入吧。
输入一个数字n，输出1~n的所有数组。 即，在n=3情况下，输出123、132、213、231、312、321
形象化提问时，假设有3个扑克牌1、2、3张和3个号码1、2、3的箱子，有几种方法可以将3张扑克牌分别放入3个箱子中？
我们用深度优先的扫描探索思想来考虑这个问题。
走到一号箱前的时候，我们手上有一、二、三三种牌。 我们把1放进去，然后去2号箱的脸签名。 手上有两三张牌。 然后，我们把2放进去，走到3号箱子前面。 手上有三张牌。 所以，装上3，然后前进到我们想象中的4号箱子前面。 所以，我们手上没有卡(123 )。
然后，我们回到3号箱，拿出3这张照片。 这时，因为我们手里只有一张卡，再放进去就还是原来的样子，所以我们再往后推，推到2号箱子前面，把2从箱子里拿出来。 这个时候，我们手上有两三张卡。 这个时候，我们可以把3放进2号箱，然后去3号箱装2。 这又是输出的组合方式
当我们寻找这个想法，然后再次返回时，我们会退到一号箱，取出1，再分别放入2和3，产生剩下的组合方式。
虽然很罗嗦，但基本上是这样的想法。
让我们看看实现的代码
defsortnumber(self，n ) :
flag=[falseforIinrange(n ) ]
a=[0forIinrange(n ) ]
l=[]
defDFS(step ) :
if step==n:
L.append(A[:]
返回
forIinrange(n ) :
if flag[i] is False:
flag[i]=True
a[step]=i
是DFS (步骤1 )
flag[i]=False
是DFS(0)
返回l
输出为
[ 0，1，2 ]、[ 0，2，1 ]、[ 1，0，2，0 ]、[ 1，2，0，1 ]、[ 2，1，1 ]、[ 2，1，1，0 ]
我们制作的名为a的list相当于上述箱子。 名为flag的list指示是否已经使用了某个数字。
其实主要思想是在这个dfs方法中的这个for循环中，在顺序序列中，我们默认优先使用最小的数字，这个for循环其实表示有机会在一个位置把这些数字都放进去，这个flag标识避免了在一个位置重复使用数字的问题
如果if成立，则表示当前位置可以使用该数字，因此将该数字放入名为a的数组中，并将标志相同的标志更改为True。 这意味着此数已被占用，然后调用方法本身进行下一步。
代码flag[i]=False很重要，上面的dfs (即下一步)结束后，必须返回到当前阶段，模拟地回收这个数字。 也就是说，将flag设置为False，表示该数字还可以使用。
想法可能是这样的，但这是深度优先搜索的简单场景。 在调试上关注，一步一步看代码会更清楚。
迷宫问题
上面对深度优先搜索进行了简单的理解，通过迷宫的问题进一步推进数字这一算法，同时引出广度优先搜索。
迷宫由m行n列单元构成，每个单元是空地还是障碍物，我们的任务是找出从起点到终点的最短路径。
让我们抽象成模型
start表示起点，end表示终点，x表示障碍物，即不能通过的点。
让我们先分析一下。 从start (0，0 )这一点，再从各点出发，也有四个方向。 只能对上下左右、) 0，0 )这一点来说，向右和向下走。 左边和上面都在小区外面，可以说是越界了。
以深度优先的想法来考虑，从出发点开始向所有方向前进，然后遇到障碍物或到达边界时，可以改变另一个方向，然后进行到底。
得到我们的这个主题，我们可以这样想。 走路的时候，我们决定右下左上那样的顺序。 也就是说，先往右走，不能往右走时改变方向。 例如，从(0，0 )到) 0，1 )的话，) 0，1 )也会先往右走，但发现) 0，2 )是障碍物，所以改为往下走，到) 1，1 )，)
其中需要注意的是，右下左上的四个方向中有一个是我们来的时候的方向，在现在这一点上，四个方向还没有结束就不要回到前面的点。 因此，类似于前一列数字代码中的flag数组也必须记录当前位置被占用。 我们必须在四个方向结束后向前后退。
先贴在下面
代码def depthFirstSearch(self):
m = 5
n = 4
# 5行 4 列
flag = [[False for i in range(n)] for j in range(m)]
# 存储不能同行的位置
a = [[False for i in range(n)] for j in range(m)]
a[0][2] = True
a[2][2] = True
a[3][1] = True
a[4][3] = True
global min_step
min_step = 99999
director_l = [[0, 1], [1, 0], [0, -1], [-1, 0]]
def dfs(x, y, step):
# 什么情况下停止 (找到目标坐标)
if x == 3 and y == 2:
global min_step
if step < min_step:
min_step = step
return
# 右下左上
for i in range(4):
# 下一个点
nextX = x + director_l[i][0]
nextY = y + director_l[i][1]
# 是否越界
if nextX < 0 or nextX >= m or nextY < 0 or nextY >= n:
continue
# 不是障碍 and 改点还没有走过
if a[x][y] is False and flag[x][y] is False:
flag[x][y] = True
dfs(nextX, nextY, step+1)
flag[x][y] = False #回收
dfs(0, 0, 0)
return min_step
首先flag这个算是二位数组吧，来记录我们位置是否占用了，然后a这个数组，是来记录整个单元格的，也就是标识那些障碍物的位置坐标。同样的，重点是这个dfs方法，他的参数x,y是指当前的坐标，step是步数。
这个大家可以看到一个director_l的数组，他是来辅助我们根据当前左边和不同方向计算下一个位置的坐标的。
dfs中我们已经注明了搜索停止的判断方式，也就是找到(3，2)这个点，然后下面的for循环，则代表四个不同的方向，每一个方向我们都会先求出他的位置，然后判断是否越界，如果没有越界在判断是否是障碍或者是否已经走过了，满足了所有的判断条件，我们在继续往下一个点，直到找到目标，比较路径的步数。
这就是深度优先搜索了，当然，这个题目我们还有别的解法，这就到了我们说的广度优先搜索。
层层递进-广度优先搜索
我们先大体说一下广度优先搜索的思路，深度优先是先穷尽一个方向，而广度优先呢，则是基于一个位置，先拿到他所有能到达的位置，然后分别基于这些新位置，拿到他们能到达的所有位置，一次这样层层的递进，直到找到我们的终点。
从(0，0)出发，可以到达(0，1)和(1,0)，然后再从(0，1)出发到达(1，1)，从(1，0)出发，到达(2，0)和(1，1)，以此类推。
所以我们我们维护一个队列来储存每一层遍历到达的点，当然了，不要重复储存同一个点。我们用一个指针head来标识当前的基准位置，也就是说最开始指向(0，0)，当储存完毕所有(0，0)能抵达的位置时，我们就应该改变我们的基准位置了，这时候head++，就到了(0，1)这个位置，然后储存完他能到的所有位置，head++，就到了(1，0)，然后继续。
def breadthFirstSearch(self):
class Node:
def __init__(self):
x = 0
y = 0
step = 0
m, n = 5, 4
# 记录
flag = [[False for i in range(n)] for j in range(m)]
# 储存地图信息
a = [[False for i in range(n)] for j in range(m)]
a[0][2] = True
a[2][2] = True
a[3][1] = True
a[4][3] = True
# 队列
l = []
startX, startY, step = 0, 0, 0
head = 0
index = 0
node = Node()
node.x = startX
node.y = startY
node.step = step
index += 1
l.append(node)
flag[0][0] = True
director_l = [[0, 1], [1, 0], [0, -1], [-1, 0]]
while head < index:
last_node = l[head]
# 处理四个方向
for i in range(4):
# 当前位置
currentX = last_node.x + director_l[i][0]
currentY = last_node.y + director_l[i][1]
# 找到目标
if currentX == 4 and currentY == 2:
print('step = ' + str(last_node.step + 1))
return
#是否越界
if currentX < 0 or currentY < 0 or currentX >= m or currentY >= n:
continue
if a[currentX][currentY] is False and flag[currentX][currentY] is False:
#不是目标
flag[currentX][currentY] = True
node_new = Node()
node_new.x = currentX
node_new.y = currentY
node_new.step = last_node.step+1
l.append(node_new)
index += 1
head += 1
首先我们定义了一个节点Node的类，来封装节点位置和当前的步数，flag，a，director_l这两个数组作用跟深度优先搜索相同，l是我们维护的队列，head指针指向当前基准的那个位置的，index指针指向队列尾。首先我们先把第一个Node(也就是起点)存进队列，广度优先搜索不需要递归，只要加一个循环就行。
每次走到符合要求的位置，我们便把他封装成Node来存进对列中，每存一个index都要+1.
head指针必须在一个节点四个方向都处理完了之后才可以+1，变换下一个基准节点。
小结
简单的介绍了深度优先搜索和广度优先搜索，深度优先有一种先穷尽一个方向然后结合使用回溯来找到解，广度呢，可能就是每做一次操作就涵盖了所有的可能结果，然后一步步往后推出去，找到最后的解。这算我个人的理解吧，不准确也不官方，思想也只能算是稍有体会，还得继续努力。
题外话
碍于自己的算法基础太差，最近一直在做算法题，我是先刷了一段时间的题目，发现吃力了，才开始看的书。感觉有点本末倒置。其实应该是先看看书，把算法的一些常用大类搞清楚了，形成一个知识框架，这样在遇到问题的时候可以知道往那些方向上面思考，可能会好一些吧。