基于神经网络预测的时间A*算法研究复现
1. 论文阅读及信息提取
1.1 构建路网拓扑
-
赋权有向图
-
交叉路口作为图的顶点，道路作为图中的边，需要存储拓扑信息：
-
[节点类型] N 表示路口，R 表示道路
-
[节点索引] 每条道路和每个路口顶点的索引值
-
[路口节点N]
-
[权值] 存储通行方向和对应预测的通行时间
-
addNodes添加相邻道路节点R -
addInters添加相邻路口节点N，及方向——
-
-
[道路节点R]
- [权值] 存储道路长度
-
addNodes添加相邻路口节点N
-
-
论文给出一个由双向道路 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
- 节点 n 到目标节点的曼哈顿距离
算法过程
-
设置起始节点（
N0），目标节点[N/R]（N9），出发时刻t -
获取
t时刻 起始节点（N0）所有的相邻路口节点的预测通行时间，计算代价函数，选取最佳的邻接路口节点进行更新 -
计算到达下一节点的道路行驶时间，与该节点预测通行时间和为
t1，更新时刻为t+t1 -
获取
t+t1时刻 更新节点 所有的相邻路口节点的预测通行时间，重复 2-4 步 -
目标节点
-
目标节点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]])