最短路问题与标号算法(label correcting algorithm)研究(4)

用户1621951

发布于 2020-05-12 09:42:58

1.3K0

发布于 2020-05-12 09:42:58

前文回顾

这是全文第三章label correcting algorithm的第二节。本章围绕Label Correcting Algorithms展开。上一节已经介绍了最短路径算法Generic Label Correcting Algorithm以及Modified Label Correcting Algorithm，本节将介绍在前两个算法上改进得到的FIFO Label Correcting Algorithm以及Deque Label Correcting Algorithm。点击下方链接回顾往期内容：

最短路问题与标号算法(label setting algorithm)研究(1) - 开篇介绍

最短路问题与标号算法(label correcting algorithm)研究(2) - 最短路径问题简介

最短路问题与标号算法(label correcting algorithm)研究(3)

3.4 FIFO Label Correcting Algorithm

3.4.1 算法介绍

同样我们再次回顾一下Modified Label Correcting Algorithm的关键步骤：引入SE_LIST记录距离标签更新的节点编号，并在下一次迭代时检查SE_LIST内某一节点发出的所有弧，即表3-5第7行与第13行。我们可以看出算法并没有给出从SE_LIST中选择节点以及向SE_LIST添加节点的具体规则，因此我们在相应代码实现时以随机的方式选取节点，并将新的节点添加到SE_LIST的尾部，即表3-6第48-50行与58-60行，表3-7第49-52行与63-65行。这种随机方式是否会对算法效率产生影响呢？前边我们已经知道，当最大网络弧长非常大时Modified Label Correcting Algorithm的迭代次数为。现在假设我们其将应用到一个病态的数据集上（这类数据集往往含有非常大的值），且每次迭代时从SE_LIST中选取节点或向SE_LIST中添加节点的顺序不合适时，算法总的迭代次数会随着网络节点数成指数式增长。显然，为了保证算法效率的可靠性我们必须设计出较为合理的规则对SE_LIST中节点进行操作。这里介绍一种基于FIFO（FirstInFirstOut，先进先出）的节点处理规则，我们称其为FIFO Label Correcting Algorithm。

这里我们尝试对中的弧进行排序以解决Generic Label Correcting Algorithm中弧扫描规则不明确问题（或者说SE_LIST中节点操作顺序问题）：将弧集合中的所有弧以某种特定的方式排序，然后在每次迭代中逐个检查中的弧，如果某条弧满足条件：，则更新相应的距离标签：，及节点的前向节点。当某步迭代后，中所有弧都满足最优性条件时，结束算法。

接下来我们回顾一下3.3.1小节的内容，在引入SE_LIST时我们提到只有当节点的距离标签更新时才需要在后续迭代时检查从节点发出的所有弧是否满足最优性条件。所以上述尝试还需进一步改进。

我们将弧集合中的弧按照它们的尾节点升排序，以便所有具有相同尾节点的弧都连续出现在集合中。这样在扫描弧时，我们可以一次考虑一个节点发出的所有弧，比如节点，扫描中的弧，并判断其是否满足最优性条件。假设在某次迭代遍历过程中，算法没有更新节点的距离标签，那么在下一步迭代中，始终存在，因此没有必要再次检查中的弧。

根据以上分析，我们同样引入可扫描列表SE_LIST，记录在一次迭代过程中距离标签发生更新的所有节点，并在下一次迭代中只考虑该列表中节点发出的所有弧。具体细节为：从SE_LIST一端（这里以左端为例）取出一个节点，检查中的所有弧是否满足最优性条件；从SE_LIST另一端（右端）添加新的节点以便后续迭代检查判断。我们称为FIFO规则，即先进先出。采用这类规则的算法称为FIFO Label Correcting Algorithm，其算法步骤如下：

表3-8 FIFO Label Correcting Algorithm

学习到这里你可能会发现，Modified Label Correcting Algorithm和FIFO Label Correcting Algorithm的步骤几乎一样。事实也是如此，如果Modified Label Correcting Algorithm采取"从SE_LIST的头部选择节点，并将新的节点添加到SE_LIST的尾部"的策略，这和我们本节提出的FIFO Label Correcting Algorithm是相同的，你也可以认为FIFO Label Correcting Algorithm是Modified Label Correcting Algorithm的一种特例。

复杂度分析

FIFO Label Correcting Algorithm以FIFO方式处理对SE_LIST进行操作，有效避免了最大弧长值对算法效率产生的影响。我们已经知道Modified Label Correcting Algorithm总的迭代次数为，所以FIFO Label Correcting Algorithm总的迭代次数为。

3.4.2 算法实现

首先给出Python版本的FIFO Label Correcting Algorithm实现（求解附录2中源节点1到其他节点的最短路径）。

"""导入相关基础包，定义全局变量"""
import pandas as pd
import numpy as np
import copy
g_node_list=[] #网络节点集合
g_node_zone={} #网络节点类别集合
g_link_list=[] #网络弧集合
g_adjacent_arc_list={}#节点邻接弧集合（从节点i发出的弧集合）
g_shortest_path=[]#最短路径集合
g_node_status=[]#网络节点状态
g_number_of_nodes=0#网络节点个数
g_origin=None   #网络源节点
node_predecessor=[]#前向节点集合
node_label_cost=[]#距离标签集合
SE_LIST=[]#可扫描节点集合
Max_label_cost=99999#初始距离标签
"""导入网络数据文件，构建基础网络并初始化相关变量"""
#读取网络节点数据
df_node=pd.read_csv('./input_file/node.csv')
df_node=df_node.iloc[:,:].values
for i in range(len(df_node)):
    g_node_list.append(df_node[i,0])
    g_node_zone[df_node[i, 0]] = df_node[i, -1]
    g_number_of_nodes+=1
    g_adjacent_arc_list[df_node[i,0]]=[]
    if df_node[i, 3] == 1:
        g_origin = df_node[i, 0]
g_node_status=[0 for i in range(g_number_of_nodes)] #初始化网络节点状态
Distance=np.ones((g_number_of_nodes,g_number_of_nodes))\
*Max_label_cost #距离矩阵
node_predecessor=[-1]*g_number_of_nodes
node_label_cost=[Max_label_cost]*g_number_of_nodes
node_predecessor[g_origin-1]=0
node_label_cost[g_origin-1] = 0
#读取网络弧数据
df_link=pd.read_csv('./input_file/road_link.csv')
df_link=df_link.iloc[:,:].values
for i in range(len(df_link)):
    g_link_list.append((df_link[i,1],df_link[i,2]))
    Distance[df_link[i,1]-1,df_link[i,2]-1]=df_link[i,3]
    g_adjacent_arc_list[df_link[i,1]].append(df_link[i,2])
SE_LIST=[g_origin]
g_node_status[g_origin-1]=1
"""最短路径求解：扫描网络弧，依据检查最优性条件更新距离标签"""
while len(SE_LIST):
    head=SE_LIST[0]#从可扫描列表中取出第一个元素
    SE_LIST.pop(0)#从可扫描列表中删除第一个元素
    g_node_status[head-1]=0
    adjacent_arc_list=g_adjacent_arc_list[head]#获取当前节点的邻接弧集合
    for tail in adjacent_arc_list:
        if node_label_cost[tail-1]>\
node_label_cost[head-1]+Distance[head-1,tail-1]:
            node_label_cost[tail-1]=\
node_label_cost[head-1]+Distance[head-1,tail-1]
            node_predecessor[tail-1]=head
            if g_node_status[tail-1]==0:
                SE_LIST.append(tail)#将新节点添加到可扫描列表尾部,append方法实现从列表尾部添加元素
                g_node_status[tail-1]=1
"""依据前向节点生成最短路径"""
agent_id=1
o_zone_id=g_node_zone[g_origin]
for destination in g_node_list:
    if g_origin!=destination:
        d_zone_id=g_node_zone[destination]
        if node_label_cost[destination-1]==Max_label_cost:
            path=" "
            g_shortest_path.append([agent_id, o_zone_id,d_zone_id,path, node_label_cost[destination - 1]])
        else:
            to_node=copy.copy(destination)
            path= "%s" % to_node
            while node_predecessor[to_node-1]!=g_origin:
                path="%s;"% node_predecessor[to_node - 1] + path
                g=node_predecessor[to_node-1]
                to_node=g
            path="%s;"%g_origin+path
            g_shortest_path.append([agent_id, o_zone_id,d_zone_id,path, node_label_cost[destination - 1]])
        agent_id+=1
"""将求解结果导出到csv文件"""
#将数据转换为DataFrame格式方便导出csv文件
g_shortest_path=np.array(g_shortest_path)
col=['agent_id','o_zone_id','d_zone_id','node_sequence','distance']
file_data = pd.DataFrame(g_shortest_path, index=range(len(g_shortest_path)),columns=col)
file_data.to_csv('./3_fifo_label_correcting/agent.csv',index=False)

表3-9 Python实现FIFO Label Correcting Algorithm（页面可滑动）

接下来给出MATLAB版本的FIFO Label Correcting Algorithm实现（求解附录2中源节点1到其他节点的最短路径）。

%% clear
clc
clear

%% 设置变量
g_node_list = []; %网络节点集合
g_link_list = []; %网络弧集合
g_origin = [];   %网络源节点
g_number_of_nodes = 0;%网络节点个数
node_predecessor = [];%前向节点集合
node_label_cost = [];%距离标签集合
Max_label_cost = inf; %初始距离标签
g_adjacent_arc_list={}; %节点邻接弧集合（从节点i发出的弧集合）
g_node_status=[]; %网络节点状态
SE_LIST=[]; %可扫描节点集合

%% 导入网络数据文件，构建基础网络并初始化相关变量
%读取网络节点数据
df_node = csvread('node.csv',1,0);
g_number_of_nodes = size(df_node,1);
g_node_list = df_node(:,1);
g_node_status = zeros(1,g_number_of_nodes);
for i = 1 : g_number_of_nodes
    if df_node(i,4)==1
        g_origin=df_node(i,1);
        o_zone_id = df_node(i,5);
    end
end
Distance = ones(g_number_of_nodes,g_number_of_nodes)*Max_label_cost; 
%距离矩阵
node_predecessor = -1*ones(1,g_number_of_nodes);
node_label_cost = Max_label_cost*ones(1,g_number_of_nodes);
node_predecessor(1,g_origin) = 0;
node_label_cost(1,g_origin) = 0;
g_adjacent_arc_list = cell(1, g_number_of_nodes);
%读取网络弧数据
df_link = csvread('road_link.csv',1,0);
g_link_list = df_link(:,2:3);
for i = 1 : size(df_link, 1) 
    Distance(df_link(i,2),df_link(i,3)) = df_link(i,4);
    g_adjacent_arc_list{df_link(i,2)} = [g_adjacent_arc_list{df_link(i,2)}, df_link(i,3)];
end

%% 最短路径求解：扫描网络弧，依据检查最优性条件更新距离标签
SE_LIST=[g_origin];
g_node_status(g_origin)=1;
while ~isempty(SE_LIST)
    head=SE_LIST(1); %从可扫描列表中取出第一个元素
    SE_LIST(1)=[]; %从可扫描列表中删除第一个元素
    g_node_status(head)=0;
adjacent_arc_list = g_adjacent_arc_list(head); 
%获取当前节点的邻接弧
    adjacent_arc_list = cell2mat(adjacent_arc_list);
    for i = 1 : length(adjacent_arc_list)
        tail = adjacent_arc_list(i);
        if node_label_cost(tail)>…
node_label_cost(head)+Distance(head,tail)
            node_label_cost(tail)=…
node_label_cost(head)+Distance(head,tail);
            node_predecessor(tail)=head;
            if g_node_status(tail)==0
                SE_LIST = [SE_LIST,tail];
                g_node_status(tail) = 1;
            end
        end
    end   
end

%% 依据前向节点生成最短路径
distance_column = [];
path_column = {};
o_zone_id_column = o_zone_id * ones(g_number_of_nodes-1, 1);
d_zone_id_column = [];
agent_id_column = [1:(g_number_of_nodes-1)]';
for i = 1: size(g_node_list, 1)
    destination = g_node_list(i);
    if g_origin ~= destination
        d_zone_id_column = [d_zone_id_column; df_node(i,5)];
        if node_label_cost(destination)==Max_label_cost
            path="";
            distance = 99999;
            distance_column = [distance_column; 99999];
        else
            to_node=destination;
            path=num2str(to_node);
            while node_predecessor(to_node)~=g_origin
                path=strcat(';',path);
                path=strcat(num2str(node_predecessor(to_node)),path);
                g=node_predecessor(to_node);
                to_node=g;
            end
            path=strcat(';',path);
            path=strcat(num2str(g_origin),path);
            distance_column = [distance_column; node_label_cost(i)];
        end
        path_column=[path_column;path];
    end
end

title = {'agent_id','o_zone_id','d_zone_id','node_sequence','distance'};
result_table=table(agent_id_column,o_zone_id_column,…
d_zone_id_column,path_column,distance_column,'VariableNames',title);
writetable(result_table, 'agent.csv',…
'Delimiter',',','QuoteStrings',true)

表3-10 MATLAB实现FIFO Label Correcting Algorithm（页面可滑动）

3.5 Deque Label Correcting Algorithm

3.5.1算法介绍

同样，我们先回顾一下已学的三个Label Correcting Algorithms的特点：Generic Label Correcting Algorithm提出了一种新的算法框架，即Label Correcting，它允许我们以更有效、灵活的方式求解最短路问题，但它的灵活性也正是它缺点，由于规则的缺失导致算法效率不能保证；因此Modified Label Correcting Algorithm引入了可扫描列表SE_LIST来明确应该扫描哪些弧，算法虽有改进但却带来了新的问题，以何种规则处理SE_LIST中节点？最后FIFO Label Correcting Algorithm提出了FIFO规则来明确SE_LIST中节点的操作规则，即表3-8第7行和第13行，在相应代码实现中体现在表3-9第46-48行和第56-59行，表3-10第49-51行和第62-64行。这里请思考下除了FIFO是最好的么？还有其他规则可以选择么？

接下来我们介绍另一种规则：将SE_LIST作为Deque处理。如图3-4（a）所示，Deuqe以Left-front标记队列的左端头部，Left-rear标记队列的左端尾部，Right-front标记队列的右端头部，Right-rear标记队列的右端尾部，当需要进行删除或者插入操作时可以选择在两端进行。

图3-4 Deque数据结构

Deque Label Correcting Algorithm将SE_LIST看作一个Deque数据结构，并且规定遍历节点时从SE_LIST的一端头部开始（这里我们以左端头部为例），添加节点时，如果该节点已在SE_LIST出现过中，则将其添加到SE_LIST的左端头部，否则将其添加到SE_LIST右端尾部尾端。接下来进一步分析采用Deque数据结构的原因。

假设在前次迭代中，节点已在SE_LIST中出现过，且某些节点可能将其作为前向节点。第次迭代时，已在SE_LIST中，如果节点的距离标签再次更新后，节点将被加入SE_LIST中：如果将节点添加到SE_LIST的右端尾部，则随后迭代时则会依次检查等节点，并更新其他节点的距离标签，当算法检查到节点时，又会更新节点的距离标签，因此建立在旧标签基础之上时其他距离标签将会失效，因此降低了算法效率。而对在次迭代中从未在SE_LIST中出现的节点来说，节点将SE_LIST已有的节点作为其可能的前向节点，因此应加到SE_LIST右端尾部。因此这种处理规则是合适的。Deque Label Correcting Algorithm步骤如下。

表3-11 Deque Label Correcting Algorithm

关于Deque Label Correcting Algorithm也可以参考文献[5]进一步学习。

复杂度分析

大量研究表明，Deque方法检查的节点数量比大多数其他标签校正算法要少。虽然该算法时间复杂度不是多项式，但在实际应用中却很有效。而且，该算法被证明是解决稀疏和交通网络最短路问题最快的算法之一。

3.5.2 算法实现

首先给出Python版本的Deque Label Correcting Algorithm实现（求解附录2中源节点1到其他节点的最短路径）。

"""导入相关基础包，定义全局变量"""
import pandas as pd
import numpy as np
import copy
g_node_list=[] #网络节点集合
g_node_zone={} #网络节点类别集合
g_link_list=[] #网络弧集合
g_adjacent_arc_list={}#节点邻接弧集合（从节点i发出的弧集合）
g_shortest_path=[]#最短路径集合
g_node_status=[]#网络节点状态
g_number_of_nodes=0#网络节点个数
g_origin=None   #网络源节点
node_predecessor=[]#前向节点集合
node_label_cost=[]#距离标签集合
SE_LIST=[]#可扫描节点集合
Max_label_cost=99999#初始距离标签
"""导入网络数据文件，构建基础网络并初始化相关变量"""
#读取网络节点数据
df_node=pd.read_csv('./input_file/node.csv')
df_node=df_node.iloc[:,:].values
for i in range(len(df_node)):
    g_node_list.append(df_node[i,0])
    g_node_zone[df_node[i, 0]] = df_node[i, -1]
    g_number_of_nodes+=1
    g_adjacent_arc_list[df_node[i,0]]=[]
    if df_node[i, 3] == 1:
        g_origin = df_node[i, 0]
g_node_status=[0 for i in range(g_number_of_nodes)] #初始化网络节点状态
Distance=np.ones((g_number_of_nodes,g_number_of_nodes))\
*Max_label_cost #距离矩阵
node_predecessor=[-1]*g_number_of_nodes
node_label_cost=[Max_label_cost]*g_number_of_nodes
node_predecessor[g_origin-1]=0
node_label_cost[g_origin-1] = 0
#读取网络弧数据
df_link=pd.read_csv('./input_file/road_link.csv')
df_link=df_link.iloc[:,:].values
for i in range(len(df_link)):
    g_link_list.append((df_link[i,1],df_link[i,2]))
    Distance[df_link[i,1]-1,df_link[i,2]-1]=df_link[i,3]
    g_adjacent_arc_list[df_link[i,1]].append(df_link[i,2])
SE_LIST=[g_origin]
g_node_status[g_origin-1]=1
"""最短路径求解：扫描网络弧，依据检查最优性条件更新距离标签"""
while len(SE_LIST):
    head=SE_LIST[0]#从可扫描列表中取出第一个元素
    SE_LIST.pop(0)#从可扫描列表中删除第一个元素
    g_node_status[head-1]=0
    adjacent_arc_list=g_adjacent_arc_list[head]#获取当前节点的邻接弧集合
    for tail in adjacent_arc_list:
        if node_label_cost[tail-1]>\
node_label_cost[head-1]+Distance[head-1,tail-1]:
            node_label_cost[tail-1]=\
node_label_cost[head-1]+Distance[head-1,tail-1]
            node_predecessor[tail-1]=head
            if g_node_status[tail-1]==0:
                SE_LIST.append(tail)#将新节点添加到可扫描列表尾部,append方法实现从列表尾部添加元素
                g_node_status[tail-1]=1
"""依据前向节点生成最短路径"""
agent_id=1
o_zone_id=g_node_zone[g_origin]
for destination in g_node_list:
    if g_origin!=destination:
        d_zone_id=g_node_zone[destination]
        if node_label_cost[destination-1]==Max_label_cost:
            path=" "
            g_shortest_path.append([agent_id, o_zone_id,d_zone_id,path, node_label_cost[destination - 1]])
        else:
            to_node=copy.copy(destination)
            path= "%s" % to_node
            while node_predecessor[to_node-1]!=g_origin:
                path="%s;"% node_predecessor[to_node - 1] + path
                g=node_predecessor[to_node-1]
                to_node=g
            path="%s;"%g_origin+path
            g_shortest_path.append([agent_id, o_zone_id,d_zone_id,path, node_label_cost[destination - 1]])
        agent_id+=1
"""将求解结果导出到csv文件"""
#将数据转换为DataFrame格式方便导出csv文件
g_shortest_path=np.array(g_shortest_path)
col=['agent_id','o_zone_id','d_zone_id','node_sequence','distance']
file_data = pd.DataFrame(g_shortest_path, index=range(len(g_shortest_path)),columns=col)
file_data.to_csv('./3_fifo_label_correcting/agent.csv',index=False)

表3-12 Python实现Deque Label Correcting Algorithm（页面可滑动）

接下来给出MATLAB版本的Deque Label Correcting Algorithm实现（求解附录2中源节点1到其他节点的最短路径）。

%% clear
clc
clear

%% 设置变量
g_node_list = []; %网络节点集合
g_link_list = []; %网络弧集合
g_origin = [];   %网络源节点
g_number_of_nodes = 0;%网络节点个数
node_predecessor = [];%前向节点集合
node_label_cost = [];%距离标签集合
Max_label_cost = inf; %初始距离标签
g_adjacent_arc_list={}; %节点邻接弧集合（从节点i发出的弧集合）
g_node_status=[]; %网络节点状态
SE_LIST=[]; %可扫描节点集合

%% 导入网络数据文件，构建基础网络并初始化相关变量
%读取网络节点数据
df_node = csvread('node.csv',1,0);
g_number_of_nodes = size(df_node,1);
g_node_list = df_node(:,1);
g_node_status = zeros(1,g_number_of_nodes);
for i = 1 : g_number_of_nodes
    if df_node(i,4)==1
        g_origin=df_node(i,1);
        o_zone_id = df_node(i,5);
    end
end
Distance = ones(g_number_of_nodes,g_number_of_nodes)*Max_label_cost; 
%距离矩阵
node_predecessor = -1*ones(1,g_number_of_nodes);
node_label_cost = Max_label_cost*ones(1,g_number_of_nodes);
node_predecessor(1,g_origin) = 0;
node_label_cost(1,g_origin) = 0;
g_adjacent_arc_list = cell(1, g_number_of_nodes);
%读取网络弧数据
df_link = csvread('road_link.csv',1,0);
g_link_list = df_link(:,2:3);
for i = 1 : size(df_link, 1) 
    Distance(df_link(i,2),df_link(i,3)) = df_link(i,4);
    g_adjacent_arc_list{df_link(i,2)} = [g_adjacent_arc_list{df_link(i,2)}, df_link(i,3)];
end

%% 最短路径求解：扫描网络弧，依据检查最优性条件更新距离标签
SE_LIST=[g_origin];
g_node_status(g_origin)=1;
while ~isempty(SE_LIST)
    head=SE_LIST(1); %从可扫描列表中取出第一个元素
    SE_LIST(1)=[]; %从可扫描列表中删除第一个元素
    g_node_status(head) = 2;
adjacent_arc_list = g_adjacent_arc_list(head); 
%获取当前节点的邻接弧
    adjacent_arc_list = cell2mat(adjacent_arc_list);
    for i = 1 : length(adjacent_arc_list)
        tail = adjacent_arc_list(i);
        if node_label_cost(tail)>…
node_label_cost(head)+Distance(head,tail)
            node_label_cost(tail)=…
node_label_cost(head)+Distance(head,tail);
            node_predecessor(tail)=head;
            if g_node_status(tail)==0
                SE_LIST = [SE_LIST, tail];
                g_node_status(tail) = 1;
            elseif g_node_status(tail) == 2
                SE_LIST = [tail, SE_LIST];
                g_node_status(tail) = 1;
            end
        end
    end   
end

%% 依据前向节点生成最短路径
destination_column = [];
distance_column = [];
path_column = {};
o_zone_id_column = o_zone_id * ones(g_number_of_nodes-1, 1);
d_zone_id_column = [];
agent_id_column = [1:(g_number_of_nodes-1)]';
for i = 1: size(g_node_list, 1)
    destination = g_node_list(i);
    if g_origin ~= destination
        destination_column = [destination_column; destination];
        d_zone_id_column = [d_zone_id_column; df_node(i,5)];
        if node_label_cost(destination)==Max_label_cost
            path="";
            distance = 99999;
            distance_column = [distance_column; 99999];
        else
            to_node=destination;
            path=num2str(to_node);
            while node_predecessor(to_node)~=g_origin
                path=strcat(';',path);
                path=strcat(num2str(node_predecessor(to_node)),path);
                g=node_predecessor(to_node);
                to_node=g;
            end
            path=strcat(';',path);
            path=strcat(num2str(g_origin),path);
            distance_column = [distance_column; node_label_cost(i)];
        end
        path_column=[path_column;path];
    end
end

title = {'agent_id','o_zone_id','d_zone_id','node_sequence','distance'};
result_table=table(agent_id_column,o_zone_id_column,…
d_zone_id_column,path_column,distance_column,'VariableNames',title);
writetable(result_table, 'agent.csv',…
'Delimiter',',','QuoteStrings',true)

表3-13 MATLAB实现Deque Label Correcting Algorithm（页面可滑动）

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2020-05-04，如有侵权请联系 cloudcommunity@tencent.com 删除

matlab