Information Technology Reference
In-Depth Information
Algorithm 1.
Estimate future edge weights
1:
for all
(
v ∈ N
)
do
2:
w
t
← f
(
v,t
)
.w
w
t−
1
← f
(
v,t
t−
1
)
.w
3:
if
(
f
(
v,t
)
.e
==
f
(
v,t
t−
1
)
.e
)
then
4:
5:
Δw ← w
t
− w
t−
1
w
est
← w
t
+
Δw
6:
7:
else
w
t−
1
← f
(
v,t
t−
1
)
.e.w − f
(
v,t
t−
1
)
.w
8:
9:
Δw ← w
t
+
w
t−
1
w
est
← w
t
+
Δw
10:
11:
end if
if
(
w
est
> f
(
v,t
)
.e.w
)
then
12:
13:
E
← g
(
v
)
14:
for
(
i ←
0;
i<E.length−
1;
i
++)
do
if
(
E
[
i
]==
f
(
v,t
)
.e
)
then
15:
16:
v.e ← E
[
i
+1]
17:
v.w ← w
est
− E
[
i
]
.w
18:
end if
19:
end for
20:
else
21:
v.w ← w
est
22:
end if
23:
end for
in
N
for
P
based on the heuristics computed in the steps before or restart the algorithm
on the vertex until we have have reached a vertex close to destination vertex
d
.
Estimating Future Weights.
The procedure for estimating future weights is given in
Algorithm 1. Since
f
updates
N
only in specific intervals and the topology of
G
changes
very quickly we try to estimate the topology of the neighboring vertices in
G
.Theidea
is to query
f
on the edge weights of all vertices contained in
N
at time
t
and
t −
1
.We
then use the delta of the two weights and add it to the current weight of a vertex in
N
.
We have to distinguish two cases here: (1) At time
t
and time
t
t−
1
vertex
v
maps to the
same edge in
G
, (2) At time
t
and time
t
t−
1
vertex
v
maps to different edge in
G
(line
4). This influences how
Δw
is calculated (lines 5 - 10).
If the estimated edge weight is larger than the weight of the currently assigned edge
of
v
we do not only estimate the weight, we also set the future assigned edge of
v
using
g
.
We store the updated values directly in
v
.
N
.
Algorithm 2 shows how the
first heuristic is computed for selecting the next vertex for
P
. The idea here is to use
w
in order to identify the vertex
v
Heuristic 1: Edge Weights between
v
∈
P
and
v
∈
N
with minimum weight to a vertex
v
P
.Itis
obvious to prefer these edges for
P
since they come close to the initial found path
P
.
∈
∈
