Description

Problem assignment 1
Problem 1. Map coloring problem

Figure 1: Map coloring problem. Left: spatial layout. Right: abstraction of the spatial layout where nodes correspond to countries and links to borders.
Part a. Formulate the map coloring problem as a (graph) search problem by defining its initial state, operators and the goal condition.
Part b. What is the search space size of the formulation in Part a? If the exact calculation of the search space size becomes hard, give a reasonable upper bound estimate.
Part c. Think of another possible formulation of the map coloring problem as the search problem. What is the search space size of this new formulation? Compare the first two formulations in terms of the search space size they define and determine which formulation appears more advantageous.
Part d. Do you think you can solve the problem? If yes, please submit the solution.
Problem 2. Traveler problem
Consider the following graph representing road connections between different cities. Let S be the initial city and G the destination.

Part a. Show how the breadth-first-search would search the graph. That is, give an order (of first 10 nodes) in which the nodes could be expanded. Use the alphabetical order to order the equivalent choices.
Part b. Show how the depth-first search with the elimination of cyclic state repeats would search the graph. That is, give an order in which the nodes are expanded. Use the alphabetical order to break the ties(i.e., equivalent node choices).
Part c. Show how the breadth-first-search would search the graph. Assume we use the breadth-first search that checks for and prevents cyclic state repeats only. Again, use the alphabetical order to break the ties (i.e., equivalent node choices).
Part d. Show how the breadth-first search that checks for all state repeats would search the graph.
Problem 3. A problem-solving agent for the 8-puzzle problem.
In this problem we will implement a number of uninformed search techniques and test them on the 8-puzzle problem. The rules for submitting the programming assignments are posted at: http://www.cs.pitt.edu/~milos/courses/cs1571/program-submissions.html
The 8-puzzle problem is described in the textbook (Russell and Norvig) on page 70 and 71. We have also studied the problem in lecture 2 (see lecture notes). The problem formulation of the 8-puzzle problem consists of:
• States: different tile configurations • Operators: moves of an empty position
• Initial configuration.
• Goal configuration:
1 2 3
4 5 6
7 8 0
where 0 represents the empty (blank) tile. Note that the goal configuration we consider is different from the configuration in the textbook!
• Solution (path) cost: the number of moves of the empty tile.
Part a. Run the plain breadth-first search algorithm.
To get you started in the assignment, you are given a python code implementation of the breadth-first search method for 8-puzzle. You can download the code from: http://www.cs.pitt.edu/~milos/courses/cs2710-Fall2019/PS/HW-1/. The two files given are:
• Puzzle8.py that defines the Puzzle 8 problem, search tree nodes, a hash table, and 5 different game configurations to solve labeled as Example 1, …, Example 5
• dfs.py that implements the basic depth first search procedure and runs it in on 4 out of 5 initial game configurations.
Once you run the code in dfs.py, you should see the solutions for four initial configurations.
Three of the initial configurations are shown below:
Example 1: Example 3: Example 4:
1 2 3 4 1 2 4 1 2
4 6 0 7 6 3 7 6 3
7 5 8 0 5 8 5 8 0
Familiarize yourself with the python code given to you before proceeding to Part b.
Part b. Breadth-first search statistics.
Write a breadth first search stats procedure that modifies the breadth first search procedure given to you in file bfs.py such that it is able to collect and print the following statistics:
• the total number of nodes expanded;
• the total number of nodes generated;
• the maximum length of the queue structure;
• the length of the solution path (number of moves)
The statistics should be printed after the example is solved and should be followed by the solution (move) sequence. Include the breadth first search stats procedure in the bfs stats.py file and use it to execute it on the first four initial configurations similarly to bfs.py.
Part c. Breadth-first search with the elimination of cyclic state repeats.
The basic breadth-first search procedure does not check for and eliminate state repeats. In general, there are two strategies to eliminate state repeats:
• Elimination of cyclic state repeats: Do not expand the node if its state is the same as in one its ancestors in the search tree.
• Elimination of all state repeats: Do not expand the node if its state has been expanded before.
Note: Please see lecture notes for Lecture 3 on the elimination of state repeats.
To implement the bfs with cycling check repeats you will need to write two pieces of code:
• function check cyclic repeats(node) that takes a tree node and checks if the state linked to that node is also associated with one of its parent nodes in the search tree. The function should return true if the cyclic repeat indeed occurred.
• function breadth first search cycles that modifies your code in Part b, such that prior to the node expansion it calls check cyclic repeats(node) to check if we entered the cycle.
Part d. Breadth-first search with the elimination of all state repeats.
Implement a breadth first search repeats procedure that: (1) checks for and eliminates all state repeats, (2) collects and prints the same statistics as in Part b. Include the procedure in the bfs repeats.py file and run it on all five test examples.
To implement the elimination of all state repeats please use the hash table implemented in Puzzle8.py file.
Hint: Similarly to the breadth first search with cyclic state repeats we recommend to check the node (its state) for repeats just before the node is expanded, that is, after it is extracted from the queue. Note that you do not have to check for cyclic repeats since the all repeats test subsumes the cyclic repeats test.
Part e. Analysis of the results
Analyze the performance of all three bfs methods (parts b,c,d) in terms of the collected statistics and include the analysis in the report. More specifically you should:
• Summarize the results of the different bfs methods in different tables, one table for every example tried.
• Compare the methods in terms of the respective statistics. Which one is the best? Explain why.
Part f. Depth-limited depth-first search
Implement a depth-limited depth-first search procedure depth first search limit(problem,limit). Please note that the depth of the node is stored in the g field of the Treenode structure, so you can easily check if the node satisfies the depth limit. Your procedure should return the optimal solution if it can be reached within the search limit. Also your limited-depth depth-first search procedure should try to check for and avoid the branches of the tree that are suboptimal given the previously seen nodes and states. To do so please use the hash table and its ability to keep an arbitrary positive value for each key. Briefly, for each explored state always keep in the hash the length of the minimum path to that state as observed during the search process. Finally, the procedure should calculate and keep the same search statistics as used in Parts b, c, d.
Include the depth-limited depth-first search procedure in the dfs limit.py file and run it using the limit 10 on Examples 1, 2 and 3. Analyze the results of your dfs procedure and compare it to results obtained for the different versions of bfs in Parts b, c, d.
Programs to be submitted with your assignement. In addition to the report you