Information Technology Reference

In-Depth Information

S
and

S
overlap, but

SS

∩=∅

Fig. 7.

a

b

If the central control process uses an overlap table to decide when to turn on com-

munication between two searches, it can be assured that some existing intersection

will not be overlooked. Unfortunately, the existence of these overlaps does not insure

that the two search spaces contain a common node. The condition is not sufficient for

several reasons, one of which is that the heuristics only
estimate
distances to the ref-

erence nodes. However, even if the heuristic makes no errors in estimating distances,

there are still other reasons why this condition is not sufficient. As shown in Figure 7,

it may be that the approximated space of S
a
intersects with the approximated space of

S
b
without having any single node in (S
b
) S
a
overlap all the reference node ranges in

(S
a
) S
b
. The result of this is that no nodes lie in the intersection of the approximated

spaces [11]. Three different intersection detection algorithms, which increasingly

progressive degree of refinement, are outlined next.

(1)
IDA-1
maintains a [min, max] overlap table and when the approximated

spaces of S
f
and S
r
intersect, S
r
will begin sending its nodes to S
f
.

(2)
IDA-2
is based on addressing one of the reasons which keeps the overlap

condition, the basis of IDA-1, from being sufficient to insure that two spaces

intersect. IDA-2 waits until the reference node values of a single node in S
r

lie in the approximated space of S
f
. When this condition occurs, S
r
will then

begin sending its nodes to S
f
.

(3)
IDA-3
checks for the same condition as IDA-2 except that it does so on a node

by node basis. Both IDA-1 and IDA-2 end up turning on communication per-

manently. It may be that two search spaces only come close to intersecting for

a short period of time resulting to a lot of unnecessary node sending if com-

munication is permanently turned on. Instead, IDA-3 checks as each node is

generated and only sends nodes which lie in the approximated space of S
f
.

As mentioned earlier, we adopt IDA-3 for our evaluation. Our experiments reveal the

following.

Search WWH ::

Custom Search