Information Technology Reference
In-Depth Information
Table 1. Results on the global and partial revision of random flooding instances
Global revision
Partial revision
Revision
Density
Density
0.2
0.5
0.8
0.2
0.5
0.8
n =500
# conflicts
61844
62110
62049
61543
62034
61851
# corrections
305
306
308
314
318
317
Time (s)
3
1
1
3
2
2
n
=1000
# conflicts
248277 249962 247737 248640 247275 247718
# corrections
619
622
619
635
633
632
Time (s)
25
14
9
33
21
16
n =2000
# conflicts 994792 993225 996207 998079 998293 993822
# corrections 1247
1244
1247
1264
1257
1269
Time (s)
202
109
75
306
228
187
interval [100,300] where the upper and lower bounds of the water height estimates
are generated. A sample of 50 problems is generated for each tuple ( n, d, t )and
the mesures are taken in average.
We can see in table 1 that the density does not affect significantly the number
of detected conflicts. However, when the density grows, the revision becomes
faster for both methods. This is due to the fact that when the density grows,
the conflicts share more constraints, and their elimination is faster. We can see
also that the number of corrected constraints in the global revision is always less
than the one in the partial revision .The global revision is also faster than the
partial revision . This is due to the minimal cover computing complexity.
6
Discussion
In a recent work [3], we have proposed different revision methods in the frame-
work of the flooding problem. The first one is the all conflicts method which
performs a minimal revision, but is applicable only to small instances of random
flooding problems. The global revision method proposed in this paper is more
ecient although it is not minimal. The partial revision outperforms the hybrid
revision method proposed in [3]. The heuristic which selects first the conflicts
having the smallest distances in each iteration, improves significantly the per-
formances of the method. In future, we will try to extend this work to revise any
problem expressed as a linear constraint network.
References
1. C. Alchourron, P. Gardenfors, D. Makinson, On the logic of theory change : Partial
meet functions for contraction and revision, Journal of Symbolic Logic 50 (1985)
510-530.
2. M. Garey, D. Johnson, Computers and Intractability: A Guide to the Theory of
NP-Completeness, W. H. Freeman and co., San Francisco, 1979.
Search WWH ::




Custom Search