代做CSCI 3202留学生、代做Artificial Intelligence编程、OS/CS语言代写

日期：2018-10-10 10:44

CSCI 3202: Introduction to Artificial Intelligence

Homework 4 (rev. 1): due 9. October 11:59pm to Moodle.

Release calendar for this homework:

+ 26. September: this prompt rev. 1 released; Problem 1 skeleton code available on Moodle.

+ 29. September: CodeRunner quiz for Problem 1 available on Moodle.

+ 1. October: Problem 2 skeleton code available on Moodle.

+ 3. October: CodeRunner quiz for Problem 2 available on Moodle.

Learning objective: Use heuristics to solve search problems; use back-forward

iteration to solve the connected-graph color constraint problem.

1 Neal Page is done with Chicago

Neal Page has had it up to HERE with living in Chicago, so far away from where he has to do

most of his business. He’s decided to pack up his family and move to Providence, this time in the

middle of summer. Because we all know that summertime in the northwest corridor is absolutely

peaches.

Del is a close friend of the family now and has decided to help his good friend Neal make the

move. Who knows, maybe he’ll live in Providence too? Neal is really only in it for the map of

straight-line distances to Providence that Del has meticulously created, as shown graphically in

sld_providence below. Even more valuable is the sld_providence dictionary in the skeleton code,

which Del wrote because he is also a script kiddie. Note that because it doesn’t make much sense to

add estimated travel times and the straight-line distance, we will only be using the map_distances

state space graph for this problem.

1

map_distances sld_providence

1.1 A-star Search

Modify your code for uniform-cost search from Homework 3 so that it provides optionally as

output the number of nodes expanded in completing the search.

Include a new optional logical (True/False) argument return_nexp, so your function calls to

the new uniform cost search will look like: uniform_cost(start, goal, state_graph, return_cost,

return_nexp).

If return_nexp is True, then the last output in the output tuple should be the number of

nodes expanded.

If return_nexp is False, then the code should behave exactly as it did in Homework 3.

Then, verify that your revised codes are working by checking Neal’s optimal route from New

York to Chicago. Include the number of nodes expanded and the path cost (using map_distances).

Moodle Quiz Problem 1. Pass the UCS unit tests (see skeleton code).

1.2 Heuristic Function

Define a function to take as an argument the state that Neal is in (city on our graphs), and return

as output the value of the straight-line distance heuristic, between Neal’s state and Providence.

Note that your function should be quite short, and amounts to looking up the proper value

from the sld_providence dictionary defined in the helper functions. Call this function heuristic_sld_providence.

This might seem sort of silly right now, but it will make your codes much easier to adapt in

Problem 3.

Moodle Quiz Problem 2. Pass the heuristic function lookup unit tests (see

skeleton code).

1.3 Full-blown A?

We are finally ready to help Neal use his knowledge of straight-line distances from various cities

to Providence to inform his family’s route to move from Chicago to Providence!

Modify your uniform-cost search codes from 1.1 even further so that they now perform A?

search, using as the heuristic function the straight-line distance to Providence.

2

Provide heuristic as an additional argument, which should just be the function to call within

the A code. So your call to the A?

routine should look like: astar_search(start, goal, state_graph,

heuristic, return_cost, return_nexp). (This kind of modular programming will make it much

easier to swap in alternative heuristic functions later, and also helps to facilitate debugging if

something goes wrong.)

Moodle Quiz Problem 3. Pass the astar_search unit tests (see skeleton code).

1.4 Middle-of-the-Journey test

Neal and Del have already made it to Buffalo, but there is a freak snow storm up there (as there

always is!) and they’re disoriented from the lack of luck. Use your A?

search code from 1.3 to help

them find the optimal path by distance traveled the rest of the way to Providence.

Moodle Quiz Problem 4. Print the the following using your code:

1. the optimal path

2. the optimal path cost (miles traveled)

3. the number of states expanded during the A?

search

Additionally, print how many states must be expanded to find the optimal

path from Buffalo to Providence using the regular old uniform-cost search algorithm

from 1.1.

Moodle Quiz Problem 5. Comment on the difference in states that must be

explored by each algorithm. Sanity check: No matter what your start and goal

states are, how should the output from astar_search and uniform_cost search

compare?

Moodle Quiz Problem 6. How many states are expanded by each of A?

search

and uniform cost search to find the optimal path from Philadelphia to Providence?

3

2 O, Canada!

We’ve discussed how map coloring problems are prime examples of constraint satisfaction problems.

In this exercise you’ll have the chance to test out backtracking, constraint propagation, and

leveraging structure. See below for a map we’re interested in coloring of mainland Canada.

colored_map graphical_map

In this problem, you only have the colors (“values”) red, green, and blue (why do we need 3

colors?). In order to solve the constraint satisfaction problem over graphical_map, write a class

CSP( vars, neighbors, domain ) where vars is a list of variables which must have values from

the list domain assigned to them, neighbors is a dict of var:[var,. . . ] that for each variable lists

the other variables that cannot have the same value. This class will be passed to different solver

algorithms that you will write. Note that in this constraint satisfaction problem we implicitly

consider the constraints to be that adjacent variables cannot hold the same value.

Moodle Quiz Problem 7. Pass the unit tests for the CSP class (see skeleton

code).

2.1 Can’t get no satisfaction

Recall the general idea behind the backtracking search (Lecture 8):

1. One variable at a time

Variable assignments are commutative, so fix ordering

e.g. [YT = red then NT = green] same as [NT = green then YT = red]

Only need to consider assignments to a single variable at each step

2. Check constraints as you go

i.e. consider only values which do not conflict previous assignments

Might have to do some computation to check the constraints

“Incremental goal test”

4

Depth-first search with these two improvements is called backtracking search.

In this problem, you will write a function backtracking_search( CSP, nbacks, mcv, lcv ) which

takes as its arguments a CSP object and a Boolean variable nbacks which indicates whether should

print out the number of times your algorithm has backtracked, as well as mcv and lcv which for

now will all be set to False. The function outputs the solved constraint satisfaction problem in the

form of a dict, e.g. YT:red, NT:green, . . . . The naive backtracking search will have an ordering that

proceeds alphabetically in variable names and in value assignments.

In the following problems, we will always assume we are beginning color assignment with the

YT variable.

Moodle Quiz Problem 8. Pass the unit tests for the naive backtracking search

(see skeleton code).

Having written a method which can solve the backtracking search problem over a given CSP,

now it’s time to solve the Canada color assignment problem.

Moodle Quiz Problem 9. Print out the solved CSP for the Canada problem using

the naive backtracking search method you’ve written, as well as the number

of times you’ve backtracked.

2.2 Heuristics on Backtracking

As we learned in class, there exist many types of heuristics which can be applied to backtracking

search in order to speed it up and reduce the number of times we need to backtrack. Three of these

we discussed in class are most constrained variable, least constraining value, and forward checking.

Remember those extra Boolean variables we set above? Now’s the time to actually implement

these heuristics (note we are not going to implement forward checking for this assignment).

Moodle Quiz Problem 10. Print out the solved CSP for the Canada problem

using the most constrained variable heuristic enabled, as well as the number

of times you’ve backtracked.

Moodle Quiz Problem 11. Print out the solved CSP for the Canada problem

using the least constraining value heuristic enabled, as well as the number of

times you’ve backtracked.

Moodle Quiz Problem 12. Print out the solved CSP for the Canada problem

with both of the heuristics enabled, as well as the number of times you’ve

backtracked.

2.3 How well can you do?

In class we also discussed the notion of sub-cuts in order to exploit the structure of the graph.

Using this method, one should be able to solve this relatively well-structured CSP by eliminating

loops and solving the forward-assigned problem in each instance. This will be the focus of a

quizlet on Wednesday, October 10 — no deliverable as part of this assignment just yet.