在本文中,我们将主要介绍Dijkstra算法和A*算法,从成本计算的角度出发,并逐步展开讨论。我们将从广度优先搜索开始,然后引入Dijkstra算法,与贪心算法进行比较,最终得出A*算法。
成本计算
在路径规划中,成本计算的一个主要因素是距离。距离可以作为一种衡量路径长短的度量指标,通常使用欧几里得距离、曼哈顿距离或其他合适的距离度量方法来计算。本文主要介绍欧几里得距离与曼哈顿距离。
广度优先搜索
广度优先搜索(Breadth First Search,BFS )是一种图遍历算法,按照广度方向逐层遍历所有可达节点。
BFS的基本思想是通过维护一个队列,逐层访问节点。具体步骤如下:
1.将起始节点放入队列中,并标记为已访问。
2.当队列非空时,执行以下步骤:
- 从队列中取出一个节点,记为当前节点,并标记为已访问。
- 如果该节点是目标节点,则返回结果。
- 将当前节点的所有未访问过的邻居节点放入队列中。
3.如果队列为空,则表示已经遍历完所有可达节点,算法结束。
算法框图