基于地理网络的最短路径并行双向搜索通信方法

摘要

本发明涉及基于地理网络的最短路径并行双向搜索通信方法，属于最短路径并行双向搜索通信技术领域；该方法包括在源点和终点开辟两个进程进行双向通信，两个进程分别读取所有的数据，构建出地理网络；设置通信粒度NUM为2以上的正整数；两个进程分别设置数组Index1、Index2来存储所有点的标识状态；两个进程分别设置通信数组Mess1、Mess2;根据源点和终点的经纬度差值，选取差值大的经度或纬度来表示地理网络中各点的地理属性，两个进程分别设置数组Mess1中各点地理属性值最大值Xmax及数组Mess2中各点地理属性值最小值Xmin；进行通信时，当搜索次数等于NUM时，两个进程进行一次通信。该方法具有减少通信次数，以及减少无效通信量的特点，提升已有技术的效率。

主权项

一种基于地理网络的最短路径并行双向搜索通信方法，其特征在于，在源点开辟进程1、终点开辟进程2，两个进程同时进行搜索及双向通信；两个进程分别读取所有的数据，包括网络中所有的点的编号、点的经纬度坐标、点的标识以及各点之间的拓扑关系，构建出地理网络；设置通信粒度NUM为2以上的正整数；各点的标识的状态分为永久标识和非永久标识，两个进程分别设置数组Index1、Index2存储所有点的标识的状态，设定各点的标识的初始状态为非永久标识；设置两个进程的通信数组分别为Mess1、Mess2，两个数组的大小均为NUM；根据源点和终点的经纬度差值，选取差值大的经度或纬度来表示地理网络中各点的地理属性，并当源点的地理属性值小于终点的地理属性值，进程1设置Mess1中各点地理属性值的最大值为参数Xmax、进程2设置Mess2中各点地理属性值的最小值为参数Xmin，并设置参数Xmax、参数Xmin的初始值为0；对于进程1的通信，包括以下步骤：步骤11：进程1进行搜索，当搜索的次数小于NUM时，进程1将搜索到的NUM个点的编号保存在数组Mess1中，同时根据点的编号在Index1中将点的标识改为永久标识；步骤12：进程1当搜索次数等于NUM时，将Mess1中NUM个点的地理属性值的最大值赋予Xmax；进程1将参数Xmax发送给进程2，并接收进程2的参数Xmin；步骤13：进程1判断参数Xmin是否小于参数Xmax，若Xmin>Xmax，说明没有相交，清空Mess1、Xmax，重复步骤11、步骤12；若Xmin<Xmax，进行步骤14；步骤14：进程1将Mess1发送给进程2，并接收进程2的Mess2；进程1根据接收到的Mess2中各点的编号在Index1中查找是否存在点的标识为永久标识，若存在，发送消息返回给进程2，搜索终止，进行步骤16；若不存在，则继续搜索，进行步骤15；步骤15：进程1继续进行搜索，当搜索的次数小于NUM时，进程1将搜索到的NUM个点的编号保存在数组Mess1中，同时根据点的编号在Index1中将点的标识改为永久标识，当搜索次数等于NUM时，进行步骤14；步骤16：结束通信，输出最短路径的结果；对于进程2的通信，包括以下步骤：步骤21：进程2进行搜索，当搜索的次数小于NUM时，进程2将搜索到的NUM个点的编号保存在数组Mess2中，同时根据点的编号在Index2中将点的标识改为永久标识；步骤22：进程2当搜索次数等于NUM时，将Mess2中NUM个点的地理属性值的最小值赋予Xmin；进程2将参数Xmin发送给进程1，并接收进程1的参数Xmax；步骤23：进程2判断参数Xmin是否小于参数Xmax，若Xmin>Xmax，说明没有相交，清空Mess2、Xmin，重复步骤21、步骤22；若Xmin<Xmax，进行步骤24；步骤24：进程2将Mess2发送给进程1，并接收进程1的Mess1；进程2根据接收到的Mess1中各点的编号在Index2中查找是否存在点的标识为永久标识，若存在，发送消息返回给进程1，搜索终止，进行步骤26；若不存在，则继续搜索，进行步骤25；步骤25：进程2继续进行搜索，当搜索的次数小于NUM时，进程2将搜索到的NUM个点的编号保存在数组Mess2中，同时根据点的编号在Index2中将点的标识改为永久标识，当搜索次数等于NUM时，进行步骤24；步骤26：结束通信，输出最短路径的结果。