CEN535435 CEN660 Introduction to Artificial Intelligence
Homework 2
Instructions
In this homework you will use Python to implement heuristic graph search and A graph search we have covered in class, also the minimax tree search and alphabeta pruning. Implementing these algorithms in program code is important, as these advanced search and planning methods are widely applied in various of AI applications and video games.
The homework should be done in Python Python 3.X is recommended. Include a documentation in .doc or .pdf format that describes the complete steps of your solutions for each problem including: 1 The answer to any questions posed, 2 any results include print outs or terminal outputs, and 3 the name of any Python modules and functions Numpy, Matplotlib, etc. you used. Discussion is allowed, but you must submit your own writeup and list your collaborators.
Zip all your documents with the source code .py files, if there are selfimplemented modules, organize them in different folders, documentation, and data image files, text, etc. into a file called LastnameFirstInitialHomework2.zip and upload it to the Blackboard prior to the due date.
Make sure your code works when you send it out.Please use as less thirdparty libraries as possible cause it is easy for instructors to reproduce your results. If you used the libraries that requires installation, please list the dependencies and its version in your README file or using pip to generate the dependency list like pip freezerequirements.txt.
For late assignments, you will receive 10 off per day on any assignment handed in late up to a week. However, after a week on any given homework you will receive no credit for the assignment. So please start your assignment ASAP.
Homework Description
Informed search 10pt
Refer to the weighted undirected graph and heuristic function h with values shown in the figure, where h indicates the heuristic estimation of how close the current state is to the goal. Answer following questions:
1 Write code to find the shortest path from S to G using greedy search. Similar to HW1, your code should return the search state expended and the path with lowest cost. Manually exam the results to see if they are correct. 4pt
2 Write code to find the shortest path from S to G using A search. Similar to HW1, your code should return the search state expended and the path with lowest cost. Manually exam the results to see if they are correct. 4pt
3 In this graph with heuristic h, is h admissible? Please answer and explain your answers in the documentation. 1pt
4 In this graph with heuristic h, is h consistent? Please answer and explain your answers in the documentation. 1pt
Note:
implement 1, 2 in Python. Put the source code in a folder named code and record results in your documentation like hw2solution.doc or .pdf.
You can either use recursion or stack implementation, and either adjacency matrix or linked list implementation.
A heuristic h is admissible optimistic if: , whereis the true cost to a nearest goal.
Consistency: heuristic arc costactual cost for each arc
hAhCcostA to C
Constraint satisfaction problems 5pt
Consider a constraint satisfaction problem CSP: coloring the given graph with only two colors black, white i.e. binary constraint. Thus, adjacent nodes must have different colors. Initially, no states have been assigned.
For each of the following scenarios, list all variables that will be changed after the specified changes or conditions. Explain how you obtain your answer in your documentation. This is a written assignment, so no coding is involved in this problem.
1 pt After a value is assigned to A, which domains might be changed after forward checking for A?
1 pt After a value is assigned to A, then forward checking is run for A. Then a value is assigned to D. Which domains might be changed as a result of running forward checking for D?
1 pt After a value is assigned to A, which domains might be changed as a result of enforcing arc consistency after this assignment?
1 pt After a value is assigned to A, and then arc consistency is enforced. Then a value is assigned to D. Which domains might be changed after enforcing arc consistency after the assignment to D?
1 pt Is there a valid solution for assigning colors to all graph nodes? Why?
Adversarial search 15 pt
Below is a minimax game search tree, the leaf nodes contain terminal values.
represents the max node. represents the min node.
5 pt Implement the minimax search in Python. Use the above tree as input and return the chosen terminal state. Print the output value and output path.
2 pt Manually complete the minimax search tree by filling the nonleaf node. What is the output value and output path?
5 pt Implement alphabeta pruning for the minimax tree search. Apply pruning from the leftmost to the rightmost. Return the chosen terminal state.Print the output value.
3 pt Show the terminal states of the minimax tree that has been pruned by alphabeta pruning. List explicitly which leave nodes or subtrees are pruned. Explain the pruning process and the value of alpha and beta there. Do we obtain the output path from the alphabeta pruning?
Hint: This question involves both coding and handwritten answers. For the coding part, you should build a tree data structure to store the value and minmax operation flag for each node.
Sample code to implement binary tree with Python
class BinaryTree:
def initself,rootid:
self.leftNone
self.rightNone
self.rootidrootid
self.valuevalue
def getLeftChildself:
return self.left
def getRightChildself:
return self.right
def setNodeValueself,value:
self.valuevalue
def getNodeValueself:
return self.value
def insertRightself,newNode:
if self.rightNone:
self.rightBinaryTreenewNode
else:
treeBinaryTreenewNode
tree.rightself.right
self.righttree
def insertLeftself,newNode:
if self.leftNone:
self.leftBinaryTreenewNode
else:
treeBinaryTreenewNode
tree.leftself.left
self.lefttree
def printTreetree:
if tree ! None:
printTreetree.getLeftChild
printtree.getNodeValue
printTreetree.getRightChild
def testTree:
myTreeBinaryTreel0
myTree.insertLeftl10
myTree.insertRightl11
l10myTree.getLeftChild
l10.insertLeftl20
l10.insertRightl21
l11myTree.getRightChild
l11.insertLeftl22
l11.insertRightl23
printTreemyTree
Reviews
There are no reviews yet.