一种自动检测全节点遍历路径优化方法

摘要

本发明提供了一种高效快速的全节点遍历路径优化的方法，最终生成一个单向的节点队列路径。本方法包括以下几个步骤：首先根据需要解决的实际问题构建节点网络，该网络可以是全向网络，以节点间的边记录路径花费；然后对全部节点建立最小生成树，针对生成树上的所有分支和端点建立队列；之后通过试探性的算法对有分支的节点逐一切断各个分支，每切断一个分支就根据端点队列搜索距离最小的端点对进行连接，不断进行这步操作，直到原最小生成树中的所有分支都被断开，所有节点连接成一个单向队列。在建立新的端点连接时，本方法还提供一种检测机制以避免新连接使节点队列形成一个环，从而避免路径中有节点丢失。此外本发明中还包括一个横向或纵向优先的路径作为优化路径的备选，以提高整个方法的可靠性。

主权项

一种自动检测全节点遍历路径优化方法，在自动检测过程中，将相机停下曝光、检测的检测点定义为一个节点，相机移动路径抽象为连接节点的边，边上的值为相机移动的距离，实际检测中，相机可以在任意两个节点间移动，所述全节点遍历路径优化方法用于优化自动检测过程的路径；其特征在于，所述方法包括以下步骤：步骤A、在自动检测过程中，将预先规划好的检测点作为节点构建节点网络，所有检查点都必须经过并进行检查，在可能出现分支的地方建立节点，以从一个节点到另一个节点的花费作为有向边的值；步骤B、构建节点网络的最小生成树：(1)根据构建的最小生成树建立节点间的连通矩阵；(2)根据构建的最小生成树建立有分支的节点队列：(3)根据构建的最小生成树建立端点节点的队列；(4)对分支节点队列的每一个节点，试探性切断该分支节点的一个分支，同时从端点节点的队列中找出距离最近的两个端点节点，在其间建立一个新连接，记录网络增加的花费；(5)以增加花费最小为准则，对有分支节点逐一去掉其它分支，直到保留花费最小的单向连接；(6)更新连通矩阵；(7)更新分支节点队列；(8)更新端点节点队列；步骤C、根据最小生成树，以新增花费最小为原则，对所有有分支的节点，逐一去除分支并建立端点间的连接；步骤D、不断重复步骤C直到网络的最小生成树每个节点都没有分支，转化为节点单向队列，从而生成优化后的遍历路径作为自动检测路径。