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

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

1. 论文阅读及信息提取

1.1 构建路网拓扑

  1. 赋权有向图

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

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

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

    • [路口节点N]

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

      • addNodes 添加相邻道路节点R

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

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

    • [道路节点R]

      • [权值] 存储道路长度
      • addNodes 添加相邻路口节点N
  3. 论文给出一个由双向道路 R0-R16 和交叉路口 N0-N10 构成的简单路网示例

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

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

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

*父类Node

论文中JAVA实现

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

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的变量类型。

  • 为不可变类型时基于神经网络预测的时间A算法研究复现

  • 为可变类型时基于神经网络预测的时间A算法研究复现

  • 解决方法

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

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权值)的计算分析

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

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

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

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

参数说明:

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

*获取计算预测时间函数

Python实现

def getFlow(t):
    pass

def calcTime():
    pass

1.3 路径规划算法A*

算法分析

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

  • 综合代价 fn(t) :

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

  • 实际代价 gn(t)

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

  • 估计代价 hn(t)

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

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

    • 节点 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]])
上一篇:oracle实现汉字按照拼音、笔画和部首排序


下一篇:sql常见函数积累