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;
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.
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.
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.)
You need to have 3 binary constraint matrices: one for Bill-Ann, one for Bill-Paul, and one for Ann-Paul.
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.
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.
You need to provide a solution to the CSP. The solution is 10am on Wednesday.
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.
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.