我用 Python 开发了自己的程序来解决 8 个谜题。最初，我使用“盲目”或不知情的搜索（基本上是暴力破解）生成和探索所有可能的继任者，并使用广度优先搜索。当它找到“目标”状态时，它基本上会回到初始状态并提供（我相信）是解决它的最优化步骤。当然，在某些初始状态下，搜索会花费大量时间并在找到目标之前生成超过 100,000 个状态。
然后我添加了启发式 - 曼哈顿距离。解决方案开始呈指数级增长，并且探索的状态要少得多。但我的困惑是，在某些时候，生成的优化序列比使用盲目或不知情的搜索所达到的要长。
我正在做的基本上是这样的：
- 对于每个状态，查找所有可能的移动（上、下、左和右），并生成后续状态。
- 检查状态是否重复。如果是，则忽略它。
- 计算该州的曼哈顿。
- 挑选出曼哈顿最低的继任者并添加到列表的末尾。
- 检查目标状态。如果是，则打破循环。
我不确定这是否符合贪婪优先或 A* 的条件。
我的问题是，这是曼哈顿距离启发式的固有缺陷，有时它不会给出最佳解决方案，或者我做错了什么。
下面是代码。我很抱歉这不是一个非常干净的代码，但主要是顺序的，应该很容易理解。我也为长代码道歉 - 我知道我需要优化它。也将不胜感激任何清理代码的建议/指导。这是什么：
import numpy as np
from copy import deepcopy
import sys
# calculate Manhattan distance for each digit as per goal
def mhd(s, g):
m = abs(s // 3 - g // 3) + abs(s % 3 - g % 3)
return sum(m[1:])
# assign each digit the coordinate to calculate Manhattan distance
def coor(s):
c = np.array(range(9))
for x, y in enumerate(s):
c[y] = x
return c
#################################################
def main():
goal = np.array( [1, 2, 3, 4, 5, 6, 7, 8, 0] )
rel = np.array([-1])
mov = np.array([' '])
string = '102468735'
inf = 'B'
pos = 0
yes = 0
goalc = coor(goal)
puzzle = np.array([int(k) for k in string]).reshape(1, 9)
rnk = np.array([mhd(coor(puzzle[0]), goalc)])
while True:
loc = np.where(puzzle[pos] == 0) # locate '0' (blank) on the board
loc = int(loc[0])
child = np.array([], int).reshape(-1, 9)
cmove = []
crank = []
# generate successors on possible moves - new states no repeats
if loc > 2: # if 'up' move is possible
succ = deepcopy(puzzle[pos])
succ[loc], succ[loc - 3] = succ[loc - 3], succ[loc]
if ~(np.all(puzzle == succ, 1)).any(): # repeat state?
child = np.append(child, [succ], 0)
cmove.append('up')
crank.append(mhd(coor(succ), goalc)) # manhattan distance
if loc < 6: # if 'down' move is possible
succ = deepcopy(puzzle[pos])
succ[loc], succ[loc + 3] = succ[loc + 3], succ[loc]
if ~(np.all(puzzle == succ, 1)).any(): # repeat state?
child = np.append(child, [succ], 0)
cmove.append('down')
crank.append(mhd(coor(succ), goalc))
if loc % 3 != 0: # if 'left' move is possible
succ = deepcopy(puzzle[pos])
succ[loc], succ[loc - 1] = succ[loc - 1], succ[loc]
if ~(np.all(puzzle == succ, 1)).any(): # repeat state?
child = np.append(child, [succ], 0)
cmove.append('left')
crank.append(mhd(coor(succ), goalc))
if loc % 3 != 2: # if 'right' move is possible
succ = deepcopy(puzzle[pos])
succ[loc], succ[loc + 1] = succ[loc + 1], succ[loc]
if ~(np.all(puzzle == succ, 1)).any(): # repeat state?
child = np.append(child, [succ], 0)
cmove.append('right')
crank.append(mhd(coor(succ), goalc))
for s in range(len(child)):
if (inf in 'Ii' and crank[s] == min(crank)) \
or (inf in 'Bb'):
puzzle = np.append(puzzle, [child[s]], 0)
rel = np.append(rel, pos)
mov = np.append(mov, cmove[s])
rnk = np.append(rnk, crank[s])
if np.array_equal(child[s], goal):
print()
print('Goal achieved!. Successors generated:', len(puzzle) - 1)
yes = 1
break
if yes == 1:
break
pos += 1
# generate optimized steps by back-tracking the steps to the initial state
optimal = np.array([], int).reshape(-1, 9)
last = len(puzzle) - 1
optmov = []
rank = []
while last != -1:
optimal = np.insert(optimal, 0, puzzle[last], 0)
optmov.insert(0, mov[last])
rank.insert(0, rnk[last])
last = int(rel[last])
# show optimized steps
optimal = optimal.reshape(-1, 3, 3)
print('Total optimized steps:', len(optimal) - 1)
print()
for s in range(len(optimal)):
print('Move:', optmov[s])
print(optimal[s])
print('Manhattan Distance:', rank[s])
print()
print()
################################################################
# Main Program
if __name__ == '__main__':
main()
如果您想检查，这里有一些初始状态和计算的优化步骤（上面的代码将提供此选项以在盲搜索与知情搜索之间进行选择）
初始状态
- 283164507 盲人：19 曼哈顿：21
- 243780615 盲人：15 曼哈顿：21
- 102468735 盲人：11 曼哈顿：17
- 481520763 盲人：13 曼哈顿：23
- 723156480 盲人：16 曼哈顿：20
我特意选择了结果很快（几秒钟或几分钟内）的例子。
您的帮助和指导将不胜感激。
编辑：我做了一些快速更改并设法减少了大约 30 多行。不幸的是，此时不能做太多事情。
注意：我已经硬编码了初始状态和盲目与知情选择。请更改初始状态的变量“string”的值和 Informed/Blind 的变量“inf”[I/B] 的值。谢谢！