一、动态规划
找到两点间的最短路径，找最匹配一组点的线，等等，都可能会用动态规划来解决。
参考如何理解动态规划中，第二个回答。冒泡
想要找到最短的从A到 Z的路径。
贪心算法：就是每次选择最优。
对应到参考的回答中，是每次选择最短的路径，对应到python数据结构教材中，就是每次先找面额最大的硬币。
贪心算法的缺点：
在路径问题中，是在A到I，I到Z的过程，都可以任意选择的。然而若是加了条件限制，比如走了I就不能再走H了。这样即使第一步选择了最短的路径，也不能保证，往后走得就是最优路径。
穷举算法：
为了避免上述情况的发生，我们可以走完所有的路径，然后选择一条最好的。这就是穷举。
对应到教材中，就是把所有可能找零的硬币数都列出来，然后挑最少的。
接下来就教材中的硬币例子，说明动态规划。
递归与动态规划：
首先，对于需要找零63美分的情况。硬币面额有1,5,10,25美分。
我们可以这么利用递归思想：
- 1.一开始，假设63美分的最优解里已经找了一个硬币。那么这个硬币可能是上面四个面额。mincoin=0+1=1
- 2、既然已经找了一个硬币，那么还剩63-coin的面额。然后再从剩下的面额的最优解中，再找一个硬币，这个硬币也可能是1.5.10.25美分。此时 ，mincoin= 1+1=2
- 3、循环上面，一直找到最优解为止。
即：
但是，这个就相当于穷举了，算法太低效。
重点：
从教材中可知，上面算法，有许多重复的路径，比如剩余面额为16的时候，就在不同的递归路径中出现了。所以，我们为了避免这种重复的面额还要被递归，可以将已经出现的面额所需要的最小找零 硬币个数存起来。比如将16的最小找零面额3存起来，等下次再递归遇到16时，直接判断出现过16，返回3即可。
这次，算法就比较高效了。里面已经有了动态规划的思想：把已经知道的最好的路径存起来，下次遇到可以直接用。
def recDC(coinValueList,change,knownResults):
minCoins = change
if change in coinValueList:
knownResults[change] = 1
return 1
#遇到了已经出现了的面额，而我们又已经计算出了需要的最少硬币数，可以直接调出来返回该数就行了。
elif knownResults[change] > 0:
return knownResults[change]
else:
for i in [c for c in coinValueList if c <= change]:
numCoins = 1 + recDC(coinValueList, change-i,
knownResults)
if numCoins < minCoins:
minCoins = numCoins
knownResults[change] = minCoins
return minCoins
print(recDC([1,5,10,25],63,[0]*64))
重要思想：构造一个列表，存储已经出现过的面额需要的最小硬币数。在递归过程中，遇到了已经出现了的面额，而我们又已经计算出了需要的最少硬币数，可以直接调出来返回该数就行了。
但是，我们采用的还不是动态规划的方法。我们只是“缓存”了面额，改善了程序的性能。
真正的动态规划：
真正的动态规划会采用更系统化的方法来解决问题。
动态规划的解决方法是从为1分钱找零的最优解开始，逐步递加上去，直到我们需要的找零钱数。这就保证了在算法的每一步过程中，我们已经知道了兑换任何更小数值的零钱时所需的硬币数量的最小值。
那么此时，动态规划的函数需要有三个参数，
一个是有效硬币面额列表[1.5.10.25],
一个是包含从1到63美分的change的最优解的列表，这个列表就是动态规划的重点。把重要的都存了起来。
一个是需要找零的change，63.
教材里的代码没有用递归函数写。可以用for循环来写。
这段代码，需要先定义两个字典
- 一个是minCoins，用来存储cents对应的最少找零数。
- 一个是coinUserd，用来存储cents对应的倒数第一个找零的硬币 ，比如63对应21，下次会找到42对应21，21对应21，可以用来输出cents所有找零面额。
def dpMakeChange(coinValueList,change,minCoins,coinsUsed):
for cents in range(change+1):#从1分到63美分挨个计算
coinCount = cents#先初始化找零的硬币数，假设都用1美分找零
newCoin = 1
#把下面的循环，用例子写出来就能看懂了。重要的是理解思想。
for j in [c for c in coinValueList if c <= cents]:
#这一句是精髓，用来确定当前cents找零的最小硬币数目
if minCoins[cents-j] + 1 < coinCount:
coinCount = minCoins[cents-j]+1
newCoin = j
minCoins[cents] = coinCount
coinsUsed[cents] = newCoin
return minCoins[change]
最后，再加上一个追踪硬币的功能，就算利用动态规划完成了找零的任务。
理解BFS以及DFS主要就是程序中的几个要点。记住了就好。
二、广度优先搜索（BFS）
2.1 、通过词梯问题，了解BFS。
词梯问题：。比如，将单词“ FOOL”转变成单词“ SAGE”。在词梯问题中，你必须以一次只改变一个字母的方式来逐步转变单词。每一步你都必须将一个单词转变成另一个单词，并且不允许转变成一个不存在的单词。
词梯问题还有很多的变形。比如你可能被要求以给定的步数完成单词转换，或者你必须使用一个特定的单词。在本节内容中，我们感兴趣的是如何算出从开始单词到目标单词所需要的最小转换次数。
为了能用图解决这个问题，我们通过两步来达到目标：
- 1、先建立一个图，描绘出单词之间的关系。
可以建立一个图的类graph。 - 2、图已经建立好，再用广度优先搜索（BFS）的图算法找到最短路径。
2.2 图的表现形式
图的表现形式主要有两个，一个是邻接矩阵，一个是邻接表。
对于邻接矩阵和邻接表的介绍参见教材7.5-7.6节。
邻接表：一个实现稀疏图的更高效的方案是使用邻接表 adjacency list。在这个实现方法中，我们维护一个包含所有顶点的主列表（master list），主列表中的每个顶点，再关联一个与自身有边连接的所有顶点的列表。在实现顶点类的方法里，我们使用字典而不是列表，此时字典中的键（key）对应顶点标识，而值（value）则可以保存顶点连接边的权重。
实现邻接表，需要用到两个类，一个是图graph，一个是顶点vertex。
2.3 建立word ladder图
把问题细化再优化：
- 1、就像动态规划中，我们把对63美分的零钱找零一样，我们先把问题细化成一次找一个硬币（贪心，穷举）来找到最优解，然后再优化（优化成动态规划）。
- 2、就像打算用图解决问题一样，我们细化问题，先建立一个图，再用图算法。
- 3、同样，这里也是。我们把“建立词梯图”问题细化成：首先明确建立什么样的图，再考虑怎么建立这个图。
2.3.1 建立什么样的图
我们第一个问题是去解决如何将大量单词组成的集合转变成图。我们想要的是在两个仅差一个字母的单词之间连一条边。如果我们可以创建一个这样的图表，那么任一从一个单词到另一个单词的路径都是某个词梯问题的一个解。图中显示了一个由一些单词构成的小图，可以解决从“ FOOL”转变成“SAGE”的词梯问题。值得注意的是，该图是无向图，并且边是没有权的。
2.3.2 怎么建造这个图
简单粗暴的方法：
假设有一个单词列表，这个列表中所有的单词长度都是4。
- 我们为这个列表中每个单词创建一个顶点。
- 为了将这些单词连接起来，我们可以将列表中的每个词与所有其他单词进行比较。
- 若是该单词，和比较的单词只有一个字母不同，就可以在图中创建一条连接他们的边。
但是这个方法的时间复杂度是O(n2)。假设有5110个单词，n2比2600万还大。
优化这个方法：
上面的方法， 是每次来一个单词，都与所有的单词进行比较。比如来了pope，会和第一个字母不同的单词（rope，nope，hope），也会和第二个字母不同的单词（pipe，pape）进行比较，然后再将有联系的单词连接起来。以此类推。这样会比较冗余。
我们可以把同一个单词类型，都放到一个桶里。
比如_ope，就是只要第一个字母不同的单词，都放到这个桶里去，不用再去和别的单词进行比较了。
对应到上面的，就是，来一个pope，我们放到_ope里去，下一次来了rope，我们也放到_ope去，这样就避免了让新来的单词跟所有的单词“见面”，只需要找到属于自己的桶就行了。
这样结束以后，我们可以认为，在同一个_ope桶里的，都是第一个字母不一样的，相互连接的单词。
如下图：
上述方法，用Python实现的话，就是把桶的表示作为字典key，把桶里的单词作为value。
构建图的时候，对一个桶的m个单词，两两之间添加联系。
for word1 in d[bucket]:
for word2 in d[bucket]:
if word1 != word2:
g.addEdge(word1,word2)
最后返回图就行了。
2.3.3 用广度优先搜索法（BFS）解决这个图问题
直观理解：在搜索完第k层的节点之前，是不会搜索第k+1层的节点的。
想像BFS的运行原理：
BFS过程，就是建造一棵以顶点 s 为根的树的过程，一次建造树的一层，同时，BFS在增加k+1层次之前，会保证将所有的k层的子顶点都添加在了树中。
追踪这个过程：
- 1、BFS 算法在搜索过程中，会给每一个顶点染色为白色、灰色或黑色。
- 2、每一个顶点在被构建时都被初始化为白色，在这之后，白色代表的是尚未被发现的顶点。
- 3、当一个顶点被第一次发现后，它被染成灰色（下次别的点搜索到这个点时，发现是灰色就说明已经被发现了，就不会再进行搜索了。）
- 4、当广度优先搜索(BFS)完全探索完一个顶点后，它被染成黑色。
这意味着一旦一个节点染成了黑色，它就没有邻近的白色节点；而另一方面，如果一个顶点被标识为了灰色，这就意味着其附近可能还存在着未探索的顶点等待被探索。
代码实现：
广度优先搜索算法使用的是前文出现过的邻接表来实现的图。此外，它还使用了一个队列来决定下一步应该探索哪一个顶点。
队列的作用：扫描到一个顶点，会把该顶点添加到队尾。由于队列的后进后出。只有当把距离为k的顶点都从队列中弹出完了以后，队首才会是距离为k+1的顶点，然后接着把距离为k+2的顶点扫到队尾。
广度优先搜索（BFS） 从起始顶点 s 开始，此时 s 的颜色被设置为灰色，代表它现在已经被发现了，另外两个参数——距离和父顶点，对于起始节点 s 初始设置为了 0 和 None。随后，起始节点会被加入到一个队列中，下一步便是系统地探索队首顶点。这个过程通过迭代（遍历）队首顶点的邻接列表来完成，每检查邻接表中的一个顶点，便会维护这个顶点的颜色参量，如果颜色是白色的，就说明这个节点尚未被探索，也就会按下述四步操作：
1、 把这个新的未探索的节点 nbr，标记为灰色；
2、 nbr 的父顶点被设置为当前节点 currentVert；
比如，我是从a点向下搜索到了b点，那么a就为b的父节点3、 nbr 的距离被设置为当前节点的距离加一；
比如从顶点s到a的距离是sa，那么从顶点s到b的距离一定是sa+1.4、 nbr 被加入队尾，直到在当前顶点的邻接列表中的所有顶点nbr被搜索完后，才能够进行下一层次的探索操作。
假设队列的队首顶点是a，a到顶点的距离是sa，那么，会在搜索完a的下一层的所有距离为sa+1的顶点。把a的颜色标记为黑色。弹出a。此时a后面的节点变为队首。
若a2距离顶点的距离一样等于sa，那么也会搜索完a2的下一层所有距离为sa+1的顶点。
这样循环下去。
from pythonds.graphs import Graph, Vertex
from pythonds.basic import Queue
def bfs(g,start):
start.setDistance(0)
start.setPred(None)
vertQueue = Queue()
vertQueue.enqueue(start)
while (vertQueue.size() > 0):
#当前点是队首的点
currentVert = vertQueue.dequeue()
for nbr in currentVert.getConnections():#遍历当前点的所有nbr节点
if (nbr.getColor() == 'white'):#如果是白色，就按照上述四步进行操作。
nbr.setColor('gray')
nbr.setDistance(currentVert.getDistance() + 1)
nbr.setPred(currentVert)
vertQueue.enqueue(nbr)
#当前节点的nbr节点被遍历完，将当前节点标记为黑色。
currentVert.setColor('black')
如果，当 bfs 函数从节点a检查到节点 b 时，发现它的颜色已经染为了灰色，这代表它已经被发现过了，并且表明从起始节点到 b之间有一条更短的路径。
- 1、顶点s到a的距离为sa，s到b的距离为sa+1。又因为BFS只有在搜索当前层节点以后，才会搜索下一层的节点。
- 2、说明在搜到a之前，已经搜索过b了，而且，之前那条路径从顶点s到b的距离小于等于sa。
- 3、所以表明，此时从顶点s到b之间有一个更短的路径，于是可以放弃当前的从s到a再到b的路径。
于是，由上面分析，可以知道，确实，代码构建的树实现了每次从节点s到b都是最短的路径。
更加形象的例子参考教材Python算法
总结
所以，BFS也就是开始说的两步：
- 1、构建图：用相邻表构建，用到了字典的知识
- 2、BFS搜索，主要是理解两点：一、搜索思想，搜索完第k层以后，才会搜索第k+1层。二、追踪节点，就是上面的发现节点以后的四小步：若是白节点b，变灰-->当前节点a设置为节点b的父节点-->该节点距离设置为sa+1-->把b添加到队尾。
理顺了，BFS也就理解了。
另外，BFS还能够让我们从树的任一节点出发，沿着父节点返回到根节点，从而得到从这个节点的词到根节点的词的最短词梯。
广度优先搜索的时间复杂度分析:
尽管是两个循环，while跟for，就相当于，两个for，第一个for的循环次数是1。第二个for的循环次数是该节点的相邻点的个数。
由于每个节点仅被发现一次，因此每个节点入栈和出栈各一次，时间均为O(1),故所有V个节点入栈和出栈总时间为O(V)
由于需要对每个节点的邻接表进行扫描，时间为O(Adj[u]),总时间为O(E);
V代表节点总数，E代表图的所有边的总数。一次while和for，只是遍历了一次一个节点的所有nbr。一个节点出入栈一次，时间为1，遍历这个节点nbr时间为adj[u]（也就是判断这个节点具有几个nbr），所以这次的while和for的时间复杂度是1+adj[u]。
那么V各节点，找了E次，就是V+E。
注意，这里不能认为while同等于for遍历V次。
首先因为while循环的条件是栈不为空，这个栈一共会出栈进栈V个节点，所以while会循环V次。
！！！但是！！！，每次循环时，for所查找的每个节点的相邻点的个数是不一样的！！！都是不确定的，所以不能单纯的就是相乘。
比如第一次while循环时，for找到了当前点有2个相邻点，下次的vert，for可能只找到了一个。
综上所示，广度优先搜索的时间复杂度为O(V+E).即是图邻接表大小的线性函数。
三、深度优先搜索（DFS）
我们用于解决骑士周游问题的搜索算法是 Depth First Search (DFS)——深度优先搜索算法。前面讨论的 BFS（广度优先搜索算法）是一次建立搜索树的一层，而 DFS 算法则是尽可能深的搜索树的一枝。
同理于用BFS解决词梯问题的步骤，对于用DFS解决骑士周游问题也是采用两步走的方案：
- 1、建立一个图。
将棋盘上合法的走棋次序表示为一个图。 - 2、利用图搜索算法找到答案。
利用DFS算法搜索一个长度为（行 x 列 -1）的路径，此路径上恰好包含每个顶点一次。
3.1 建立骑士周游图
问题细化：
- 1、将棋盘的每个格子用图的顶点表示。见左下
- 2、骑士从点a可以合法移动到点b，则在图中，a和b就用边连接起来。
根据上面两点，可以构建图：
- 1、for每行，for每列，得到一个棋盘上的点的行列信息。
- 2、用一个pos_to_nodeid函数将棋盘上点位置的行列信息转换成一个线性顶点数。（如上左图的表示方法）。
- 3、用gen_legal_Moves函数来创建当前这个格子上骑士所有合法移动的列表。
- 4、将得到列表中的每个点和当前点用addEdge方法，用边连接起来。
于是得到一个图。
3.2 用DFS算法解决问题
3.2.1 DFS算法的思想
DFS算法尽可能深的搜索每个树枝，一直搜索到最深的那一个为止。
所以DFS很适合用于发现一条包含63条边的路径。
当DFS走到一条死路（再也没有可能的合法移动的方式）时，它会沿着树返回直到该节点有路可走。然后继续往深处探索。
3.3.2 DFS的递归函数
在DFS中，我们递归调用knightTour函数，将节点传入此函数，这个函数能够返回这个节点能够走的最长的path。
knightTour函数需要四个传递参量：
- n ，当前树的深度；
- path ，这个节点前所有已访问的点的列表；
- u ，我们能够探索的点；
- limit ，搜索总深度限制。
该函数递归使用：当 knightTour 被调用时，首先检查基础状态：如果 path 包含有 64 个节点，函数 knightTour返回 True 表示已经找到一条可周游的路径；如果 path 还不够长，我们继续选择一个新节点并以此为参数调用自身。
该函数结束条件，path包含64个节点，或者当前节点不能再走下去。
DFS对节点的追踪：
DFS 算法还需要使用“颜色”来追踪图中哪些节点已经被访问过了。未访问的节点染为白色，访问过的染为灰色。
DFS使用栈：
在 BFS 里面我们用 queue（队列）来跟踪要访问的节点，而在 DFS 里由于我们使用了递归，也即默认使用了 Stack（栈）来实现我们的回溯机制。
具体的解释：
当我们从knightTour函数返回 False时（ 代码第11行），我们依然在 while 循环里面并在 nbrList 中寻找下一个要搜索的节点。也就是说，对于深度为path_a的节点a来说，它的相邻点b（path_a+1的点）有若干个，若其中一个b1调用knightTour后返回了False，说明从a到b1再往后就走不通了。
此时不会跳出while循环，会继续对另一个b2调用这个函数，如果不返回false，说明从a到b2再往后还有路走，那就一直深挖下去。
如果a的所有相邻点都最终返回了false，可能此时从顶点s到a到a的相邻点的路深度分别为path_sab1=20,path_sab2=30,path_sab3=25,都小于63，那么说明经过a点也不会找到最长路径，那么此时以a为参数的递归调用也返回false。
from pythonds.graphs import Graph, Vertex
def knightTour(n,path,u,limit):
u.setColor('gray')
path.append(u)
if n < limit:#当path小于63时，继续往深了搜索
nbrList = list(u.getConnections())
i = 0
done = False
while i < len(nbrList) and not done:#保证将当前节点的相邻点都深度搜索完
if nbrList[i].getColor() == 'white':
#当找不到路，或者是path不符合条件时，返回false
done = knightTour(n+1, path, nbrList[i], limit)
i = i + 1
if not done: # prepare to backtrack
#如果按照上述方法探索后，这个路径不能达到最深，那么说明这个路径不对
#因为要遍历每一个节点，所以最优的路径还是会用到这个节点
#因此需要将这个节点但从栈中弹出，并且将这个点的颜色还原为白色，保证还能再用
path.pop()
u.setColor('white')
else:
done = True
return done
DFS总结
也是说的两步走：
- 1、建立图
- 2、用栈的思想，探索一个节点a，就标记为灰色然后入栈，继续探索下面的节点b，b的深度为sa+1，b入栈，标记为灰色。若是探索完b返回false，那么就将b弹出，b变回白色。再探索a的另一个相邻点b1。
- 3、直到探索的点的深度达到要求。
3.3.3 目前DFS的缺点--搜的太傻，不如启发式搜索
当前骑士周游算法是一个时间复杂度为O(kN)的算法，N是棋盘格的数目，k是一个小的常数。可视化：
假设搜索到的节点下面有8个合法的位置，然后就要先把下面的每个位置往深了使劲找完以后再才能再回到当前节点。然后进行新的节点的搜索。即使这个节点时错误的，算法也会忠实的搜索完。
启发式搜索：
直观地说，就是下一步选择有最少可能移动位置的顶点。
比如：
不用启发式：顶点a下面的点有b1，b2，b3，b4.按理说，就是从a挨个向下探索，a到b1，再到下下层的c1...
用启发式：先判断b1，b2，b3，b4下面有几个相邻节点，把具有相邻节点数目最小的比如b3，排在第一位。下次a就会先从b3搜索。
假设选择有最多可能移动位置的节点作为下一个顶点的问题在于骑士将倾向于在周游的早期访问棋盘中间的方格。当这样的事情发生的时候，骑士将容易被困在棋盘的一边而不能到达棋盘另一边未被访问的方格。
另一方面，首先去访问最少可能的格子会迫使骑士早早的进入边角的格子。 进而保证骑士早早访问那些不容易到达的角落，并且在需要的时候通过中间的方格跳跃着穿过棋盘。利用这种先验的知识来改进算法性能的做法，称作为“启发式规则”。
人类每天应用启发式规则来做决定，启发式搜索经常被用在人工智能领域。这个启发式规则算法以 H. C. Warnsdorff 的名字来命名，被叫做 Warnsdorff 算法，他在1823 年发表了自己的想法。
3.3 通用深度优先搜索
上述的DFS只建立了一个深度最深的树。
在深度优先搜索中建立不止一个树，也是有可能的。（为什么要建立不止一个树，比如下面的拓扑排序题，想要知道不同的树，以及不同树需要的时间，这就是通用DFS的用处了。）
对于通用深度优先搜索算法的理解参考教材，其中开头标题的注释也讲的比较明白了。不过，此算法的应用不是很理解，比如拓扑排序用此算法以后顶点确实能成线性了，但还是不知道怎么制作香饼。。
四、BFS与DFS的不同
4.1、直观上的不同
4.1.1、BFS==> 搜完一层，才搜下一层
BFS是先搜索完一层的所有点，再搜索下一层。被搜索完第k层的节点，绝对不会再次被搜索到，因为这些节点的所有可能已经被搜索完了。
想想的话，就是，既然目标是找最短的路径，那么我就干脆一层一层的找，最短的路径肯定是层数最少的，这种方法是可以的。
4.1.2、DFS==> 每搜一个节点，就是当前节点的下一层
DFS是每次搜索一层的一个点，然后搜下一层的一个点。即，先从根节点s使劲往下探索，探索到最深处再回来探索另一条路径。
想想的话，就是既然目标是找最长的路径，那最长的路径肯定是需要一路往下找的。所以每次就一个点一个点的往下搜索。
理论上说，如果我用BFS，每次搜索完一一层，以最长的路径目标，也是可以的。
4.2、所用的数据结构不同
4.2.1、BFS ==> 队列
BFS所用的是队列，每次新搜索一个点，就添加到队尾，按照上面所说，因为是一层搜完才会搜下一层。所以搜索完这个点，就不会再对这个点进行搜索了。所以直接从队列中删掉就行。
4.2.2、DFS ==> 栈
DFS用的是栈，按照上面所说，因为是搜了k层的点a，再搜k+1层的点b，再 搜k+2层的点c。搜到c时，当前点标记为b，搜完c若返回false，那么就会回来从b再向下别的方向进行搜索。也就是说，搜索了这个点，还可能回来再搜这个点向下的别的方向。
因为会回溯，所以要用栈，将搜索的点压入栈中，若返回false就pop出这个点，然后再搜索栈顶的点的别的方向。
4.3、对节点的追踪方式不同（标注颜色方式不同）
4.3.1、BFS ==> 三种颜色，白，灰，黑
上面也已经说过，BFS搜索完一个点，这个点就不会被再次搜索了。
一个节点未被搜索前，是白色。
已经被搜索，标记为灰色。（注意，搜索的目标--是--当前节点的下一层的节点）。
这个节点的下一层节点搜索完了，那么此时，当前节点标记为黑色表示不会再被搜索，当前节点的下一层节点标记为灰色。
4.3.2、DFS ==> 两种颜色，白，灰
DFS中，已经被搜索的点，还可能会被用到（代码中的三行解释）
节点被搜索前，是白色。
节点正在被搜索标记为灰色。（注意，搜索的目标--是--当前节点的不断往下层前进的节点）
节点被搜索完以后，路径是false ，节点从灰色再次标记为白色。说明在新的路径中，此节点未被搜索到。
