阳光算法（改进版）：面向密集小障碍物复杂环境的路径规划方法与严谨的Ｏ（ｎ）时间复杂度证明

Ne0inhk

— 12 min read
阳光算法（改进版）：面向密集小障碍物复杂环境的路径规划方法与严谨的Ｏ（ｎ）时间复杂度证明

        阳光算法是一种全新的基于采样的平面路径规划方法，该方法的主要思路是通过模仿阳光照射的自然现象搜索到采集地形或障碍物边缘的切点从而快速构建出可行性路径，非常适合于解决迷宫等复杂地形下的全局路径规划问题。该方法在简洁的同时拥有极高的搜索效率，其计算复杂度经证明也比现有的RRT系列算法更低，关于该方法的详细介绍可以参考https://blog.ZEEKLOG.net/seabiscuit1993/article/details/147731476， 本文不再赘述。尽管阳光算法相较于传统路径规划方法具备显著优势，但其在部分环节仍存在严谨性与完备性方面的不足。本文针对传统的阳光算法中存在的问题做出了两个关键性改进，并通过进一步的分析和仿真实验对比，验证了所提改进方案的优越性和有效性。该改进算法已发表在如下期刊。

Yingjie Deng et al 2026 Meas. Sci. Technol. 37 096303，doi：10.1088/1361-6501/ae49b1

        首先是地图搜索完备性的问题。阳光算法对于地图的探索主要通过

FindTangent(\cdot)

寻找地形或者障碍图的边缘切点，具体是通过模拟阳光照射的现象，以路径节点

x_{sun}

为中心发射等角度间隔的太阳光线的方式来进行采样，之后对采样点进行筛选就可以获得符合条件的路径切点，如图1所示。这种采样方法对于连续不间断的地形或者障碍物边缘效果很好，但是对于密集小障碍物环境却很不理想，这是因为用于搜索的射线间的角度间隔固定，随着射线的逐渐延长，两条射线间的弧长也在逐渐增大，最终两个切点间的距离也会逐渐增加，如图2所示。这会直接导致密集环境中障碍物边缘切点的大量丢失，从而影响算法对于最短可行性路径的搜索。

图1   左图为360°照射采样，右图为切点采样

        针对等角度间隔采样不足的问题，改进后的阳光算法提出了一种自适应采样补偿机制，可以有效解决采样点丢失。改进后的

FindTangent\_mod(\cdot)

函数的伪代码如图3所示。当阳光射线由点

x_{sun}

以等角度间隔射出后，首先寻找两条射线间的最短弧长并将其设为

s

，以最短弧长

s

为基准，对于其他任意两条射线所对应的弧长

L

，如果存在关系

L=m*s

，那么就在这两条射线间的区域额外插入

m-1

条射线来将该区域平均划分为

m

份，如图4所示，其中

m

的定义式为

m=\max\left \{ 1, round\left ( \frac{\min\left \{ L,L_{pre} \right \}*\pi*\theta_{step}}{180*arc} \right ) \right \}

图2   密集小障碍物环境中的切点采样图

        有些读者可能会有这样的问题，难道不可以通过减小太阳射线间的角度间隔来提高在小障碍物密集区域的采样点数量吗？这种思路其实是可行的，然而一般的搜索地图中不仅存在小障碍物密集区域，还存在具有连续不间断边缘的大型障碍物，在这种情况下较小的角度间隔反而会生成大量的冗余节点，降低采样进行的效率，因此自适应采样补偿机制本质上是一种角度间隔的自适应调整。

图3    

FindTangent\_mod(\cdot)

函数伪代码

        除了采样点丢失的问题外，传统的阳光算法还存在时间复杂度的证明不严谨的问题。由证明的过程可知，阳光算法的时间复杂度为

O\left ( n \right )

的前提是数据集

Openset

为有限集合。但是传统的阳光算法并不存在

Openset

筛选机制，因此实际上

Openset

是无上限的，这不仅导致了时间复杂度验证的严谨性问题，无上限也意味着集合中存在冗余节点，这将降低算法的运行速度。为了提高算法的搜索速度，同时确保计算复杂度验证的严谨性，改进后的阳光算法提出了一种新型的滤波筛选机制用来保证集合

Openset

的有限性。这种滤波机制建立在之前的

NotOtherSon

的基础上，在筛选切点之前，首先对已经保存在

Openset

中的节点进行筛选。如图5所示，首先选取任意一个切点

x_{pt}

，对于

Openset

中的任意一个节点

x

，

L_1

表示从出发点

x_{start}

到达该点的原始路径的长度，

L_2

表示由出发点

x_{start}

经过点

x_{sun}

和切点

x_{pt}

到达该点的长度，如果存在关系

L_1>L_2

，那么说明到达该点的原始路径不是最优的，并将该点和其对应的连接关系从相应的集合中去除，重复上述操作直到所有的切点都将

Openset

中的节点遍历完成。相应的对于切点

x_{pt}

，如果连接

x_{pt}

和

x_{sun}

的总路径长度比连接

x_{pt}

和

Openset

中任何一个点的总路径长度都要长，那么说明

x_{pt}

应该是其他点的子节点而不是

x_{sun}

的。通过上述过滤机制进一步限制了

Openset

的大小使其存在有限边界，保证了时间复杂度证明的严谨性。

图4   自适应采样补偿机制演示图

      首先需要找到在算法运行过程中重复出现次数最多的函数，即

CollisionFree(\cdot)

函数，选择此函数的原因是它需要逐个像素的检查占用率，并且在每次迭代循环中都会被调用。如图6所示为改进的阳关算法的伪代码，假设闭集

Closeset

中存在

n_c

个点，由第五行可知

CollisionFree(\cdot)

函数在

Illnuminate(\cdot)

函数中被调用

n_c

次；对于第十行的每次

FindTanget\_mod(\cdot)

函数调用，可以参考图3中的伪代码，假设阳光射线的长度存在上界

\bar L

，设

CollisionFree(\cdot)

在

FindTanget\_mod(\cdot)

函数中的总调用次数为

n_t

，在第五行中的调用次数为

n_{t1}

次，在第十六行的调用次数为

n_{t2}

次，存在关系

n_t=n_{t1}+n_{t2}

，由

FindTanget\_mod(\cdot)

函数的伪代码可知

n_{t1}\le\left ( ceil\left ( \frac{360^\circ}{\theta_{step}} \right )+1\right )*\left ( ceil\left ( \frac{\bar L}{\Delta_{step}} \right )+1 \right )

其中

ceil\left ( \cdot \right )

为向上取整函数。由第十行可知，while循环将会执行

ceil\left ( \frac{360^\circ}{\theta_{step}} \right )

次。由

m

的定义式和阳光射线长度的上界

\bar L

可知，

m

的上界可以定义为

\bar m=round\left ( \frac{\bar L*\pi*\theta_{step}}{180*arc} \right )

由此可以得到

n_{t2}

的边界为

n_{t2}\le\bar m*ceil\left ( \frac{360^\circ}{\theta_{step}} \right )*\left ( ceil\left ( \frac{\bar L}{\theta_{step}} \right )+1 \right )

由上述不等式可知

n_{t1}

和

n_{t2}

均存在有限上界，那么一定存在关系

n_{t}\le\bar n_t

，并且

\bar n_t

是一个正常数。由此可知在图6第十行处

FindTanget\_mod(\cdot)

函数最多执行

n_c*n_t

次。又由于数据集

Openset

存在有限边界

\bar n_0

，切点集合

X_{candidates}

存在有限边界

\bar n_{X}

，在第十四行

CollisionFree(\cdot)

最多执行

n_c*\bar n_X*\bar n_o

次，在第二十三行最多执行

n_c*\bar n_X

次。设

CollisionFree(\cdot)

函数的最大执行次数为

n_{all}

，那么存在关系

n_{all}\le n_c+n_c*\bar n_t+n_c*\bar n_X*\bar n_o+n_c*\bar n_X

由上式可以得出关系

n_{all}\in O\left ( n \right )

，所以改进后的算法的计算复杂度为

O\left ( n \right )

。

图5    

Openset

数据集筛选演示图

图6    改进后的阳光算法伪代码图

Read more

按需购买Token：针对高频算法推理用户的灵活计费模式

按需购买Token：针对高频算法推理用户的灵活计费模式 在算法竞赛、科研验证和工程开发的日常中，一个现实问题正变得越来越突出：如何在保证模型推理质量的同时，有效控制使用成本？许多开发者发现，每当他们需要反复调试一段代码逻辑、批量测试不同输入条件下的解题路径，或是进行多轮数学证明推演时，依赖通用大模型API所带来的费用迅速累积——一次看似简单的调用可能不贵，但成百上千次的迭代下来，账单却令人望而却步。 正是在这种背景下，一种新的技术范式正在兴起：小参数、高密度、垂直优化的专用模型 + 本地部署 + 按Token计量计费。VibeThinker-1.5B-APP 正是这一趋势的典型代表。它不是一个泛化能力强大的“全能助手”，而是一位专注于数学推理与算法编程任务的“专项选手”。仅15亿参数的体量，却能在AIME、HMMT等高难度数学竞赛题上超越数百亿参数的大模型；支持Docker镜像一键部署，可在消费级GPU上稳定运行；更重要的是，它的使用方式打破了传统云服务“按请求收费”的固定模式，引入了更精细、更公平的“按生成Token数量计费”机制。 这不仅仅是一次性能与成本的再平衡，更是对AI

By Ne0inhk
《算法题讲解指南：优选算法-二分查找》--23.寻找旋转排序数组中的最小值，24.0~n-1中缺失的数字

《算法题讲解指南：优选算法-二分查找》--23.寻找旋转排序数组中的最小值，24.0~n-1中缺失的数字

🔥小叶-duck：个人主页 ❄️个人专栏：《Data-Structure-Learning》 《C++入门到进阶&自我学习过程记录》《算法题讲解指南》--从优选到贪心 ✨未择之路，不须回头 已择之路，纵是荆棘遍野，亦作花海遨游 目录 23.寻找旋转排序数组中的最小值 题目链接： 题目描述： 题目示例： 解法（二分查找）： 算法思路： C++算法代码：(以nums[ n - 1 ]为参照物) C++算法代码：(以nums[ 0 ]为参照物) 算法总结及流程解析： 24.0~n-1中缺失的数字 题目链接： 题目描述： 题目示例： 解法（二分查找）： 算法思路： C++算法代码： 算法总结及流程解析： 结束语

By Ne0inhk
Flutter for OpenHarmony: Flutter 三方库 collection 为鸿蒙端处理海量业务数据提供算法级的集合操作支持（数据处理瑞士军刀）

Flutter for OpenHarmony: Flutter 三方库 collection 为鸿蒙端处理海量业务数据提供算法级的集合操作支持（数据处理瑞士军刀）

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.ZEEKLOG.net 前言 在进行 OpenHarmony 的复杂业务逻辑开发时，我们经常需要处理各种 Lists、Sets 和 Maps： 1. 数据分组：如何将成百上千条鸿蒙日志按日期自动归类（GroupBy）？ 2. 集合对比：如何判断两个鸿蒙节点的状态列表是否内容一致（无视顺序）？ 3. 优先级队列：如何在鸿蒙任务调度中自动让高优先级的任务插队排在第一位？ collection 软件包是 Dart 官方团队维护的“集合增强包”。它补齐了原生态集合操作在算法层面的短板，为鸿蒙开发者提供了一套工业级、高性能的数据处理函数库。 一、高级数据处理模型 collection 在基础 List/Map 之上增加了丰富的算法维度。 鸿蒙原始迭代器 (Iterable) 分组与聚合 (GroupBy) 特殊数据结构 (Queue/Heap) 业务最终态 深层对比 (Equality)

By Ne0inhk
深入理解强化学习：近端策略优化（PPO）算法详解

深入理解强化学习：近端策略优化（PPO）算法详解

深入理解强化学习：近端策略优化（PPO）算法详解 近端策略优化（Proximal Policy Optimization, PPO）是强化学习领域最具影响力和应用最广泛的算法之一。自2017年由OpenAI提出以来，它凭借其出色的稳定性、高效的性能和相对简单的实现，成为了许多复杂决策任务的首选算法。本文将带你深入剖析PPO的每一个细节，从算法的起源、核心数学原理，到公式的详细推导和广泛的实际应用。 1. 算法的由来：为什么我们需要PPO？ 在PPO诞生之前，策略梯度（Policy Gradient, PG）方法是解决强化学习问题的主流选择。然而，传统的PG方法存在两个棘手的问题： 1. 更新步长敏感性：策略网络的更新步长（即学习率）极难选择。如果步长太大，一次糟糕的更新就可能让策略性能急剧下降，甚至“万劫不复”；如果步长太小，训练过程又会变得异常缓慢，难以收敛。 2. 数据利用率低：大多数基础的PG算法（如REINFORCE）是On-policy的，这意味着它们只能使用当前策略采样的数据进行学习。一旦策略更新，所有旧数据都将被丢弃，导致采样效率极低。

By Ne0inhk