0x27 A*
2024-08-31 09:58:46
终于完全了解A*到底是什么玩意儿了
对于当前的决策，选取当前花费+预估花费最小来拓展。
因为假如预估出现失误，那么很可能就会延伸到一个错误的决策点，而这个决策点偏偏就是ed，而由于预估失误，其他点的当前花费+预估花费比这个错误的花费大，那么答案就错了。
所以预估花费要比最小花费小。
证一下：
f函数为预估值，g函数为理论最小值，s函数为到达当前的费用
设通过点x延伸是最优的
由于预估失误，此时s(x)+f(x)>s(y)+f(y) 而其实 s(x)+g(x)<s(y)+g(y)
那么先被取出的是y，s(ed)=s(y)+c y->z ed
但是s(y)+c y->ed = s(y)+g(y) > s(x)+g(x) > s(x)+f(x)
先出堆的必然是x，重新更新一次ed
poj2449 k短路 QAQ
poj1077 宽搜第一题做烂的八数码
没什么好放的
最新文章
- JS常用正则表达式和JS控制输入框输入限制(数字、汉字、字符)
- NewQuant正式在Github发布
- HDU 3709 Balanced Number (数位DP)
- Unity学习笔记（一）——基本概念之场景（Scene）
- IIS 之 打开/关闭 Internet 信息服务
- Qt 添加外部库文件（四种方法）
- WPF 中如何使用第三方控件 ，可以使用WindowsFormsHost 类
- NekoHTML
- Deep Learning 学习随记（三）Softmax regression
- 我的MYSQL学习心得（十一）
- pcap filter
- 深入设计电子计算器(一)——CPU指令集设计
- swiper 轮播图，拖动之后继续轮播
- 下面程序的输出结果是____ A:11,10 B:11,11 C:10,10 D:10,11 int x=10; int y=x++; printf("%d,%d",(x++,y),y++);
- JavaScript 函数调用和this指针
- Linux 第七天
- ubuntu ufw防火墙软件的配置入门
- JavaScript 如何断平台
- 重识linux-SSH中的SFTP
- .NetCore中使用AspectCore、ExceptionLess 实现AOP操作日志记录