Welcome! Log In Create A New Profile

Advanced

Mock Exam Q6 (Food Delivery)

Posted by Sanoz0r 
Announcements Last Post
Announcement SoC Curricula 09/30/2017 01:08PM
Announcement Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
Announcement School of Computing Short Learning Programmes 11/24/2014 08:37AM
Announcement Unisa contact information 07/28/2011 01:28PM
Mock Exam Q6 (Food Delivery)
November 10, 2008 06:10PM
This is my attempt at Q6.

========================================

Variables = {T, A, B, P}

Domain for all variables = {1, 2, 3, 4}

Constraints:
- Alldiff(T, A, B, P)
- A < P
- A < B
- T != 4

My solution to this CSP:

1. Arc consistency: remove 4 from A (because of A<P and A<B ) and 4 from T (T!=4).
- T: {1, 2, 3}
- A: {1, 2, 3}
- B: {1, 2, 3, 4}
- P: {1, 2, 3, 4}

2. MRV states we use T or A. The degree heuristic then tells us to use A (because it is highly constrained). The least-constraining value for A is 1. Arc consistency then removes 1 from P, B and T.
- T: {2, 3}
- A: 1
- B: {2, 3, 4}
- P: {2, 3, 4}

3. MRV states we assign T next since it has the fewest remaining values. Values 2 and 3 rule out the same values for the domains of B and P so the least-constraining-value heuristic cannot be used. The value 2 will be used because it is before 3 in the domain's value list. Arc consistency removes 2 from B and P.
- T: 2
- A: 1
- B: {3, 4}
- P: {3, 4}

4. The MRV and degree heuristics cannot distinguish between B and P (they are equally constrained and have the same number of legal values remaining). Hence, B will be used since it is first in the variable list. Value 3 will be used since it is first in the domain list. Arc consistency removes value 3 from P's domain.
- T: 2
- A: 1
- B: 3
- P: {4}

5. P = 4.
- T: 2
- A: 1
- B: 3
- P: 4
avatar Re: Mock Exam Q6 (Food Delivery)
November 12, 2008 10:42AM
i completely forgot about mrv & least constrained values, thanks for your solution!
Sorry, only registered users may post in this forum.

Click here to login