Lost points codes:

Breadth First - 
1.1	SAFCG 	Checked for the goal after when the node was added
		instead of when the node was expanded -4
1.7	SAFCFG	Forgot F has a child A

Branch & Bound -

1.2	SACFDHFG did not use dynamic programming
1.6	SAFCDC	 Out of order but using dynamic programming	

Greedy
1.8	SACDG	Use best h(n) not the arc distance

A*
1.3	SACG 	did not expand in alphabetical order
1.5	SAFCDG	Included child nodes in the decision before adding to the queue

Hill Climbing	
1.4	SACG	Moved to A first instead of F

 2.1 Net
     Wrong means if the greedy search does output optimal PATH (not
     EXPANED nodes).

 2.2 Greedy Search
     This problem depends on the the net provided in previous question. 

 2.3 Path
     Greedy search does generate optimal path;
     Assert path = EXPANDED nodes;
     Assert optimal path = shortest path.

 3.1 Min_Max
     Just show choice but no explanation;
     Choice is wrong but some value are assigned correctly;
     Choice is correct but few value mistakes.
     
 3.2 A-B Pruning
     Miss-skip specific node(s);
     Miss-skip a specific branch;
     Skip node(s) that should be evaluated;

Note 5.1a:

            The off-diagonal matrix elements should be zero, because “there are binary constraints between each two persons denoting the fact that the time scheduled for the meeting must be the same one for all persons.”  This is equivalent to a “binary equals” constraint between every pair of people.

 

Note 5.1b:

            Each element of a matrix should represent a value pair, that is, an assignment of values to each of the two variables.  Therefore, each binary constraint matrix should be a 4 x 4 matrix, because there are 4 values, and 16 possible value pairs.

 

Note 5.1c:

            You need to show the constraint net, with nodes, edges, and labels.  There should be 3 nodes (labeled Bill, Ann, and Paul), and 3 edges.  (It’s a fully connected net of 3 nodes.)

 

Note 5.1d:

            You need to have 3 binary constraint matrices:  one for Bill-Ann, one for Bill-Paul, and one for Ann-Paul.

 

Note 5.1e:

            You need to represent the unary constraints in the binary constraint matrices.  Just 1’s on all the diagonals would mean that the only constraint is that they all meet at the same time, but they could meet at any time.

 

 

 

Note 5.2a:

            What you describe is simply the representation of the constraints in the binary constraint matrices.  Arc consistency checking takes place after the constraints have been represented in the matrices, and can let you remove values from the domain of a variable even if there were no given constraints that would preclude using that value.  (OR)  You describe values being removed from the domain of the variables, but don’t say why or how.  (OR)  You described a method of arc consistency checking that will not result in a fully consistent set of matrices, e.g. you make consistency updates, but don’t check them for consistency again.

 

Note 5.2b:

            You need to provide a solution to the CSP.  The solution is 10am on Wednesday.

 

Note 5.2c:

            What you describe is the search through the constraint net for a solution.  Arc consistency checking takes place before the search begins.  Immediately after the constraints have been entered into the BCMs, the BCMs themselves might be in a state that is inconsistent with each other.  The arc consistency checking resolves this problem.

It’s an understandable error because there is consistency checking during the search, but it is the consistency of variable assignments, not constraint matrices.  However, the difference is very important.  If you discover an inconsistency of variable assignments during the search, you simply backtrack and make different assignments.  You do NOT reduce the domain of the variables, because the assignment may be consistent with some other combination of assignments for all other variables.  This is very different from arc consistency checking, where you are oscillating between reducing the domain of variables, and reflecting the reductions in the BCMs.

 

Note 5.2d:

            You need to describe how you chose the ordering of the variables (NOT values, and not BCMs).  This is the order that the variables are assigned values (visited).  In particular, the ordering of variables based on how constrained each variable is, and you first choose the variable that is most constrained, and each consecutive variable is the most constrained of the unassigned variables.

 

 

 

 

 

 

 

 

 

 

 

 

 

.