写在前面的话骑士问题与第四节八皇后问题一样，是国际象棋里面的著名猜想之一，也是很多算法课的必讲内容，当然，自然也是很多大厂的经典笔试算法题之一。 问题是这样的： 国际象棋里面的骑士（Knights），是一种曲线攻击的兵种，类似于中国象棋里面的马（走日字，但是国际象棋里面的马没有蹩马腿一说）： 
从上图可以看见，一个骑士能够攻击到的位置一共是8个，所以中国象棋里面常有“马有八面威风”一说，套用到国际象棋里面，也是一样的。 整个棋盘一共有8*8 = 64个位置，问最少需要多少个骑士，且如何摆放，才能够攻击到整个棋盘所有位置？ 看起来，似乎是一个很简单的计算题——共计64个格子，一个骑士控制8个格子，那不就是8个骑士就可以攻击到所有的位置了么？ 答案当然是否定的，因为骑士的特性，越往棋盘边上靠，控制的区域就会越少，所以无论如何，8个骑士都是无法控制全盘的。比如下面是就一种的摆放方式： 
总共用了14个骑士，才控制住了全场，我们随便挑选任意位置，都最少有一个骑士可以攻击得到： 
类似于八皇后问题，现在我们需要通过算法，来计算一下，是否还有其他的摆放方法？ 算法实现部分首先，定义个骑士当前所在的位置的类，就两个属性，X和Y，三个内部函数，分别用于打印、比较和hash。 什么是hash，请看第五节图着色问题，或者自行上网搜索。
class Position:
def __init__(self, x, y):
self.X = x
self.Y = y
def __str__(self):
return "{},{}".format(self.X, self.Y)
def __eq__(self, other):
return self.X == other.X and self.Y == other.Y
def __hash__(self):
return self.X * 1000 + self.Y
然后定义一个棋盘类：通过输入棋盘的高低，来构造成一个棋盘，然后通过输入的上面的Position（骑士位置）类，来构造骑士在棋盘上的位置。print函数用于输出。 class Board:
def __init__(self, positions, width, height):
board = [['.'] * width for _ in range(height)]
for index in range(len(positions)):
knightPosition = positions[index]
board[knightPosition.Y][knightPosition.X] = 'N'
self._board = board
self._width = width
self._height = height
def print(self):
# 0,0 prints in bottom left corner
for i in reversed(range(self._height)):
print(i, "\t", ' '.join(self._board[i]))
print(" \t", ' '.join(map(str, range(self._width))))
然后是计算当前能够攻击到该点的骑士的位置方法： def get_attacks(location, boardWidth, boardHeight):
return [i for i in set(
Position(x + location.X, y + location.Y)
for x in [-2, -1, 1, 2] if 0 <= x + location.X < boardWidth
for y in [-2, -1, 1, 2] if 0 <= y + location.Y < boardHeight
and abs(y) != abs(x))]
我们可以测试一下这个攻击方法：试试要攻击最左下角这个点，骑士需要摆放在哪个位置： n = get_attacks(Position(0,0),8,8)
Board(n,8,8).print()
运行结果： 7 . . . . . . . .
6 . . . . . . . .
5 . . . . . . . .
4 . . . . . . . .
3 . . . . . . . .
2 . N . . . . . .
1 . . N . . . . .
0 . . . . . . . .
0 1 2 3 4 5 6 7
可以看见，在0,0这个点，只有两个位置上的骑士可以攻击得到 又或者是我们看看棋盘中间的点，比如第三列，第四行： n = get_attacks(Position(3,4),8,8)
Board(n,8,8).print()
运行结果有8个位置的骑士，都可以攻击到这个点。 7 . . . . . . . .
6 . . N . N . . .
5 . N . . . N . .
4 . . . . . . . .
3 . N . . . N . .
2 . . N . N . . .
1 . . . . . . . .
0 . . . . . . . .
0 1 2 3 4 5 6 7
接下去就是核心的健壮性检验函数了：该函数的设计很简单，直接用随机构造出来的骑士的位置，来计算棋盘上面有多少个点被攻击到，如果是重复的，则不计数。可以看到，如果被攻击的位置等于64，则表示覆盖了整个棋盘。 def get_fitness(genes, boardWidth, boardHeight):
attacked = set(pos
for kn in genes
for pos in get_attacks(kn, boardWidth, boardHeight))
return len(attacked)
打印函数，主要是输出棋盘和骑士所在的位置 def display(candidate, startTime, boardWidth, boardHeight):
timeDiff = datetime.datetime.now() - startTime
board = Board(candidate.Genes, boardWidth, boardHeight)
board.print()
print("{}\n\t{}\t{}".format(
' '.join(map(str, candidate.Genes)),
candidate.Fitness,
timeDiff))
关键函数：进化变异函数 这应该是到目前以来，最复杂的进化变异函数了，具体的代码说明见里面注释 def mutate(genes, boardWidth, boardHeight, allPositions, nonEdgePositions):
#随机交换8-10组基因，这个值也可以修改，一般来说，别太多，否则慢。
for i in range(random.randint(8,10)):
#构建一个由棋盘上所有的点所组成的字典
positionToKnightIndexes = dict((p, []) for p in allPositions)
#从种群的基因库中查看骑士的位置
# 然后把这些骑士能够攻击到的点，都加入到上面那个字典里面
# 结构是{点1:[骑士1的索引,骑士2的索引]……}
for i, knight in enumerate(genes):
for position in get_attacks(knight, boardWidth, boardHeight):
positionToKnightIndexes[position].append(i)
knightIndexes = set(i for i in range(len(genes)))
print(knightIndexes)
unattacked = []
#下面对每个点进行进行迭代
# 如果某个点没有任何一个骑士可以攻击到的话，把这个点记录下面
# 如果某个点，只有一个骑士可以攻击到，那个这个骑士的位置就太浪费
# 会把这个骑士先移除掉，设定为需要重新放位的
for kvp in positionToKnightIndexes.items():
if len(kvp[1]) > 1:
continue
if len(kvp[1]) == 0:
unattacked.append(kvp[0])
continue
for p in kvp[1]: # len == 1
if p in knightIndexes:
knightIndexes.remove(p)
# 对于完全没有被攻击到的点，进行一次计算，计算出可以攻击到他们的位置
# 也就是潜在的要被攻击的点。
# 而且这些潜在的点，需要是非边界上的点。
# 如果未被攻击到的点小于等于0了，那么需要计算的潜在点，就是非边界点。
potentialKnightPositions = \
[p for positions in
map(lambda x: get_attacks(x, boardWidth, boardHeight),
unattacked)
for p in positions if p in nonEdgePositions] \
if len(unattacked) > 0 else nonEdgePositions
#选择需要替换的基因库里面的基因
geneIndex = random.randrange(0, len(genes)) \
if len(knightIndexes) == 0 \
else random.choice([i for i in knightIndexes])
# 在前致电里面，选择一个位置，设置为新的骑士的位置
position = random.choice(potentialKnightPositions)
genes[geneIndex] = position
return Chromosome(genes, get_fitness(genes,boardWidth, boardHeight))
下面的两个方法，是用来创建初始化骑士位置的……当然，你可以可以简单的用个随机函数来生成： 遗传算法的一个特点就是，不会在乎起始的情况是怎么样的。
def fnGetRandomPosition():
return random.choice(nonEdgePositions)
def create(fnGetRandomPosition, expectedKnights):
genes = [fnGetRandomPosition() for _ in range(expectedKnights)]
return genes
传统方法，种群类，用来记录种群基因和健壮性。 class Chromosome:
def __init__(self, genes, fitness):
self.Genes = genes
self.Fitness = fitness
设置棋盘大小和骑士的数量 这里默认的骑士数量是14个，这是能够全面控制棋盘的最少的骑士数量
初始化了两个位置集合，一个是全棋盘64个点的位置集合，一个是非边框的位置集合。 boardHeight = 8
boardWidth = 8
expectedKnights = 14
allPositions = [Position(x, y)
for y in range(boardHeight)
for x in range(boardWidth)]
nonEdgePositions = [i for i in allPositions
if 0 < i.X < boardWidth - 1 and
0 < i.Y < boardHeight - 1]
执行方法 def get_best():
startTime = datetime.datetime.now()
optimalFitness = boardWidth * boardHeight
geneset = create(fnGetRandomPosition,expectedKnights)
best = Chromosome(geneset, get_fitness(geneset,boardHeight,boardWidth))
if best.Fitness == optimalFitness:
return best
num = 0
while True:
child = mutate(best.Genes, boardWidth, boardHeight,
allPositions, nonEdgePositions)
num +=1
if best.Fitness > child.Fitness:
continue
#display(child,startTime, boardWidth, boardHeight)
if not child.Fitness > best.Fitness:
best = child
if child.Fitness == optimalFitness:
break
best = child
return (best,num)
执行过程如下： 7 . . . . . . . .
6 . . . . . N N .
5 . . N . N . . .
4 . . . N . . . .
3 . . . N . N . .
2 . . N . N . N .
1 . N N . N . . .
0 . . . . . . . .
0 1 2 3 4 5 6 7
3,4 1,1 4,5 6,6 4,2 1,1 2,2 4,1 6,2 2,5 3,3 5,6 2,1 5,3
51 0:00:00.000998
# ……中间过程略
7 . . . . . . . .
6 . . N . N . . .
5 . . N . N . N .
4 . . N . . . N .
3 . . N . . . N .
2 . . N . N . N .
1 . . N . N . . .
0 . . . . . . . .
0 1 2 3 4 5 6 7
4,6 4,1 2,2 4,2 2,1 6,5 6,2 2,5 2,6 6,4 4,5 2,3 6,3 2,4
64 0:00:00.191378
初始化的时候，14个骑士，只能控制51个位置，迭代到230次之后，变成了最终的样子，总共控制了64个位置，进化结束。 进行100次迭代： 
本次迭代100次，平均549次进化，完成骑士问题布局。 当然，我们也可以修改棋盘大小和骑士的数量，来增加算法的难度，比如当棋盘扩大为10 * 10的时候，最少需要22个骑士才能控制全场：代码略，运行结果如下： 9 . . . . . . . . . .
8 . N . . N N N . . .
7 . N . N . . N . . .
6 . . . . . N . N . .
5 . . . . . . N . . .
4 . . . N N . . . . .
3 . . . . . N N . . .
2 . . . N . . N N . .
1 . . N . . . . . N .
0 . . . . . . . . . .
0 1 2 3 4 5 6 7 8 9
7,6 6,7 4,8 7,2 1,7 3,2 6,5 5,8 3,7 6,7 7,2 1,8 8,1 4,4 5,6 5,6 2,1 3,4 6,8 6,2 6,3 5,3
78 0:00:00.003988
# …… 中间过程略
9 . . . . . . . . . .
8 . . . . . . N . . .
7 . N N N N . . N N .
6 . . . . . . . N N .
5 . N N . . . N . . .
4 . . . . . . . . . .
3 . . . N N N N . . .
2 . . N N . . N N . .
1 . . N . . . . N . .
0 . . . . . . . . . .
0 1 2 3 4 5 6 7 8 9
6,5 2,1 5,3 8,6 6,2 4,3 3,2 2,7 7,7 2,5 2,2 4,7 3,7 8,7 7,6 6,8 1,7 7,2 3,3 1,5 6,3 7,1
100 0:00:01.400890
100个位置全部被控制，迭代完成。 结语骑士算法的解法，与扑克牌问题的解法一样，定义了一个比较复杂的进化算法，根据定义，也是一种模因进化算法。 模因作为一种广义的基因（把进化论思维扩展到了文化领域），让我们在进化的时候有更多是选择，而不仅仅是简单的通过随机算法模拟基因突变来进行进化。 通过在进化算法里面，控制基因的突变（主要是在一次突变中，就突变数次，这个次数可以固定，也可以通过随机数来控制，大家可以通过修改进化算法里面的第一行，for循环中的循环次数来测试），来加速进化，是模因算法的一个特点。 不过一般来说，不建议把求解的完整过程倚赖与进化方法，而应该结合健壮性检验函数和进化算法来联合实现……用遗传算法的专业说法就是：我们应该更多的发挥基因引擎的作用。
|
