Database Reference
In-Depth Information
f
P
m
(
x
)=∑
y
≤
x
f
e
m
(
y
)
×
f
P
m
|
e
m
(
x
|
y
)
(8.2)
Proof.
P
m
contains subpath
P
m
−
2
and edges
e
m
−
1
and
e
m
, as illustrated in Figure 8.2.
Therefore,
f
P
m
|
e
m
(
|
)=
[
w
P
m
−
1
=
−
|
w
e
m
=
]
x
y
Pr
x
y
y
= ∑
y
Pr
[
w
P
m
−
2
=
z
1
,
w
e
m
−
1
=
z
2
|
w
e
m
=
y
]
z
1
+
z
2
=
x
−
Using the basic probability theory,
Pr
[
w
P
m
−
2
=
z
1
,
w
e
m
−
1
=
z
2
|
w
e
m
=
y
]
=
[
Pr
w
e
m
−
1
=
z
2
|
w
e
m
=
y
]
Pr
[
w
P
m
−
2
=
z
1
|
w
e
m
−
1
=
z
2
]
Since
z
1
+
z
2
=
x
−
y
,wehave
Pr
[
w
P
m
−
2
=
z
1
|
w
e
m
−
1
=
z
2
]=
Pr
[
w
P
m
−
1
=
x
−
y
|
w
e
m
−
1
=
z
2
]
Thus, Equation 8.1 holds. Equation 8.2 follows with the basic principles of prob-
ability theory.
, the probability function of
w
P
m
can be calculated
from
w
P
m
−
1
and
w
e
m
using Theorem 8.1. Calculating the probability mass function
of
P
m
requires
O
For a path
P
m
=
v
1
,...,
v
m
+
1
(
|
w
P
m
−
1
|·|
w
e
m
|
)=
O
(
∏
P
m
|
w
e
|
)
time.
e
∈
is required, we do not need to use all samples in an
edge weight. The largest sample we can take from
w
e
i
Interestingly, if only
F
P
m
(
l
)
(
1
≤
i
≤
m
)
is bounded by
the following rule.
Lemma 8.1 (Sample
components).
For weight
threshold
l
and
path
P
can be a com-
ponent of a sample of P in the l-weight constrained region only if x
i
j
≤
=
v
1
,...,
v
m
+
1
, a sample x
i
j
of edge e
i
=(
v
i
,
v
i
+
1
)(
1
≤
i
≤
m
)
l
−
∑
i
=
i
x
i
1
,
where x
i
1
.
Proof.
Since one and only one sample should be taken from each edge in a possible
world, the sum of the minimal sample from each edge in
P
is the smallest weight of
P
. Thus, the conclusion holds.
is the smallest sample of edge e
i
=(
v
i
,
v
i
+
1
)
8.1.2 Approximating l-Weight Probabilities
The probability mass function of
F
P
m
+
1
(
l
)
can be calculated from the distributions on
f
e
m
+
1
according to Theorem 8.1. To accelerate probability calculation,
we introduce an approximation method that keeps a constant number of samples in
the weight distribution of any subpath during the search.
If
w
P
m
contains
n
f
P
m
|
e
m
and
f
e
m
|
x
n
(
t
is a user defined parameter), then we
divide those values into
b
exclusive buckets
>
2
t
samples
x
1
,···,
φ
i
=[
x
z
i
,
x
z
i
]
, where
z
k
−
1
+
z
1
=
1
,
z
k
=
1
,
for 1
<
k
≤
b
;
1
t
},
(8.3)
z
i
=
max
j
z
i
{
j
|
F
P
m
|
e
m
(
x
j
|
y
)
−
F
P
m
|
e
m
(
x
z
i
|
y
)
≤
for 1
≤
i
≤
b
≥