需要用到上一节中定义的Graph类，直接复制：
## 将代码块运行结果全部输出，而不是只输出最后的，适用于全文
from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"
class Vertex:
def __init__(self, key):
self.id = key # 用id保存key
self.connectedTo = {} # 字典保存，非常类似昨天10.14写的ID3里对于多叉数的节点定义
self.distance = None
self.pred = None
self.color = "white"
def addNeighbor(self, nbr, weight = 0): # nbr——链接的对象的key
self.connectedTo[nbr]=weight # 加入connection里，并赋边的权重
def __str__(self):
return str(self.id) +' connectedTo: ' +str([x.id for x in self.connectedTo])
def getId(self): # 获得id
return self.id
def getConnections(self): # 该顶点链接的所有顶点的key
return self.connectedTo.keys()
def getWeight(self,nbr): # 查看两个顶点的边权重
return self.connectedTo[nbr] # 字典按照key索引
##### 增加部分 ######
def setDistance(self, x): # 设置距离
self.distance = x
def setPred(self, x): # 设置前驱顶点
self.pred = x
def setColor(self, x): # 设置颜色标识
self.color = x
class Graph: # 维护一个masterlist
def __init__(self):
self.vertList = {} # 存储所有顶点，是一个字典key:vertex
self.numVertices = 0 # 顶点数量
def addVertex(self,key): # 添加顶点
newVertex = Vertex(key) # 变成顶点形式
self.vertList[key] = newVertex # 加入masterlist字典
self.numVertices +=1
#print(newVertex)
def getVertex(self,item): # 按照key从master里查找一个顶点
if item in self.vertList:
return self.vertList[item]
else:
return None
def __contain__(self,item): # 是否包含某个key
return item in self.vertList
def addEdge(self, f, t, cost=0): # 添加边 f 到 t（key），cost是边的权重
# 如果给出的f和t在masterlist里面找不到
if f not in self.vertList:
nv = self.addVertex(f)
if t not in self.vertList:
nv = self.addVertex(t)
self.vertList[f].addNeighbor(self.vertList[t], cost) # 调用vertex类里定义联系的方法
#print(self.vertList[f])
def getVertices(self): # 输出所有顶点key
return self.vertList.keys()
def __iter__(self):
return iter(self.vertList.values()) # 可迭代 所有vertex
图——骑士周游问题
马从一个格子开始，按照“马走日”的规则，把棋盘中所有格子都走一遍（不重复）
“马走日”规则：
- 每步棋先横走或直走一格，然后再往外斜走一格；
- 或者先斜走一格，最后再往外横走或竖走一格
问题处理——构建图
思路：
- 把棋盘格作为图的顶点
- 把“马走日”这个规则的走棋步骤作为连接边
- 每一次最多有8个格子可以走
生成合法走棋位置：
genLegalMoves
- 输入：当前位置
- 输出：当前位置上骑士所有合法移动的列表
def genLegalMoves(x,y,bdSize):
newMoves = []
moveOffsets = [(-1,-2),(-1,2),(-2,-1),(-2,1),( 1,-2),( 1,2),( 2,-1),( 2,1)]
for i in moveOffsets: # 按照规则所有走法
newX = x + i[0] # 走到的位置
newY = y + i[1]
if legalCoord(newX,bdSize) and legalCoord(newY,bdSize): # 没有走出棋盘
newMoves.append((newX,newY)) # 生成合法的移动新位置
return newMoves
def legalCoord(x,bdSize):
if x >= 0 and x < bdSize:
return True
else:
return False
genLegalMoves(0, 0, 8)
genLegalMoves(3, 3, 8)
[(1, 2), (2, 1)]
[(2, 1), (2, 5), (1, 2), (1, 4), (4, 1), (4, 5), (5, 2), (5, 4)]
走棋关系图
# 给顶点的id，没有重复
def NodeID(row, col, bdsize):
return row*bdsize + col
def revNodeID(nodeid, bdsize): # 根据node id 计算棋盘上的位置
x = nodeid//bdsize
y = nodeid%bdsize
return (x,y)
# 生成图
def knightGraph(bdsize=8):
ktGraph = Graph()
for row in range(bdsize):
for col in range(bdsize): # 遍历每个格子
nodeid = NodeID(row, col, bdsize) # 生成id
new_xy = genLegalMoves(row, col, bdsize) # 计算合法移动位置
for position in new_xy: # 对每个合法移动的位置
nid = NodeID(position[0], position[1], bdsize) # 生成id
ktGraph.addEdge(nodeid, nid) # add函数建边，没有顶点就先建立顶点再建边
return ktGraph
knightG = knightGraph(8)
length = 0
for key in knightG.getVertices():
length += len(knightG.getVertex(key).connectedTo)
print("一共%d个顶点，%d条边\n"% (knightG.numVertices, length))
# 与(0,0) （3,3）两个顶点有边相连的顶点
print(knightG.getVertex(NodeID(0, 0 ,8)))
print(knightG.getVertex(NodeID(3, 3, 8)))
[revNodeID(x.id, 8) for x in knightG.getVertex(NodeID(0, 0 ,8)).connectedTo] # 2个（2个可走位置）
[revNodeID(x.id, 8) for x in knightG.getVertex(NodeID(3, 3 ,8)).connectedTo]# 8个（8个可走位置）
一共64个顶点，336条边
0 connectedTo: [10, 17]
27 connectedTo: [17, 21, 10, 12, 33, 37, 42, 44]
[(1, 2), (2, 1)]
[(2, 1), (2, 5), (1, 2), (1, 4), (4, 1), (4, 5), (5, 2), (5, 4)]
深度优先搜索 DFS
Depth First Search
- 沿着树的单支尽量深入，
- 直到无法继续还没有找到解时
- 回溯到上一层，搜索下一支
实现的算法：
- 第一种，每个顶点仅访问一次
- 第二种，允许顶点被重复访问
用于解决骑士周游问题
-
思路：
-
假定每个顶点只能被访问一次
-
沿着单支深入，直到：还没有走到63步（还没完成周游时），已经出现“当前位置的所有合法移动位置都被走过了”
-
那就清除当前位置标记，返回上一层换一个分支搜索
-
-
根据这个思路可以发现，访问路径可以用栈来处理：
- 引入一个栈记录路径
-
整个算法用递归完成：
访问一个节点——标记、对所有合法位置递归、如果都失败则清楚当前节点标记，并返回上一步
def knightTour(position, path, depth, limit):
position.setColor('grey') # 走过了就记作灰色，避免重复
path.append(position) # 纳入路径中
if depth==limit: # 结束条件
available = True
else:
available = False
new_xy = list(position.getConnections()) # 下一步走棋位置
i = 0
# 对于所有合法且没有走过的解法，递归调用
while i < len(new_xy) and not available:
if new_xy[i].color =="white": # 如果没走过
available,path = knightTour(new_xy[i], path, depth+1, limit)
i += 1
if not available: # 循环结束，如果没有找到
path.pop() # 返回上一步
position.setColor("white") # 当做没来过
return available, path
knightG = knightGraph(5)
available, path = knightTour(knightG.getVertex(NodeID(2, 2 ,5)), [], 0, 24)
path = [str(revNodeID(x.id, 5)) for x in path]
print("5x5的棋盘上骑士周游的一条路径：\n"+ ' -> '.join(path))
5x5的棋盘上骑士周游的一条路径：
(2, 2) -> (1, 0) -> (0, 2) -> (1, 4) -> (3, 3) -> (4, 1) -> (2, 0) -> (0, 1) -> (1, 3) -> (3, 4) -> (4, 2) -> (3, 0) -> (1, 1) -> (0, 3) -> (2, 4) -> (4, 3) -> (3, 1) -> (2, 3) -> (0, 4) -> (1, 2) -> (0, 0) -> (2, 1) -> (4, 0) -> (3, 2) -> (4, 4)
改进算法
骑士周游问题的改进算法——在进行对于所有合法移动位置new_xy，按照新位置的合法移动位置数目来决定搜索顺序。
- 下一步选择有最少可能移动位置的顶点！！
### 1.首先定义函数——把下一步的合法移动位置按照其包含的合法移动位置排序：
def orderByAvail(n):
nextlist = []
for i in n.getConnections():
if i.color =="white":
count = 0
for j in i.getConnections(): # 计算新的顶点有多少可能的移动位置
if j.color=="white":
count+=1
nextlist.append((count,i))
# 按照可能移动位置排序，由小到大
nextlist.sort(key = lambda x: x[0])
# 输出排序后的节点列表
return [x[1] for x in nextlist]
# 测试
knightG = knightGraph(8)
orderByAvail( knightG.getVertex(NodeID(4, 4 ,8)))
### 2.修改原本的算法
def knightTour(position, path, depth, limit):
position.setColor('grey') # 走过了就记作灰色，避免重复
path.append(position) # 纳入路径中
if depth==limit: # 结束条件
available = True
else:
available = False
new_xy = orderByAvail(position) # 【修改位置】
i = 0
# 对于所有合法且没有走过的解法，递归调用
while i < len(new_xy) and not available:
if new_xy[i].color =="white": # 如果没走过
available,path = knightTour(new_xy[i], path, depth+1, limit)
i += 1
if not available: # 循环结束，如果没有找到
path.pop() # 返回上一步
position.setColor("white") # 当做没来过
return available, path
[<__main__.Vertex at 0x10a0f9198>,
<__main__.Vertex at 0x10a0f9518>,
<__main__.Vertex at 0x10a0f9630>,
<__main__.Vertex at 0x10a0f96a0>,
<__main__.Vertex at 0x10a0f90b8>,
<__main__.Vertex at 0x10a0f7cf8>,
<__main__.Vertex at 0x10a0f7e80>,
<__main__.Vertex at 0x10a0f9438>]
knightG = knightGraph(8)
available, path = knightTour(knightG.getVertex(NodeID(2, 6 ,8)), [], 0, 63)
path = [str(revNodeID(x.id, 8)) for x in path]
print("8x8的棋盘上骑士周游的一条路径：\n"+ ' -> '.join(path))
8x8的棋盘上骑士周游的一条路径：
(2, 6) -> (0, 7) -> (1, 5) -> (0, 3) -> (1, 1) -> (3, 0) -> (5, 1) -> (7, 0) -> (6, 2) -> (5, 0) -> (7, 1) -> (6, 3) -> (7, 5) -> (6, 7) -> (4, 6) -> (2, 7) -> (0, 6) -> (1, 4) -> (0, 2) -> (1, 0) -> (2, 2) -> (0, 1) -> (2, 0) -> (4, 1) -> (6, 0) -> (7, 2) -> (6, 4) -> (7, 6) -> (5, 7) -> (3, 6) -> (1, 7) -> (0, 5) -> (1, 3) -> (3, 4) -> (5, 5) -> (4, 7) -> (6, 6) -> (7, 4) -> (5, 3) -> (4, 5) -> (3, 7) -> (2, 5) -> (0, 4) -> (1, 6) -> (2, 4) -> (3, 2) -> (4, 0) -> (6, 1) -> (4, 2) -> (2, 1) -> (0, 0) -> (1, 2) -> (3, 3) -> (5, 4) -> (7, 3) -> (6, 5) -> (7, 7) -> (5, 6) -> (4, 4) -> (5, 2) -> (3, 1) -> (2, 3) -> (3, 5) -> (4, 3)
-
小感受
我的天这个效率提升也太快了，原因就是因为充分利用了先验知识，通常要棋盘边上走，选择有最多可能移动位置的节点作为下一个顶点，会导致问题骑士将倾向于在周游的早期访问棋盘中间的方格，因为不能重复走，最后没法完成周游 -
list排序的新知识：
- key = lambda 元素: 元素[字段索引]
nextlist.append((count,i))
nextlist.sort(key = lambda x: x[0]) # 按照某一维排序
return [x[1] for x in nextlist] # 只输出某一维
a = [(1,4,3),(6,2,4),(5,9,1)] # 当然这里是圆括号还是方括号都可以
a.sort(key = lambda x :x[0]); [x[0] for x in a]
a.sort(key = lambda x :x[1]); [x[1] for x in a]
a.sort(key = lambda x :x[2]); [x[2] for x in a]
[1, 5, 6]
[2, 4, 9]
[1, 3, 4]