<p>我提出了两个选择,但没有一个能够及时解决案例2。第一个选项是使用带有字符串距离度量的*作为h(n),第二个选项是IDA*。我测试了许多字符串相似性度量,在我的方法中使用了smith waterman。我已更改了您的符号,以便更快地处理这个问题。我在每个数字的末尾添加了数字,以检查一个工件是否移动了两次</p>
<p>以下是我测试过的案例:</p>
<pre><code>start = [
['R1', 'R2', 'R3', 'R4'],
['Y1', 'Y2', 'Y3', 'Y4'],
['G1', 'G2', 'G3', 'G4'],
['B1'],
['B2', 'B3', 'B4']
]
case_easy = [
['R', 'R', 'R', 'R'],
['Y', 'Y', 'Y', 'Y'],
['G', 'G', 'G'],
['B', 'B'],
['B', 'B', 'G']
]
case_medium = [
['R', 'R', 'R', 'R'],
['Y', 'Y', 'Y', 'B'],
['G', 'G', 'G'],
['B'],
['B', 'B', 'G', 'Y']
]
case_medium2 = [
['R', 'R', 'R' ],
['Y', 'Y', 'Y', 'B'],
['G', 'G' ],
['B', 'R', 'G'],
['B', 'B', 'G', 'Y']
]
case_hard = [
['B'],
['Y', 'Y', 'Y', 'Y'],
['G', 'G', 'G', 'G'],
['R','R','R', 'R'],
['B','B', 'B']
]
</code></pre>
<p>以下是A*代码:</p>
<pre><code>from copy import deepcopy
from heapq import *
import time, sys
import textdistance
import os
def a_star(b, goal, h):
print("A*")
start_time = time.time()
heap = [(-1, b)]
bib = {}
bib[b.stringify()] = b
while len(heap) > 0:
node = heappop(heap)[1]
if node == goal:
print("Number of explored states: {}".format(len(bib)))
elapsed_time = time.time() - start_time
print("Execution time {}".format(elapsed_time))
return rebuild_path(node)
valid_moves = node.get_valid_moves()
children = node.get_children(valid_moves)
for m in children:
key = m.stringify()
if key not in bib.keys():
h_n = h(key, goal.stringify())
heappush(heap, (m.g + h_n, m))
bib[key] = m
elapsed_time = time.time() - start_time
print("Execution time {}".format(elapsed_time))
print('No Solution')
</code></pre>
<p>以下是IDA*代码:</p>
<pre><code>#shows the moves done to solve the puzzle
def rebuild_path(state):
path = []
while state.parent != None:
path.insert(0, state)
state = state.parent
path.insert(0, state)
print("Number of steps to solve: {}".format(len(path) - 1))
print('Solution')
def ida_star(root, goal, h):
print("IDA*")
start_time = time.time()
bound = h(root.stringify(), goal.stringify())
path = [root]
solved = False
while not solved:
t = search(path, 0, bound, goal, h)
if type(t) == Board:
solved = True
elapsed_time = time.time() - start_time
print("Execution time {}".format(elapsed_time))
rebuild_path(t)
return t
bound = t
def search(path, g, bound, goal, h):
node = path[-1]
time.sleep(0.005)
f = g + h(node.stringify(), goal.stringify())
if f > bound: return f
if node == goal:
return node
min_cost = float('inf')
heap = []
valid_moves = node.get_valid_moves()
children = node.get_children(valid_moves)
for m in children:
if m not in path:
heappush(heap, (m.g + h(m.stringify(), goal.stringify()), m))
while len(heap) > 0:
path.append(heappop(heap)[1])
t = search(path, g + 1, bound, goal, h)
if type(t) == Board: return t
elif t < min_cost: min_cost = t
path.pop()
return min_cost
class Board:
def __init__(self, board, parent=None, g=0, last_moved_piece=''):
self.board = board
self.capacity = len(board[0])
self.g = g
self.parent = parent
self.piece = last_moved_piece
def __lt__(self, b):
return self.g < b.g
def __call__(self):
return self.stringify()
def __eq__(self, b):
if self is None or b is None: return False
return self.stringify() == b.stringify()
def __repr__(self):
return '\n'.join([' '.join([j[0] for j in i]) for i in self.board])+'\n\n'
def stringify(self):
b=''
for i in self.board:
a = ''.join([j[0] for j in i])
b += a + '-' * (self.capacity-len(a))
return b
def get_valid_moves(self):
pos = []
for i in range(len(self.board)):
if len(self.board[i]) < self.capacity:
pos.append(i)
return pos
def get_children(self, moves):
children = []
for i in range(len(self.board)):
for j in moves:
if i != j and self.board[i][-1] != self.piece:
a = deepcopy(self.board)
piece = a[i].pop()
a[j].append(piece)
children.append(Board(a, self, self.g+1, piece))
return children
</code></pre>
<p>用法:</p>
<pre><code>initial = Board(start)
final1 = Board(case_easy)
final2 = Board(case_medium)
final2a = Board(case_medium2)
final3 = Board(case_hard)
x = textdistance.gotoh.distance
a_star(initial, final1, x)
a_star(initial, final2, x)
a_star(initial, final2a, x)
ida_star(initial, final1, x)
ida_star(initial, final2, x)
ida_star(initial, final2a, x)
</code></pre>