Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

该solver实现的heuristic function不是admissible heuristic function #3

Open
ComradeSpark opened this issue Dec 19, 2023 · 0 comments

Comments

@ComradeSpark
Copy link

ComradeSpark commented Dec 19, 2023

即,如README描述,设定为“到目当前状态为止,所有箱子按顺序排列的位置和所有目的地按顺序排列的位置,两两间的manhatten distance总和”是可能大于真实需要步数的(从README中,A*算法在level1中不能得到最优解RurrddddlDRuuuuLLLrdRDrddlLdllUUdR也可以说明此问题)。
提供两个简单的admissible heuristic function的想法:

  1. 对每个箱子,寻找距离其与最近的目标的曼哈顿距离,求和;
  2. 对每个箱子和每个目标,使用曼哈顿距离构造代价矩阵,并使用Kuhn–Munkres算法求解得到最优匹配总开销;
  3. 1或2中的方法,但增加人物和任一/最远(的未到位)箱子的曼哈顿距离 - 1。
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant