Geography Reference
In-Depth Information
Algorithm 5.2:
The landmark spider routing algorithm.
Data
: G D .V; E/: a directed graph, s 2 V : the start vertex; ": the set of outgoing edges
over all nodes;
w
W " !
R
C
: the weighting function.
Result
: c
s
W E !
R
C
: the minimal cost (clearest path) to all nodes from origin s.
1
S={} ;
/* The set of visited edges. */
2 forall the
e 2 E
do
3
c
s
.e/ 1;
/* Initialize the costs to reach an edge for all edges. */
4 forall the
.s;
v
i
/ 2 E
do
5
c
s
..s;
v
i
//
w
..s;
v
i
// ;
/* Initialize outgoing edges of
s
with their weight. */
6 while
jEnSj >0
do
7
e
min
min.c
s
.e/je 2 EnS/ ;
/* Find edge with minimal costs */
S S
S
fe
min
g ;
8
/* and visit it. */
forall the
e
0
2 EnS
do
9
if
.e; e
0
/ 2 "
then
10
c
s
.e
0
/ min.c
s
.e
0
/; c
s
.e
min
/C
w
.e
0
// ;
/* Update the costs to all non-visited
neighbors
e
0
of
e
.*/
11
while less relevant landmarks receive a higher weighting. That is, weights here serve
as a penalty; good landmarks mean low penalty. The according algorithm is listed
something similar. The algorithm is based on Richter's work on context-specific
the instructions, but also minimize the number of instructions. The overall aim is to
generate instructions that are memorizable and easy to follow. This is reflected in
the algorithm.
graph reflects movement options in a graph, i.e., it captures all possibilities to turn
from one edge onto another. Formally, this is the graph G
0
D
.E
0
;"/. E
0
is the set
of edges in G, where the direction of edges is ignored (i.e., .
v
i
;
v
j
/
D
.
v
j
;
v
i
/ in
E
0
). " is the set of pairs of vertices in E that share their middle vertex, i.e., "
D
f
..
v
i
;
v
j
/; .
v
j
;
v
k
//
2
E
E
g
. A pair of adjacent edges in E represents a decision
an agent can take to move from one edge to the next. Figure
5.15
illustrates these
definitions further.
Richter and Duckham's algorithm models the instructions required to describe
a route as a set I of instruction labels. Instructions are associated with decisions
(the pairs of adjacent edges). These instructions describe what to do in order to
move from one edge to another (e.g., 'turn right at this intersection'). Specifically
these instructions may contain references to landmarks ('turn right at the church').
There may be more than one instruction associated with a pair of edges, reflecting
alternative ways of describing the decision. And, likewise, the same instruction may
be associated with several pairs of adjacent edges—there may be many intersections
in the network where a right turn is possible. However, the algorithm assumes that
Search WWH ::
Custom Search