Information Technology Reference
In-Depth Information
In algorithm PBA* a
central control process
(CCP) is used to coordinate the local
search processes running concurrently. The CCP compares the search spaces with
respect to their estimated distances to the reference nodes and instructs two search
processes to start exchanging nodes when their search spaces seem to be intersecting.
As it is quite expensive to store
all
the reference nodes' distances for
all
nodes gener-
ated by each search space, the CCP uses an
overlap table
to store selected distances
for each reference node. Specifically, the overlap table holds only the minimum and
maximum distances to each reference node from each search space. Each search space
keeps track of its minimum and maximum values for each reference node, and in-
forms the CCP as these values change. The CCP receives the new values, updates the
overlap table, and checks if an overlap between a pair of opposite direction search
spaces has occurred. An overlap with respect to a reference node k occurs when
(
(
)
)
SR
min,
SR
max
∩
SR
min,
SR
max
≠ ∅
i
k
i
k
j
k
j
k
{
(
)
}
SR
min
=
min
dist n
,
R
j
k
S
k
j
and
(
)
{
}
SR
max
=
max
dist n
,
R
j
k
S
k
j
n
in
S
.
It happens that an intersection between two search spaces is not possible until such
an overlap occurs. Figure 6 is an example of an overlap table maintained by the cen-
tral control process when four search processes and four reference nodes are present.
The table shows that search processes S
1
(forward) and S
2
(reverse) overlap with
respect to all four reference nodes. In this case, the CCP will instruct search processes
S
1
and S
2
to start node exchange. In particular, the reverse search process S
2
is in-
structed to send nodes to the forward search process S
1
, and the forward search proc-
ess S
1
is given an alert that nodes from S
2
are to arrive.
for any node
j
Search
process
R1
R2
R3
R4
Min
Max
Min
Max
Min
Max
Min
Max
S1
(forward)
10
17
63
68
4
25
9
26
S2
(reverse)
14
27
43
65
13
31
18
40
S3
(forward)
4
7
11
19
4
12
4
19
S4
(reverse)
28
32
22
31
37
51
28
43
Fig. 6.
A sample overlap table
Search WWH ::
Custom Search