AC-1 procedure AC-1 (G) begin Q = f(i; j) (i; j) 2 arc(g), i 6= jg repeat begin CHANGE = false for each (i; j) 2 Q do CHANGE = REVISE((i; j)) _ CHANGE

Size: px

Start display at page:

Download "AC-1 procedure AC-1 (G) begin Q = f(i; j) (i; j) 2 arc(g), i 6= jg repeat begin CHANGE = false for each (i; j) 2 Q do CHANGE = REVISE((i; j)) _ CHANGE"

さやしばもと
5 years ago
Views:

1 AC-5, May 7, 2003 Lecture 3-1, (Local Consistency) 4 1. (Node Consistency) 2. (Arc Consistency) 3. (Path Consistency) m (m-consistency) 4. AC-1 AC-2 (Waltz, ) AC-3 AC-4

2 AC-1 procedure AC-1 (G) begin Q = f(i; j) (i; j) 2 arc(g), i 6= jg repeat begin CHANGE = false for each (i; j) 2 Q do CHANGE = REVISE((i; j)) _ CHANGE until : CHANGE AC-1,, May 7, 2003 Lecture 3-2

3 for each v 2 D i REVISE ArcCons procedure REVISE ((i; j)) begin DELETE = false do if C ij (v,u) u 2 D j then begin Remove(x; D i ) DELETE = true return DELETE REVISE,, May 7, 2003 Lecture 3-3

4 REVISE C ij =) AC-1 O(ed 3 ) AC-1 O(d 2 ) repeat jqj = 2e repeat, 1 1., repeat d.,, May 7, 2003 Lecture 3-4

5 begin i = 1 to n do for = f(i; j) (i; j) 2 arc(g), i < jg Q = f(h; i) (h; i) 2 arc(g), h < ig Q' not EmptyStack(Q) do while not EmptyStack(Q) do while REVISE((k; m)) then if 0, f(p; k) (p; k)2arc(g),pi; p6=mg) push(q = Q 0 ; Q 0 = empty Q AC-2 procedure AC-2 (G) (k; m) = pop(q),, May 7, 2003 Lecture 3-5 AC-2

6 AC-2 AC-2 O(ed 3 ) Waltz ( ) (Constraint propagation) (symbolic relaxation method),, May 7, 2003 Lecture 3-6

7 Waltz, Convex edge Concave edge Boundary, with "stuff" on the right,, May 7, 2003 Lecture 3-7

8 [Winston],, May 7, 2003 Lecture 3-8

9 2 J1 L6 J6 L1 L5 J2 L7 L9 J5 L2 L8 J7 L4 J3 L3 J4 J8 L8 J7 J1 L1 J10 J11 L15 L13 L14 L12 J5 L7 L6 L5 J6 L2 L9 L11 J9 L10 L4 J4 J2 L3 J3,, May 7, 2003 Lecture 3-9

10 {1,3} {+,>},, May 7, 2003 Lecture 3-10

11 {1,3} {+,>} {2,3,4} {+,>} {+,-} {+,-} {+,>} {2,3,4} {+,>} {1,3} {1,3} {+,-} {1,2} {+,>} {2,3,4} {+,>} ,, May 7, 2003 Lecture 3-11

12 {2,3,4} {+,>},, May 7, 2003 Lecture 3-12

13 {2,3,4} {+,>} {+,>} {1,3} {1,3} {+,>} {2,3,4} {2,3} {1,2} {+,-} {+,-} {+,-} {+,-} {+,-} {+,>} {+,>} {+,>} {1,3} {1,3} {+,-} {+,>} {1,3} {2,3,4} {+,-} {+,>} ,, May 7, 2003 Lecture 3-13

14 AC-3 procedure AC-3 (G) begin Q = f(i; j) (i; j) 2 arc(g), i 6= jg while not EmptyQueue(Q) do begin (k; m) = pop(q) if REVISE((k; m)) then Q = Q [ f(i; k) (i; k)2arc(g),i6=k;i6=mg AC-3,, May 7, 2003 Lecture 3-14

15 nx d(e k 0 1) = d(2e 0 n) k=1 AC-3 AC-2, AC-3 REVISE k e k e 0 1 k Q. repeat 1 Q,, 2e + d(2e 0 n), d 2 C ij =) AC-3 O(ed 3 ) REVISE =) (ed 2 ),, May 7, 2003 Lecture 3-15

16 AC-5 AC-5 (generic) ArcCons LocalArcCons AC-3 AC-4 { (functional constraints) { (anti-functional constraints) { (monotonic constraints) { (piecewise functional constraints) { (piecewise anti-functional...) (piecewise monotonic constraints) {, May 7, 2003 Lecture 3-16,

17 i, May 7, 2003 Lecture 3-17, AC-5 Queue AC-5 ((i, j), w) queue. (i, j), w D j (i, j).. Enqueue(j, 1, Q) (i, j) w 2 1 queue Q ((i, j), w). k j C ij D j 1

18 ArcCons LocalArcCons function ArcCons(i,j ) Returns 1 = fv 2 D i j 8u 2 D j :C ij (v; u)g D i 1 (i,j ) consistent D j w function LocalArcCons(i,j,w) Returns 1 s.t where 1 1 = fv 2 D i j C ij ^ 8u 2 D j :C i;j (v; u)g 1 2 = fv 2 D i j 8u 2 D j :C i;j (v; u)g,, May 7, 2003 Lecture 3-18

19 AC-5 procedure AC-5 (G) InitQueue(Q) for each (i; j) 2 arc(g) do 1 = ArcCons(i, j ) Enqueue(i; 1; Q) Remove(1; D i ) while not EmptyQueue(Q) do ((i; j), w) = Dequeue(Q) 1 = LocalArcCons(i, j, w) Enqueue(i; 1; Q) Remove(1; D i ) AC-5, May 7, 2003 Lecture 3-19,

20 { InitQueue Status((k, i), v) = present if v 2 D i AC-5 Status((k, i), v) AC-5 queue \(edge, value)", Status rejected otherwize { EnQueue queue Status = susped { DeQueue queue Status = rejected = present i v 2 D i = susped i v =2 D i ((k, i), v) Q = rejected i v =2 D i ((k, i), v) Q AC-5 enqueue dequeue O(ed) =), May 7, 2003 Lecture 3-20,

21 ArcCons O(d 2 ) =) AC-3 enqueue dequeue O(ed 3 ) AC-3 AC-3 AC-5., LocalArcCons ArcCons,, May 7, 2003 Lecture 3-21

22 ArcCons:O(d 2 ), LocalArcCons:O(d) ) AC-5: O(ed 2 ) AC-4 j 2 u u fug i 2 v v fu; vg 1 w w fv; wg edge O(d 2 ) O(d 2 ) edge O(d) O(d 2 ) LocalArcCons(i; j; w) edge (i; j) w 1., 0 1. ArcCons:O(d 2 ), LocalArcCons:O(d) ) AC-4: O(ed 2 ) =), May 7, 2003 Lecture 3-22,

23 for each v 2 D i f ij (v) =2 D j then 1 = 1 [ fvg if 1 return return fg else LocalArcCons (functional constraints) C D i 8v 2 D fw 2 DjC(v; w)g w 1 ArcCons(i,j ) function = fg 1 bf do ArcCons O(d) ArcCons O(1) LocalArcCons LocalArcCons(i,j,w) AC-5 O(ed) function f ij (v) 2 D j then return ff ij (w)g if,, May 7, 2003 Lecture 3-23

24 3 AC Word List AFT HEEL HOSES 4 5 ALE HIKE SAILS 6 7 EEL KEEL LASER 8 LEE LINE SHEET TIE KNOT STEER,, May 7, 2003 Lecture 3-24

1. A0 A B A0 A : A1,...,A5 B : B1,...,B

1. A0 A B A0 A : A1,...,A5 B : B1,...,B12 2. 3. 4. 5. A0 A B f : A B 4 (i) f (ii) f (iii) C 2 g, h: C A f g = f h g = h (iv) C 2 g, h: B C g f = h f g = h 4 (1) (i) (iii) (2) (iii) (i) (3) (ii) (iv) (4)