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
)