Database Reference
In-Depth Information
e
edge
u
v
v i−1
v
i
P 2
P 1
explored path
unexplored path
actual Pr w =x
P
Pr w =x |w =y
[
]
estimated
[
]
1
e
1
P 2
2
Fig. 8.4 P* search process.
The objective of P* is to find a good heuristic estimate h P 2 | e (
x 2 |
y
)
for f P 2 | e (
x 2 |
y
)
,
such that F P (
l
)
can be estimated before visiting v i . Then, the vertex with the higher
estimated F P (
l
)
is visited earlier. The estimated F P (
l
)
is used as a heuristic evalua-
tion function of vertex v i :
F P (
x 1 + y + x 2 l
Δ (
v i ,
l
)=
l
)=
f P 1 , e (
x 1 ,
y
) ×
h P 2 | e (
x 2 |
y
)
(8.8)
In order to answer a query Q l (
u
,
v
)
, P* starts from u . For any vertex v i adjacent
to u , P* calculates
and puts v i into a priority queue. Each time, P* removes
the vertex v i with the highest
Δ (
v i ,
l
)
Δ (
v i ,
l
)
from the priority queue. After v i is visited, the
Δ
scores of other vertices are updated accordingly. A path P is output if v is reached
and F P (
l
) τ
. The algorithm stops if the priority queue is empty, or the
Δ
scores of
the vertices in the priority queue are all smaller than
.
In order to guarantee that P* finds all answer paths, the heuristic evaluation func-
tion should satisfy the following requirement.
τ
Theorem 8.5 (Heuristic evaluation function). P* outputs all answer paths if and
only if for any path P
=
u
,...,
v i ,...,
v
,
Δ (
v i ,
l
)
F P (
l
)
.
Proof. If there is a path P such that
Δ (
v i ,
l
) < τ
F P (
l
)
. Then, P will not be returned
by P* but it is actually an answer path.
Δ (
v i ,
l
)
is called a valid heuristic evaluation function if
Δ (
v i ,
l
)
F P (
l
)
.
8.2.2 Heuristic Estimates
It is important to find a good heuristic estimate h P 2 | e (
x 2
|
y
)
so that the evaluation
function
. In this subsection, we first
present two simple heuristic estimates that satisfy Theorem 8.5. Then, we derive a
sufficient condition for valid heuristic estimates, and present a more sophisticated
heuristic estimate.
Δ (
v i ,
l
)
is valid and close to the real F P (
l
)
 
Search WWH ::




Custom Search