scheme - 在 Scheme/Racket 中实现 A* 搜索算法
问题描述
我期待着实现 A* 搜索算法,但我不知道我应该从哪里真正开始。我想出了一种方法来表示我的图表,如下所示:
(
'("city1" (x y (("neighbour1" edgeWeight1)("neighbour2" edgeWeight2))))
...
)
我创建了一个开放列表和一个封闭列表,但从这一点开始,我真的不知道该怎么做。有任何想法吗?
解决方案
尝试实现算法时应该做的第一件事是实现算法使用的抽象。
A* 搜索算法使用两个抽象。第一个抽象是图的抽象。您应该提出一些图的定义并实现函数来执行 A* 所需的“图的事情”(例如,获取给定节点的邻居,查找图中的所有节点等)。
A* 搜索使用的第二个抽象是优先级队列,它用于“开放集”。您将需要为“开放集”提供一个方案定义,并编写方案函数来完成必须完成的事情(即找到并删除成本最低的节点)。
一旦你做了这些事情,你应该会发现算法相当简单。
推荐阅读
- python - 在新环境中构建 cython 扩展:找不到 /lib/libpthread.so.0
- python - 检测部分字符串并相应地重新排列 csv
- html - 无法将 div 与 text-align 水平对齐?
- php - Wordpress 在显示每个类别的帖子时具有多个循环,我可以让它更快吗?
- c# - ASP.NET MVC 应用程序在调试中工作,但在使用 Plesk 和 GoDaddy 发布时不能工作
- php - 调用未定义的方法 Infusionsoft\Api\Rest\ContactService::addWithDupCheck()
- c++ - MESI 协议和 std::atomic - 它是否确保所有写入对其他线程立即可见?
- c# - 为什么是 C# 列表
添加方法很慢? - canvas - 微信小程序Canvas上的触摸事件处理
- python - 从桌面上的 Python 访问 Android 手机上的文件