Dijkstra

FEB

迷宫与网格寻路：四种经典算法对比

本文介绍了DFS、BFS、Dijkstra 与 A * 这四类经典的图与网格搜索算法。DFS采用深度优先、碰壁回溯的思路，借助栈实现，空间开销小，但不保证最短路径，适合只需找到任意可行路径的场景。BFS以队列逐层扩展，能在无权图中得到最短路径，属于盲目搜索，扩展范围较大。Dijkstra使用优先队列，可处理带权路径，能找到全局最小代价路线，但同样盲目扩展，在大网格中效率偏低。A*在 Dijkstra 基础上引入启发函数，结合已走代价与预估剩余距离，有方向地搜索，在满足可采纳性时可得到最优解，效率显著更高，是游戏导航、路径规划等场景的主流选择。整体上，四者从盲目到启发、从简单到高效，覆盖了从可行路径到最优带权路径的不同需求。 …

FEB

从C++中的迭代器说到左闭合区间

和C#中的IEnumerable接口类似，在C++中，遍历标准容器库比如vector、deque、list等，都需要用到迭代器对象(iterator)，根据容器的类型不同以及访问时是否需要读写，迭代器也分为可读写迭代器iterator，只读迭代器const_iterator以及反向迭代器reverse_itertaor。调用容器类型成员的begin和end方法(或者cbegin,cend,rbegin,rend)方法，这两个方法分别返回指向容器首元素，以及尾元素之后的位置(one past the last element)，简称尾后的迭代器。这里面有一个容易误解的地方在于，end方法返回的迭代器，从来都不会指向容器的最后一个元素，而是指向最后一个元素之后的元素。如果容器v的第一个和最后一个元素分别记为first和last，那么调用v.begin()和v.end()返回的迭代器范围( …

iterator left-inclusive Dijkstra

码农兼一个普普通通小青年

迷宫与网格寻路：四种经典算法对比

从C++中的迭代器说到左闭合区间