文件名称：ngraph.path：图形中的路径查找
文件大小：2.49MB
文件格式：ZIP
更新时间：2024-02-23 06:20:03
algorithm graph finder pathfinder heap
ngraph.path 快速查找任意图形的路径。 或YouTube上。 如果您想学习演示的制作方法，请参考。 我试图详细描述它。 性能 我在纽约市道路图（ 733,844边线， 264,346节点）上测量了该库的性能。 通过解决250随机路径查找问题来完成。 每种算法都在解决相同的问题。 下表显示解决一个问题所需的时间。 平均 中位数 敏 最高 90 99 A *贪婪（次优） 32毫秒 24毫秒 0毫秒 179毫秒 73毫秒 136毫秒 NBA * 44毫秒 34毫秒 0毫秒 222毫秒 107毫秒 172毫秒 A *，单向 55毫秒 38毫秒 0毫秒 356毫秒 123毫秒 287毫秒 迪克斯特拉 264毫秒 258毫秒 0毫秒 782毫秒 483毫秒 631毫秒 但是，“ A *贪婪”收敛最快，因为名称暗示找到的路径不一定是全局最优的。 为什么这么快？ 有一些因素有助于该库的性能。 我正在使用基于堆的优先级队列，该队列专门为查找路径而构建。 我实现，以便更改任何元素的优先级都需要O(lg n)时间。 每个路径查找器在其探索过程中都会打开许多图形节点，这会对垃
【文件预览】：
ngraph.path-master
----a-star()
--------NodeHeap.js(3KB)
--------a-star.js(5KB)
--------heuristics.js(403B)
--------defaultSettings.js(1KB)
--------nba()
--------a-greedy-star.js(7KB)
--------makeSearchStatePool.js(1KB)
----LICENSE(1KB)
----test()
--------utils()
--------a-star.js(7KB)
--------nba.js(1KB)
--------nodeHeap.js(3KB)
----README.md(8KB)
----index.d.ts(1KB)
----dist()
--------ngraph.path.min.js(16KB)
--------ngraph.path.js(30KB)
----docs()
--------guided.png(26KB)
--------seattle.gif(2.46MB)
--------weighted.png(20KB)
----.gitignore(119B)
----index.js(148B)
----package-lock.json(159KB)
----package.json(713B)