算法解读

‘壹’ A星算法详解(个人认为最详细,最通俗易懂的一个版本)

在探索领域中，寻找最短路径的问题经常需要使用到A*算法。A*算法是一种广泛应用于路径规划和游戏开发中的启发式搜索算法。本文将通过详细的步骤，深入解读A*算法的运作原理和实现细节。首先，我们假设目标是从A点移动到B点，其中两点之间被一堵墙隔开。图1展示了这个示例，其中绿色代表A点，红色代表B点，蓝色代表墙。

图1展示了简化后的搜索区域，我们将其划分为正方形的格子。这一简化方法将搜索区域转化为二维数组，数组的每一项代表一个格子，其状态为可走或不可走。通过计算从A点到B点需要经过哪些格子，我们可以找到一条路径。当路径确定后，角色将从一个格子的中心移动到另一个格子的中心，直至到达目的地。

在A*算法中，搜索区域的简化为节点（nodes）的引入提供了基础。节点可以被放置在任意多边形内，可以位于多边形的中心，也可以位于边线上。使用这种方法最简单的原因在于其通用性，适用于不同形状的搜索区域。

算法开始于定义起点A，并将其加入到一个名为开放列表（open list）的集合中。开放列表是一个待检查的格子列表，其中的格子可能是路径的一部分，也可能是路径的候选。随后，我们检查起点A的相邻格子，并将其中可走的或可到达的格子加入开放列表中，同时将起点A作为这些格子的父节点。在追踪路径时，父节点的信息至关重要。

下一步是从开放列表中选择一个与起点A相邻的格子，重复上述过程。但选择哪一格子则基于其F值最小的原则。F值是由G值（从起点A到特定格子的移动代价）和H值（从该格子到终点B的估算成本）相加得到的。

路径排序涉及计算路径中每个格子的F、G和H值。G值代表从起点A到指定格子的移动代价，横向和纵向移动的代价为10，对角线移动的代价为14。这些数值简化了计算过程，同时提高了算法的执行效率。H值通过估计起点到终点的曼哈顿距离计算得出，即横向和纵向距离的总和，忽略对角移动。

计算出G和H值后，我们得到F值，用于后续选择操作。在选择过程开始时，我们会遍历开放列表，选择F值最小的格子。这一过程不断重复，直到将终点加入开放列表，路径被找到。在每一步中，选择的格子从开放列表移除，加入到关闭列表（closed list）中，表示不再需要关注的格子。

在搜索过程中，我们需要对选定的格子执行一系列操作。首先，将该格子从开放列表中移除并加入到关闭列表中。接着，检查与该格子相邻的格子，忽略那些已位于关闭列表中或不可走的格子。对于不在开放列表中的相邻格子，将其加入开放列表中，并将选定的格子作为其父节点。若相邻格子已在开放列表中，会检查新路径是否更优。如果新路径更优，则更新该格子的父节点，并重新计算其F、G和H值。

在搜索过程中，我们不断重复上述步骤，直到找到终点或确定无法找到路径。当终点被加入开放列表后，搜索过程完成。此时，我们可以通过追踪父节点从终点回溯到起点，找到最短路径。

在实现A*算法时，关键在于如何高效地维护开放列表和关闭列表，以及计算路径代价（G、H和F值）。为了优化性能，可以采用排序数据结构（如二叉堆）来管理开放列表，以便快速找到具有最小F值的格子。在考虑其他单位、优化速度、地形损耗、维护未探测区域、平滑路径以及处理非方形搜索区域时，A*算法的实现细节变得更为丰富和复杂。通过阅读相关的高级主题和参考资料，如Amit的A*页面、Smart Moves: Intelligent Path Finding和Terrain Analysis等文章，可以进一步深入理解A*算法的高级应用和优化策略。

‘贰’ DQN从入门到放弃5 深度解读DQN算法

DQN算法深度解读：

一、QLearning回顾 QLearning算法通过估算每一个状态下每一种选择的价值来得到最优策略。 Q值的更新依赖于当前得到的Reward以及下一个时间片的Q值，通过反复实验不断更新Q值直至收敛。

二、DQN引入 在现实问题中，由于状态空间巨大，使用表格存储Q值不可行。 解决方法是价值函数近似，即用一个函数来表示Q，这个函数可以是任意类型，如线性函数或深度神经网络。

三、DQN的核心思想 使用深度神经网络表示Q值：输入状态s，输出包含每一个动作Q值的向量。 训练Q网络：通过QLearning算法获取标签，利用这些标签和Q网络的输出计算损失函数，并通过梯度下降更新Q网络的参数。

四、DQN的训练过程 样本获取：利用QLearning算法在虚拟环境下进行无限次的实验，获取样本。 经验池：由于样本具有连续性，直接用于训练可能导致效果不佳。因此，将样本先存入经验池，然后从中随机采样进行训练，以增强学习的稳定性和效率。 同步进行增强学习和深度学习训练：在DQN中，增强学习QLearning算法和深度学习的SGD训练是同步进行的。通过QLearning获取无限量的训练样本，然后对神经网络进行训练。

五、总结 DQN算法结合了QLearning和深度学习的优势，能够处理高维状态空间的问题。 通过使用深度神经网络表示Q值，并利用经验池和梯度下降方法进行训练，DQN在多个领域取得了显着的效果。