基于改进贪婪算法的道路巡检方法、系统、设备和介质

专利主权项内容

1.一种基于改进贪婪算法的道路巡检方法，其特征在于，包括以下步骤：S1：建立道路巡检模型，包括：在指定区域内的每条道路上设有多个检查点，获取带权无向图，该带权无向图包括检查点集、道路集以及每两个检查点连线的道路代价数组；S2：对检查点进行编号，设置已访问检查点序列和未访问检查点序列；S3：初始化每两个检查点连线的道路代价数组；S4：构造已访问检查点序列，加入起始点，起始点为第一个检查点；S5：判断已访问检查点序列内的检查点的数量是否小于所有检查点的数量，如果不小于，则形成道路巡检路径，该已访问检查点序列所连成的路径为道路巡检路径，否则进行步骤S6；S6：获取未访问检查点序列的第一个检查点，作为当前检查点；删除未访问检查点序列的第一个检查点，形成新的未访问检查点序列；S7：算出当前检查点在已访问检查点序列所有位置中的最小代价，并将当前检查点插入最小代价对应的已访问检查点序列的位置，形成新的已访问检查点序列；S8：重复步骤S5至步骤S7，直到形成道路巡检路径；步骤S7中，所述算出当前检查点在已访问检查点序列所有位置中的最小代价的方法包括：计算当前检查点插入已访问检查点序列中第二个位置至最后一个位置的最小的路径代价和作为最小代价；所述计算当前检查点插入已访问检查点序列中第二个位置至最后一个位置的最小的路径代价和最为最小代价的方法包括：S71：从已访问检查点序列中第二个位置开始遍历至最后一个位置；S72：将当前检查点插入已访问检查点序列；S73：计算当前已访问检查点序列的路径代价和；S74：记录最小的路径代价和并保存当前检查点在已访问检查点序列中的位置；S75：从已访问检查点序列中删除当前检查点；S76：重复步骤S71至步骤S75，完成第二个位置开始遍历至最后一个位置后，获取最小的路径代价和及对应的当前检查点在已访问检查点序列中的位置；该最小的路径代价和为最小代价。。该数据由整理