基于神经网络预测的时间A*算法研究复现

1. 论文阅读及信息提取

1.1 构建路网拓扑

1. 赋权有向图

2. 交叉路口作为图的顶点，道路作为图中的边，需要存储拓扑信息：

   • [节点类型] N 表示路口，R 表示道路

   • [节点索引] 每条道路和每个路口顶点的索引值

   • [路口节点N]

     • [权值] 存储通行方向和对应预测的通行时间

     • addNodes 添加相邻道路节点R

     • addInters 添加相邻路口节点N，及方向——

       

   • [道路节点R]

     • [权值] 存储道路长度
     • addNodes 添加相邻路口节点N

3. 论文给出一个由双向道路 R0-R16 和交叉路口 N0-N10 构成的简单路网示例

   

   

*父类Node

论文中JAVA实现

Python改写

class Node():
    def __init__(self, type, id, nodes=None, inters=None):
        self.type = type
        self.id = id
        if nodes is None:
            self.nodes = []
        if inters is None:
            self.inters = {}

    def addNodes(self, NeighborList):
        self.nodes += NeighborList

    def addInters(self, TupleList):
        for item in TupleList:
            self.inters[item[1]] = item[0]

    def addNweight(self, dir, weight):
        self.Nweight[dir] = weight

    def addRweight(self, weight):
        self.Rweight = weight

    def getID(self):
        return self.type + str(self.id)

    def getConnections(self):
        nodes = []
        for i in self.nodes:
            nodes.append(i.getID())
        if self.type == 'R':
            return 'The neighbouring nodes of %s is %s.' % (self.getID(), str(nodes))
        if self.type == 'N':
            inters = []
            for j in self.inters.keys():
                inters.append((j, self.inters[j].getID()))
            return 'The neighbouring nodes of %s is %s, and neighbouring routes is %s.' % (
                    self.getID(), str(nodes), str(inters))

    def getWeight(self):
        if self.type == 'R':
            return 'The weight of %s is %s.' % (self.type + str(self.id), str(self.Rweight))
        if self.type == 'N':
            return 'The weight of %s is %s.' % (self.type + str(self.id), str(self.Nweight))

Python中的变量类型

在创建Node类时遇见了一个令人疑惑的问题——

在__init__函数中设置类的属性时，当属性默认值为可变类型时，所有实例化对象该属性的地址相同，对于某个实例对象属性的修改会对其它实例对象产生连带反应。后来我发现，这里面的坑就是python的变量类型。

• 为不可变类型时

• 为可变类型时

• 解决方法

  

python的可变变量（mutable）与不可变变量（immutable）

• 不可变变量根据值开辟内存地址，值相同的不同变量名指向同一地址；值一旦改变就会占据新的内存空间

  x=1
  y=1
  z=1
  print (id(x))
  print (id(y))
  print (id(z))
  
  #56976040
  #56976040
  #56976040
  
  x=1
  print (id(x))
  x+=1
  print (id(x))
  
  #52454056
  #52454032
  

• 可变变量创建一次就开辟一次地址，不会引用同一块内存；而对同一个对象的操作，内存地址是不会改变的

  x=[]
  y=[]
  z=[]
  print (id(x))
  print (id(y))
  print (id(z))
  
  #62566472
  #62669960
  #62671368
  
  x=[]
  print (id(x))
  x.append(1)
  print (id(x))
  
  #49918024
  #49918024
  

• 因此，不可变变量按值传递——同值不同对象地址相同，修改值地址改变；

  ​ 可变变量按引用传递——同值不同对象地址不同，修改值地址不变

• 以上这一切还有底层原因…扒不下去了，在这里留下一句话：Python一切皆对象。

  （这不禁让我想起JS原型链，这和JS所有数据结构顶端都是对象一样吗？学明白了回来比较一下）

Python中的共享属性

最开始找坑的时候方向错了，于是顺带了解了一下python中共享属性的问题。

python中的类变量和实例变量

• 类变量：可在类的所有实例之间共享的值。
• 实例变量：实例化之后，每个实例单独拥有的变量。
• 类变量和实例变量的区别在于：类变量是所有对象共有，其中一个对象将它值改变，其他对象得到的就是改变后的结果；而实例变量则属对象私有，某一个对象将其值改变，不影响其他对象。

'''
类变量/类属性
1.在类体(class)内，所有函数(def)外声明
2.以<类名>.<属性名>声明

实例变量/实例属性
1.在类体(class)内，所有函数(def)内声明，以self.<属性名>声明
'''

1.2 行驶时间(N权值)的计算分析

路口节点所具有的时间权值可表示为：

​

参数说明：

• 路口的通行时间 T
• 自由流情况下通往该路口的道路的行驶时间 t0
• 美国公路局通过分析大量城市交通的流量数据，进行回归分析总结出路段的行驶时间 t
• 实际通行时间与自由流通行时间之间的比例系数 λ = t/t0
• 交通流量 f
• 路段的通行能力 C
• 阻塞率 q/ C
• 通往该路口的道路的长度 s
• 行车速度，在本文中将其设置为一个常量，无堵塞状况下城市交通中允许通行的最大速度，若运用于可实时监测车速的导航系统中，可将其设置为车辆的行驶速度 v

*获取计算预测时间函数

Python实现

def getFlow(t):
    pass

def calcTime():
    pass

1.3 路径规划算法A*

算法分析

• 综合代价 fn(t) :

  节点 n 的基于行驶时间的代价函数值

• 实际代价 gn(t)：

  从起始节点到达节点 n 的已行驶时间，在路径搜索过程中根据存储的节点时间权值信息计算得到

• 估计代价 hn(t)：

  从节点 n 到达目标节点的估计最少行驶时间

  

  • 节点 n 到目标节点的曼哈顿距离 sn
  • 上文已设置的速度值 v

算法过程

1. 设置起始节点（N0），目标节点[N/R]（N9），出发时刻 t

2. 获取t时刻 起始节点（N0）所有的相邻路口节点的预测通行时间，计算代价函数，选取最佳的邻接路口节点进行更新

3. 计算到达下一节点的道路行驶时间，与该节点预测通行时间和为 t1，更新时刻为 t+t1

4. 获取t+t1时刻 更新节点 所有的相邻路口节点的预测通行时间，重复 2-4 步

5. 目标节点

   • 目标节点R：

     只需要在每次更新路口节点后，判断目标节点是否为该更新节点的相邻节点即可。是则搜索结束。

   • 目标节点N：

     到达目标节点时，搜索结束。

算法实现

*子类RNode/NNode

class NNode(Node):
    def __init__(self, type, id, nodes=None, inters=None, Nweight=None, predictT=None):
        super().__init__(type, id, nodes, inters)
        self.explored = False
        self.time = None
        self.F = None
        self.G = None
        self.H = None
        self.father = None
        self.direction = None
        if Nweight is None:
            self.Nweight = {}
        if predictT is None:
            self.predicT = []

    def __str__(self):
        return self.getID() + ': ' + self.getConnections() + self.getWeight()
        
class RNode(Node):
    def __init__(self, type, id, nodes=None, Rweight=0, length=0):
        super().__init__(type, id, nodes)
        self.Rweight = Rweight
        self.length = length        
		

*路网实例化

这一段，是真的才疏学浅，没有什么批量实例化的好办法硬生生手敲的。如果有好方法请不吝赐教！

nls = []
rls = []

for Nindex in range(11):
    nls.append(NNode('N', Nindex))

for Rindex in range(17):
    rls.append(RNode('R', Rindex))

nls[0].addNodes([rls[0], rls[2], rls[5]])
nls[1].addNodes([rls[1], rls[2], rls[3], rls[6]])
nls[2].addNodes([rls[3], rls[4], rls[7]])
nls[3].addNodes([rls[4], rls[8]])
nls[4].addNodes([rls[5], rls[9]])
nls[5].addNodes([rls[6], rls[9], rls[10], rls[11]])
nls[6].addNodes([rls[7], rls[10], rls[12]])
nls[7].addNodes([rls[8], rls[13]])
nls[8].addNodes([rls[11], rls[14]])
nls[9].addNodes([rls[12], rls[14], rls[15]])
nls[10].addNodes([rls[13], rls[15], rls[16]])

nls[0].addInters([(nls[1], 2), (nls[4], 3)])
nls[1].addInters([(nls[0], 4), (nls[2], 2), (nls[5], 3)])
nls[2].addInters([(nls[1], 4), (nls[3], 2), (nls[6], 3)])
nls[3].addInters([(nls[2], 4), (nls[7], 3)])
nls[4].addInters([(nls[0], 1), (nls[5], 2)])
nls[5].addInters([(nls[1], 1), (nls[4], 4), (nls[6], 2), (nls[8], 3)])
nls[6].addInters([(nls[2], 1), (nls[5], 4), (nls[9], 3)])
nls[7].addInters([(nls[3], 1), (nls[10], 3)])
nls[8].addInters([(nls[5], 1), (nls[9], 2)])
nls[9].addInters([(nls[6], 1), (nls[8], 4), (nls[10], 2)])
nls[10].addInters([(nls[7], 1), (nls[9], 4)])

rls[0].addNodes([nls[0]])
rls[1].addNodes([nls[1]])
rls[2].addNodes([nls[0], nls[1]])
rls[3].addNodes([nls[1], nls[2]])
rls[4].addNodes([nls[2], nls[3]])
rls[5].addNodes([nls[0], nls[4]])
rls[6].addNodes([nls[1], nls[5]])
rls[7].addNodes([nls[2], nls[6]])
rls[8].addNodes([nls[3], nls[7]])
rls[9].addNodes([nls[4], nls[5]])
rls[10].addNodes([nls[5], nls[6]])
rls[11].addNodes([nls[5], nls[8]])
rls[12].addNodes([nls[6], nls[9]])
rls[13].addNodes([nls[7], nls[10]])
rls[14].addNodes([nls[8], nls[9]])
rls[15].addNodes([nls[9], nls[10]])
rls[16].addNodes([nls[10]])