Database Reference
In-Depth Information
We construct
w
e
opt
as follows. At the beginning, we set
w
e
opt
=
0. Then, we rep-
resent each sample
x
. We sort all samples in the
value ascending order. If there are two samples with the same value, we only keep
the sample with the larger cumulative probability. In the next step, we scan the sam-
ples in the sorted list. If
w
e
opt
=
∈
w
e
(
e
∈ E
) as a pair
(
x
,
F
e
(
x
))
0, then we add the current sample
(
x
,
F
e
(
x
))
into
x
,
x
))
be the sample with the largest value
x
in
w
e
opt
.
w
e
opt
. Otherwise, let
(
F
e
opt
(
x
and
F
e
x
)
(
,
(
))
>
(
)
>
F
e
opt
(
We add the current sample
x
F
e
x
into
w
e
opt
if
x
x
. Last,
we assign weight
w
e
opt
to each edge
e
i
∈
≤
≤
P
opt
(1
i
n
).
Example 8.5 (Assigning edge weights). Consider the probabilistic graph in Fig-
ure 2.6. There are two paths between B and E: P
1
=
B
,
E
and P
2
=
B
,
D
,
E
.
E
=
{
BD
,
DE
,
BE
}
. The probability mass function of the constructed weight w
e
opt
is
.w
e
opt
is smaller than w
BD
,w
DE
and w
BE
in
stochastic order. The weight cumulative distribution functions of those edges are
shown in Figure 8.5(a).
{
5
(
0
.
2
)
,
10
(
0
.
1
)
,
20
(
0
.
6
)
,
30
(
0
.
4
)
}
Step 3: Assigning the path weight
w
P
opt
= ∑
1
≤
i
≤
n
w
e
i
. The distribution of
w
P
opt
depends on the marginal distribution of
w
e
i
and the correlations among
w
e
i
's. If the correlations among edges are explicitly
represented, then we just construct
w
P
opt
according to the correlation function.
In most cases, the correlation functions among weights are not available. There-
fore, we want to construct a path weight
w
P
opt
that stochastically dominates all pos-
sible weights given the same
w
e
1
,...,
w
e
n
, as defined in the following rule.
Lemma 8.5 (Upper bound).
For path P
opt
containing edges e
1
,...,
e
n
, let x
min
i
≤
i
≤
n
x
min
be the smallest sample of weight w
e
i
, and l
min
=
∑
. Then, F
P
opt
(
l
)
≤
1
i
x
min
i
min
1
≤
i
≤
n
{
.
Proof.
The lemma follows with Lemma 8.1 directly.
F
e
i
(
l
−
l
min
+
)
}
Therefore, for any value
l
, we assign
x
min
F
P
opt
(
l
)=
1
≤
i
≤
n
{
min
F
e
i
(
l
−
l
min
+
)
}.
i
The heuristic evaluation function is
∑
x
1
+
y
+
x
2
≤
l
Δ (
v
i
,
l
)=
f
P
1
,
e
(
x
1
,
y
)
×
f
P
opt
(
x
2
)
.
Example 8.6 (Assigning path weights). Continuing Example 8.5, since P
opt
only
contains one edge, the probability distribution of P
opt
is the same as that of e
opt
.
As another example, suppose P
opt
contains two edges e
1
and e
2
with the same
weight w
e
opt
. How can we calculate the probability distribution of P
opt
? The sum
of minimal samples of w
e
1
and w
e
2
is
10
. Then, F
P
opt
(
20
)
is
min
{
F
e
1
(
20
−
10
)=
0
.
3
,
F
e
2
(
20
−
10
)=
0
.
3
}
=
0
.
3
. The cumulative distribution function of P
opt
is shown
in Figure 8.5(b).
