PROGRAMMING SEARCH ALGORITHMS FOR MISSIONARIES AND CANNIBALS , ROAD TRIP PROBLEMS
Artificial Intelligence
Homework 1
PROBLEM 1.: Problem Formulation for Search (50 points)
___________________________________________________________________
The Missionaries and Cannibals Problem is stated as follows. Three missionaries and three cannibals are on one side of the river, along with a boat that can hold one or two people. Find a way to get everyone to the other side without ever leaving a group of missionaries outnumbered by cannibals in that place.
Programming Assignment for Problem 2:
1. Use the implementations of the search strategies available in the aima code; available at:
https://github.com/aimacode/
to write the program that will search for the solution to Missionaries and Cannibals Problem. (list the content of the frontier and the list of explored nodes for the first 5 steps of each of the strategies used 50points)
(a) uniform-cost search; (b) iterative deepening search; (c) greedy best-first search; (d) A* search and (e) recursive best-first search
PROBLEM 2: Searching for Road Trips in the U.S.A. (50 points)
Considering the following table:
Table of direct/flight distances to Dallas (in miles). =heuristics
___________________
Austin 182
Charlotte 929
San Francisco 1230
Los Angeles 1100
New York 1368
Chicago 800
Seattle 1670
Santa Fe 560
Bakersville 1282
Boston 1551
The road graph is (in miles):
_____________________________________
Los Angeles — San Francisco ::: 383
Los Angeles — Austin ::: 1377
Los Angeles — Bakersville ::: 153
San Francisco — Bakersville ::: 283
San Francisco — Seattle ::: 807
Seattle — Santa Fe ::: 1463
Seattle — Chicago ::: 2064
Bakersville — Santa Fe ::: 864
Austin — Dallas ::: 195
Santa Fe — Dallas ::: 640
Boston — Austin ::: 1963
Dallas — New York ::: 1548
Austin — Charlotte ::: 1200
Charlotte — New York ::: 634
New York — Boston ::: 225
Boston — Chicago ::: 983
Chicago — Santa Fe ::: 1272
Boston — San Francisco ::: 3095
You contemplate to search for a trip back to Dallas from Seattle, having access to a road map which should be implemented as a graph
1/ Programming Assignment for Problem 2 _Part A:
Use the implementations in the AIMA code available at:
https://github.com/aimacode
to find the solution and return a simulation of the RBFS strategy by generating automatically the following five values: (1) f_limit; (2) best; (3) alternative; (4) current-city; and (5) next-city for each node visited.
(20 points)
2/Programming Assignment for Problem 2 _Part B:
Use the implementations in the AIMA code available at:
https://github.com/aimacode
to find the solution to the same search which implements the A* algorithm. Make sure that the program lists the contents of the frontier and explored list for each node that you visit during search, in the format:
[Current node: X; Evaluation function (current node)=???;
Explored Cities: [ ._]_;Frontier: [(City_X, f(City_X)), .];]
(20 points)
And also Write a program that will check if the heuristic provided in this problem is consistent, given the road graph.(10 points)
Your README file must include the following:
· A description of every file for your solution, the programming language used, supporting files from the aima code used, etc.
· How your code operates, in detail.
· A description of special features (or limitations) of your code.
Within Code Documentation:
· Methods/functions/procedures should be documented in a meaningful way. This can mean expressive function/variable names as well as explicit documentation.
· Informative method/procedure/function/variable names.
· Efficient implementation
· Don’t hardcode variable values, etc
