看到问答区有个问题：
集装箱码头在堆场任务过程中（装船或提箱）存在翻箱任务，原因是由于要求的发箱顺序和码头堆放的次序不符合，如图所示，其中数字代表发箱顺序（数字越小越早发箱，可以有重复），S代表堆放的排数量（<=6），T代表堆放的高度上限（考虑堆场机任务业能力等因素，<=5），最小预翻箱问题就是，通过一系列的尽可能少的翻箱动作（如（2，2）→（4，4），（3，1）→（3，2）），把堆场倍位初始状态数字小的箱子都翻上来，避免实际任务（装船或提箱）时由于翻箱造成的任务效率损失。设计和实现最小预翻箱算法，完成如下问题：
1.基于启发式规则的A星算法用python实现（2），并输出和验证求解结果（翻箱步骤）（初始发箱顺序可随机生成），翻箱过程中不违背堆放的高度上限。
我试着解决了一下。A*算法本身没太多可说的，网上已经有很多的文章介绍。关键是确定合适的启发函数，这里我用了：
def _h(self):
length = len(self.stack.get_incorrect_containers())
adjustment = self.value / (self.stack.total_row * self.stack.max_height)
return length + 1 - adjustment
意思是如果某个翻箱动作能使错误摆放的箱子数最少，那么优先考虑该翻箱动作。如果所有可能的翻箱动作的错误箱子数相同，那么优先移动顺序最靠后的一个。
特别的，按照程序执行的结果，问题中的例子其实可以5步解决，不需要6步。
完整代码如下：
import operator
S = 4
T = 4
# 每一排箱子的发箱顺序
origin_stack = [[9, 1, 5, 0], [8, 0, 0, 0], [2, 11, 4, 0], [10, 7, 3, 6]]
# 代表堆场的类
class Stack(object):
def __init__(self, values, total_row, max_height):
# 所有箱子
self.containers = values
# 一共多少排
self.total_row = total_row
# 最大高度
self.max_height = max_height
# 当前各排实际高度
self.height = [max_height] * total_row
for i in range(total_row):
self.height[i] = -1
for j in range(max_height):
if values[i][j] != 0:
self.height[i] = j
# 取得某一排最上面一个箱子
def get_top_container(self, row):
if self.height[row] != -1:
return self.containers[row][self.height[row]]
else:
return None
# 修改某个位置箱子的发箱顺序
def set_container(self, position, value):
self.containers[position[0]][position[1]] = value
# 取得指定位置的箱子
def get_container(self, position):
return self.containers[position[0]][position[1]]
# 列举当前有哪些可移动步骤：只有最顶上的箱子可以被移动到其它有空位的排的顶上
def list_available_steps(self, close_steps):
available_steps = []
for i in range(self.total_row):
if self.height[i] < 0:
continue
for j in range(self.total_row):
if i != j and self.height[j] < self.max_height - 1:
cloned_stack = self.__copy__()
top_container = cloned_stack.get_top_container(i)
new_step = Step(top_container, (i, self.height[i]), (j, self.height[j] + 1), cloned_stack)
if new_step not in close_steps:
available_steps.append(new_step)
return available_steps
# 取得所有摆放位置不对的箱子
def get_incorrect_containers(self, row=-1):
if row == -1:
return self._get_incorrect_containers(range(self.total_row))
else:
return self._get_incorrect_containers(range(row, row + 1))
# 取得所有摆放位置不对的箱子：如果发箱顺序小的箱子位于发箱顺序大的箱子之下，那么认为这个发箱顺序小的箱子向上的所有箱子位置都不对
def _get_incorrect_containers(self, rows):
result = []
for i in rows:
for j in range(1, self.max_height):
if self.containers[i][j] > self.containers[i][j - 1]:
for k in range(j, self.max_height):
if self.containers[i][k] != 0:
result.append(self.containers[i][k])
break
return result
# 把箱子从move_from位置移动到move_to位置
def move(self, move_from, move_to):
self.set_container(move_to, self.get_container(move_from))
self.set_container(move_from, 0)
self.height[move_from[0]] -= 1
self.height[move_to[0]] += 1
# 打印当前堆场
def print(self):
for j in range(self.max_height):
for i in range(self.total_row):
print(str(self.containers[i][-j - 1]).rjust(4), end='\t')
print()
# 判断两个堆场是否相等：比较所有位置的箱子，如果所有箱子的发箱顺序一样，则相等
def __eq__(self, other):
return operator.eq(self.containers, other.containers)
# 深度复制堆场
def __copy__(self):
cloned_containers = [[None for i in range(self.max_height)] for j in range(self.total_row)]
for i in range(self.total_row):
for j in range(self.max_height):
cloned_containers[i][j] = self.containers[i][j]
return Stack(cloned_containers, self.total_row, self.max_height)
# 代表移动步骤的类
class Step(object):
def __init__(self, container, move_from, move_to, stack):
# 被移动的箱子
self.value = container
# 箱子移动前的位置
self.move_from = move_from
# 箱子移动后的位置
self.move_to = move_to
# 堆场
self.stack = stack
# 前一个步骤
self.parent = None
# 当前是第几步
self.order = 0
# 修改堆场状态，实际移动箱子
self.stack.move(self.move_from, self.move_to)
# 修改前一个步骤
def set_parent(self, parent):
self.parent = parent
self.order = parent.get_order() + 1
# 获得前一个步骤
def get_parent(self):
return self.parent
# 获得当前是第几步
def get_order(self):
return self.order
# 获得当前步骤执行后对应的堆场状态
def get_stack(self):
return self.stack
# 启发函数
def _h(self):
length = len(self.stack.get_incorrect_containers())
adjustment = self.value / (self.stack.total_row * self.stack.max_height)
return length - adjustment
# 计算从开始状态到当前实际多少步
def _g(self):
return self.order
# 估值函数
def f(self):
return self._g() + self._h()
# 判断两个步骤是否等价：如果对应的堆场状态完全一样，则两个步骤等价
def __eq__(self, other):
return operator.eq(self.stack, other.get_stack())
# tostring的输出格式
def __str__(self):
return f'({self.value}: {self.move_from} -> {self.move_to}, {self.order}, {self.f()})'
# 打印时的表现形式
def __repr__(self):
return self.__str__()
if __name__ == '__main__':
# 最初的堆场状态
origin = Stack(origin_stack, S, T)
origin.print()
open_steps = []
close_steps = []
# 将最初堆场的可用步骤加入open list
open_steps.extend(origin.list_available_steps(close_steps))
# 根据估值函数最小的原则找到移动的第一步
current_step = min(open_steps, key=lambda x: x.f())
# 第一步移动后的堆场状态
current_stack = current_step.get_stack()
# 如果移动后还是有摆放位置不对的箱子，则继续调整
while len(current_stack.get_incorrect_containers()) > 0:
available_steps = current_stack.list_available_steps(close_steps)
# A*算法的处理：注意步骤比较会按照Step类的__eq__方法，即比较步骤对应的堆场状态
for step in available_steps:
# 如果步骤在open list中，即open list中有其它步骤形成了与可用步骤相同的堆场状态
if step in open_steps:
open_step = open_steps[open_steps.index(step)]
# 与open list中等价步骤的order进行比较，如果原有步骤的order比可用步骤大，则删除原有的步骤, 否则跳过可用步骤
if open_step.get_order() > step.get_order():
open_steps.remove(open_step)
else:
continue
# 将可用步骤链接到当前步骤之后，然后加入open list
step.set_parent(current_step)
open_steps.append(step)
# 当前步骤被从open list移动到close list
open_steps.remove(current_step)
close_steps.append(current_step)
# 如果已经没有可用的步骤了，输出无法完成，结束程序
if len(open_steps) == 0:
print("It can't be done.")
exit(0)
# 根据估值函数最小的原则找到移动的下一步
current_step = min(open_steps, key=lambda x: x.f())
current_stack = current_step.get_stack()
# 如果正确退出循环，说明找到了移动方法，倒序打印所有步骤
actual_steps = [current_step]
while current_step.get_parent() is not None:
actual_steps.append(current_step.get_parent())
current_step = current_step.get_parent()
for step in reversed(actual_steps):
print(step)
step.get_stack().print()
# 打印步骤数
print(f'It could be done in {len(actual_steps)} steps.')