AI算法代写 | CSCI4511 | Artificial Intelligence | final project

CSCI4511 Introduction to Artificial Intelligence, Fall 2018

Make-Up Take Home Exam

1. The runtime bound of DFS is in terms of maximum branch depth O(b^m), whereas the runtime bound of BFS is in terms of minimum solution depth O(b^d).  For aand b,consider a problem in which m is significantly larger than d. 
   1. Identify specific conditions of the problem and/or search tree under which DFS finds a solution faster given m >> d.
   2. Identify specific conditions under which DFS is slower given m >> d.
   3. Why is it that for Sudoku and KenKen, there is no difference in the worst-case runtime of BFS and DFS? Which would you recommend using for either Sudoku or KenKen and why?
2. Run the A* algorithm (graph version) on the following graph to find the shortest path. You start at “D” and the goal is “J”. Show your work by providing the frontier at each time step. The frontier should be in sorted order based on node values (show those values too). Is this heuristic admissible? Is it consistent?

2. Throughout the semester, you implemented a variety of problem solving techniques including search and CSP. Explain why using constraint satisfaction (i.e. AC3 with Backtracking Search) to solve KenKen would be preferred over classic search, such as BFS or DFS, discussing both the implementation and the impact on search time and space.

3. The ability to evaluate a given state or solution plays a significant role in many problem solving strategies. Describe the intent and impact that a good evaluation function can have on a search strategy, contrasting this with a “bad” evaluation function. Discuss this in the context of two of the following algorithms:  A*, Adversarial Search, Hill-Climbing, Genetic Algorithm, Simulated Annealing. Pick TWO of the algorithms to discuss.

4. Consider creating AI to compete against a human in a game of checkers (or chess) using adversarial search. Answer the following. There is not a right answer to these questions.

• Give 3 characteristics of a boardin checkers (or chess) that could be used in the evaluation function for CUTOFF search, stating whether each is negatively or positively weighted. Provide at least one positive and one negative.

• As the designer of an evaluation function for adversarial search, you have to determine both the relevant factors and the weighting of those factors. If you did not have a lot of experience with evaluating the state of a game, how would you develop and design a “good” evaluation function?

5. Four people {Wes, Lula, Viv, Xin} performed {Piano, Dance, Magic, Sing} in some order.  What we know:

• Xin sang.
• Wes was 2 acts after the person who performed magic.
• Wes and Lula: one of them was the first act and the other danced.
• The 2^ndact was piano.

Consider framing this for CSP. A variable is a person, and the domain is defined by the set of tuples (act, order). For example, it might be found that Xin was the 2^nd person to perform and he sang: Xin = ( Sing, 2^nd ).

1. Describe the initial domain (generally) for all of the variables. What size is it?
2. Define a constraint, using lambda notation, for “Wes was 2 acts after the person who performed magic.”
3. If you define a constraint for AC3 for the variable pair (Wes, Viv), why do you also need to define one for (Viv, Wes)?

Using propositional logic, consider the expression of a person’s act as “Person_Act” and the order as “Person_Order.” For example, Xin singing 2^nd would be expressed as Xin_Sing AND Xin_2.

• Using Xin_Sing, express that Xin singing means that no one else could have been singing.
• Using “Person_Act” and “Person_Order,” express the collection of rules to reflect that “The 2^ndact was piano.”
• If you expressed all rules in CNF or in Horn clauses, you could use Resolution or Chaining, respectively. Select one of these inference methods, and describe generally what you would be asking your knowledge base to infer to solve this puzzle. Be sure to describe a processto determine a complete solution, not just the order or act for a single person.

• Reframe this problem using first-order logic. Define the constant and predicate symbols.
• State the first-order logic rules that represent:
• Wes was 2 acts after the person who performed magic.
• Wes and Lula: one of them was the first act and the other danced.

• Below is a knowledge base written in propositional logic.

A and F –> E

C –> E

B –> C

D and A –> C

D and B –> A

D.

B.

Draw the AND-OR search tree of a Backward Chaining DFS for Ask(KB,E). Be sure to make clear OR versus AND.

Draw the whole tree, expanding every possible branch.

Whenever a literal is inferred (i.e. becomes True): 1) circle it on your diagram, 2) number them in order of inference (i.e. put #1 by the first literal that you infer from the tree), and 3) from that point on, assume it has been added to the KB.

You can draw this out on paper, take a picture, and include the image.

SOlution：