Database Reference
In-Depth Information
Definition 8.2 (Stochastic dominance).
For two paths
P
1
and
P
2
,
P
1
stochastically
dominates
P
2
,if
w
P
1
, the weight or
P
1
, is smaller than
w
P
2
, the weight of
P
2
,in
stochastic order.
P
opt
stochastically dominates
all paths in
P
2
,if
w
P
opt
is smaller than any
w
P
i
(1
m
) in stochastic order. An example is shown in Figure 8.5(b).
P
opt
stochas-
tically dominates
≤
i
≤
. The following theorem shows that
P
opt
can be used to
define a valid heuristic evaluation function.
B
,
D
,
E
Theorem 8.6 (Sufficient condition).
Let
P
=
{
P
2
1
,...,
P
2
m
}
be all paths between
2
v
i
and v in graph G. For a path P
opt
=
v
i
,...,
v
,ifP
opt
stochastically dominates all
paths in
P
2
, then
∑
Δ (
v
i
,
l
)=
f
P
1
,
e
(
x
1
,
y
)
×
f
P
opt
(
x
2
)
x
1
+
y
+
x
2
≤
l
is a valid heuristic evaluation function for P*.
Proof.
Compare two paths
P
P
opt
and
P
=
=
P
1
+
P
1
+
P
2
i
(
P
2
i
∈P
2
).
]=
x
≤
l
Pr
[
w
P
1
=
x
]
×
Pr
[
w
P
opt
≤
l
−
x
]
Pr
[
w
P
≤
l
w
P
≤
]=
x
≤
l
Pr
[
w
P
1
=
x
]
×
Pr
[
w
P
2
i
≤
l
−
x
]
Pr
[
l
w
P
≤
Since
Pr
[
w
P
opt
≤
l
−
x
]
≥
Pr
[
w
P
2
i
≤
l
−
x
]
,wehave
Pr
[
w
P
≤
l
]
≥
Pr
[
l
]
.
More than one
P
opt
can be constructed. Here we present a simple three-step con-
struction method that ensures the resulting path is a stochastically dominating path
for
P
2
.
Step 1: Constructing the path
We find the path
P
2
i
2
with the least number of edges. Let
n
be the num-
ber of edges in
P
2
i
. We construct
n
in
P
−
1 virtual vertices
v
1
,...,
v
n
−
1
. Let
P
opt
=
v
i
,
v
1
,...,
v
n
−
1
,
v
. Thus,
P
opt
has the least number of edges among all edges in
P
2
.
For example, in the probabilistic graph in Figure 2.6, there are two paths between
B
and
E
:
P
1
=
B
,
E
and
P
2
=
B
,
D
,
E
. Since
P
1
only contains one edge, the path
P
opt
should also contain only one edge.
Step 2: Assigning edge weights
Let
P
2
. We want to construct the weight of an edge
e
opt
in
P
opt
such that
e
opt
stochastically dominates all edges in
E
be the set of edges in
E
.
