社区讨论

对本题A* 估价函数的hack

P1379八数码难题参与者 7已保存回复 11

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
11 条
当前快照
1 份
快照标识符
@lo7wd7nf
此快照首次捕获于
2023/10/27 08:50
2 年前
此快照最后确认于
2023/10/27 08:50
2 年前
查看原帖
A* 估价函数 h(x)h(x) 需要满足估计值 小于等于 实际值此时才有正确性
本题很多 A* 题解对估价函数的设计是:不在应该在的位置的数字个数,或者曼哈顿距离 但这些都无法满足要求 h(x)h(x) 设计的要求,即不能满足 估计值小于等于实际值 例如
CPP
123
840
765
这组数据在两种 h(x)h(x) 设计下均为 22 ,但是实际代价为 11
Hack :
821304657821304657 对 oi-wiki A* 的hack
765420381765420381 对 @伟大的王夫子 题解 IDA* 的hack
正确答案/错误答案 :
2020 / 2222
2929 / 2828

回复

11 条回复,欢迎继续交流。

正在加载回复...