应用 Dijkstra 算法寻找最低能量路径

Question

我很难进行以下练习：

给定一个可以堆放盒子的机械臂。箱子必须堆放，每堆最多 3 个箱子，箱子的顺序必须按重量排列并放置在初始箱子中（左侧）。机械臂可以拉伸一个位置（+1 空间）或所有位置（+4 空间）。仅考虑机器人使用左和右的双向环境。

初始配置建议：

                             | ------
                             |      |
                             | 
_10_  _30_  ____  _10_  ____ | _40_  ____  _20_  ____  _30_

移动箱子时，需要消耗 1 点能量。然而，移动超过 2 个位置将花费 75% 的移动成本。例如：将盒子移动 4 个位置，需要花费 4*(3/4) = 3 能量。每 10 磅，成本增加 1 能源，因此 20 磅的盒子成本 2。示例：将 40 磅的盒子移动 2 个位置：2*0.75 + 40/10 = 5.5 能源。

因此，可能的最终配置是：

                             | ------
 10    10                    |      |
 30    20                    | 
_40_  _30_  ____  ____  ____ | ____  ____  ____  ____  ____

使用Dijkstra算法，在给定初始配置的情况下，机械臂可以以最低的能量消耗执行任务。

即使我知道 Dijkstra 算法是如何工作的，我也看不出将其应用到练习中的方法。我认为主要问题是我不知道如何将问题表示为有限图。任何有关如何开始解决练习的提示都会有很大帮助。

Answer 1

1. 设计一个数据结构来表示状态（==图顶点）。可能是一个包含 10 个元素的列表来表示位置。每个列表元素都是一个 3 元素列表，代表堆叠在该位置的盒子

2. 给定起始框，枚举这些框的所有可能状态。删除某个位置有超过三个盒子或盒子堆叠顺序错误的州。

3. 设计一种方法来计算是否可以在两个状态之间移动，如果可以，则计算成本。

4. 在可以移动的状态之间添加边并消耗边。

5. 设计一种方法来评估每个状态的分数，估算其与解决方案的接近程度。这可能是相当粗糙的。例如：左侧第一个位置的每个方框为 10 分，左侧第二个位置的每个方框为 9 分，等等

6. 使用步骤 5 中的状态得分作为启发式应用 A* 算法。