Table 4.1
River-Crossing Process
Trip Number | Starting Bank | Travel | Ending Bank |
Start | A a B b C C | ||
1 | A B C c | a b → | |
2 | A B C c | ← a | b |
3 | A B C | a c → | b |
4 | A B C | ← a | b c |
5 | A a | B C → | b c |
6 | A a | ← B b | C c |
7 | B b | A a → | C c |
8 | B b | ← C c | A a |
9 | b c | B C → | A a |
10 | b c | ← a | A B C |
11 | b | a c → | A B C |
12 | b | ← a | A B C c |
13 | a b→ | A B C c | |
Finish | A a B b C c |
Where X is a domain or a set of nodes of graph G. D is a set of edges in G. A is a subset of premises, p is a goal, is a reasoning function defined on A. T is a semi-order structure. F: is a function called a reasoning rule.
where, G1 and G2 are arbitrary combination functions of their arguments. The range of g1 is .
(4.1)
(4.2)
Since , we have . Namely
Again,
(4.3)
(4.4)
(4.5)
where the range m is all basic probability assignments which satisfy (4.3).(4.6)
(4.7)
(4.8)
(4.9)
(4.10)
(4.11)
where and are weights (constants).
(4.12)
(4.14)
(4.15)
Where, the first sum is only over all j in , the second sum is only over all i in .(4.18)
Where, the sum is over all .Table 4.2
Total CPU Time (in seconds) in Random Networks
Number of Nodes | 100 | 200 | 300 | 400 | 500 |
Our method | 0.939 | 1.356 | 3.112 | 6.634 | 12.171 |
Dijkstra | 1.719 | 9.797 | 91.141 | 565.391 | 1002.125 |
Floyd | 0.940 | 4.220 | 118.630 | 212.030 | 511.560 |
Table 4.3
Total CPU Time (in seconds) in Small-World Networks
Number of Nodes | 100 | 200 | 300 | 400 | 500 |
Our method | 0.640 | 2.403 | 6.659 | 14.330 | 22.262 |
Dijkstra | 2.758 | 10.546 | 87.239 | 700.540 | 1100.200 |
Floyd | 0.790 | 4.783 | 132.743 | 230.412 | 498.317 |
Table 4.4
Total CPU Time (in seconds) in Scale-Free Networks
Number of Nodes | 100 | 200 | 300 | 400 | 500 |
Our method | 0.437 | 1.734 | 4.297 | 8,187 | 15.562 |
Dijkstra | 2.045 | 8.236 | 86.431 | 668.400 | 998.354 |
Floyd | 0.780 | 4.060 | 108.598 | 206.580 | 466.250 |