CSC396 - Project 1
Solving Problems

Assigned Jan 24nd
Due Feb 8th 2pm

Overview

Part 1 - Travelers on a Bridge

We will investigate a particular instance of this problem, where we have four travelers with travel times as noted below:

A -- 1 minute
B -- 2 minutes
C -- 5 minutes
D -- 10 minutes

Consider the search space for this problem.

1. What information must be kept at each search node?
2. What is the initial search node?
3. What is the goaltest function for this problem?
4. What operators should be used to generate the children of a node?
5. Draw the state space for this problem.

For each of the search strategies listed below, (a)show the contents of the OPEN and CLOSED lists for each iteration through the Pseudocode for Searching, (b)indicate which goal state is reached if any, and(c)write down the solution path that reaches that goal. (Recall that a state is expanded when it is removed from the OPEN list.) When all else is equal, nodes should be expanded in alphabetical order based on who is on the left side of the bridge.

1. breadth first search
2. depth first search
3. iterative deepening search
4. uniform cost search

General Pseudocode for Searching

Note: Things may need to be tailored a bit to each different search method being used. For example, in the iterative deepening search a node may be placed on the closed list because it is at the maximum depth for an iteration, but later the code may find another way to that node that would make the node less deep, and so the node would need to be moved out of the closed list and put back in the open list.

  OPEN   = { startNode } // Nodes under consideration.
  CLOSED = { }           // Nodes we're done with.

  while OPEN is not empty
  { 
    remove an item from OPEN based on search strategy used
    - call it X

    if goalState?(X) return the solution found

    otherwise // Expand node X.
    {
        1) add X to CLOSED
        2) generate the immediate neighbors (ie, children of X)
        3) eliminate those children already in OPEN or CLOSED
        4) add REMAINING children to OPEN according to QUEUEING FUNCTION
    }
  }
  return FAILURE  // Failed if OPEN exhausted without a goal being found.

Part 2 - Programming Puzzles

First, you must have the user input the initial state for your puzzle. This can be done through a series of questions for the user, or can be entered using an appropriate symbolic language to describe a state for your puzzle. Such a language should be similar in nature to the solution language described on the back of your puzzle cards.

Second, you must ask the user for the search technique to be used. This will be one of the following options

• BFS: Breadth First Search
• DFS: Depth First Search
• UCS: Uniform Cost Search
• GREEDY: Greedy Search

Third, your program must implement a heuristic function for use with GREEDY search. This heuristic function is designed by you, and should attempt to model your best guess as to the distance left to a goal node. The heuristic function at the goal nodes should be equal to 0.

Fourth, your program must search according to the chosen search method and report the first goal node found. It will print out the solution path to the goal node in such a manner that it can be implemented by you on the physical puzzle and verified, along with the length of the solution path and the number of nodes expanded to reach that goal node. You must test your program on more than one of the puzzle cards to guarantee your program can find the appropriate solutions.

I strongly recommend creating an instantiable class SearchNode. This will need to have data members as we have described for a node in the search tree, such that it tracks the current state space, parent node, total path cost, depth, etc. It should be able to generate all successor states (children) based on the current state and applying all possible actions.

This SearchNode class will be used by your main driver class, in which you will implement the pseudocode search algorithm from above. Make good use of your available data structures already implemented in your language of choice, such as lists and dictionaries in python or ArrayList and HashTable classes in Java.

Evaluation

1. Describe your heuristic function in easy-to-understand English.
2. What do you see as the weaknesses of your heuristic function?
3. Is your heuristic function admissible?
4. Which search technique do you believe worked the best on your puzzle and why?

Sample Code

• cupsTest.py in Python
• Cup.java in Java
• CupsNode.java in Java

What to Hand In

1. Open the Terminal application.
2. SSH with ssh username@cs.centenary.edu to connect with the cs server.
3. Type in your password.
4. Make a new directory with mkdir csc396
5. Make a new directory with mkdir csc396/project1
6. Change the permissions with chmod 700 csc396
7. Change the permissions with chmod 700 csc396/project1
8. Set permissions for grading with setfacl -m u:mgoadric:rx -R csc396
9. Log out of the cs server with logout
10. Change to the directory where you have your files on the local computer.
11. Securely copy your files to your directory with scp filenames username@cs.centenary.edu:"csc396/project1"
12. Securely copy your evaluation file to your directory with scp project1_evaluation.txt username@cs.centenary.edu:"csc396/project1"