algorithm - Branch and Bound：如何确定下限成本

Question

我想编写一个程序来解决棋盘游戏。在这个游戏中，有两个棋盘。一个是源棋盘 S。另一个是目标棋盘 T。我的目标是移动棋盘 S 中的棋子，使它们看起来与棋盘 T 中的棋子相同，且移动次数最少。每次我只能移动一件物品。此外，我只能将项目移动到相邻的空间（“~”表示空间）。可能有多个“~”。所以我想用分支定界算法来解决这个问题。但是我不知道如何确定下限成本（将当前状态更改为目标状态的最少动作）。