Search

Due:

11:00pm, Friday October 1, 2021

Description

Write a programs that implement breadth-first search (BFS) and A^* search for the following problem:

The environment has two kinds of components:

• A table top with three places 1, 2, and 3
• A variable number of blocks A, B, C, etc. that can be arranged in places on the table or stacked on top of one another.

A legal action is to move a block from one place or block onto another place or block

• The moved block must not have another block on top of it
• No other blocks are moved in the process

The program must take a single command line argument where the argument will be an ASCII text file representing the initial state and the goal state for the problem. Here is a example format for the input file:

1 C B A
2
3
1
2 C B A
3

The first three lines represent the initial state and the last three lines represent the goal state. A line starts with the place followed by blocks separated by spaces. The first block on a given line is the lowest block and the last block on a given line is the highest block.

For each search algorithm output the following information:

• Length of the solution
• Maximum size of the frontier (queue for BFS and priority queue for A^*)
• The number of nodes expanded
• The effective branching factor which we will approximate with the formula N^(1/d) where N is the number of nodes expanded and d is the depth at which the solution was found.

To make the results deterministic (at least for the BFS case) your algorithm should expand the nodes in the following order exactly:

1. 1 → 2
2. 1 → 3
3. 2 → 1
4. 2 → 3
5. 3 → 1
6. 3 → 2

The results of you program will be evaluated by running your program on the university Linux server. A test case will be considered a failure if the program takes more than 5 minutes to execute. The A^* search will be evaluated based on its performance relative to BFS on the same test cases.

The following compilers/interpreters are available on the Linux server:

• g++ 8.3.0
• Go 1.15.14
• Java 15.0.1
• OCaml 4.05.0
• Perl 5.16.3
• Python 3.7.7
• Rust 1.54.0

Getting the Assignment

The starter code for the assignment is on the Linux server at the path:

/export/home/public/schwesin/csc447/projects/project1-handout

Turning in the Assignment

You must turn in the following files:

1. bfs.x – implementation where x is an appropriate file extension
2. astar.x – implementation where x is an appropriate file extension
3. README

The README file should be a plain ASCII text file (not a Word file, not an RTF file, not an HTML file) describing your design decisions. This should also detail your choice of heuristic for A^* search. One or two English paragraphs should suffice. Spelling, grammar, capitalization and punctuation all count.

To submit the assignment, execute the command:

    make submit

from within the assignment directory.

Grading Criteria

Grading (out of 100 points):

• 35 points — BFS test cases (up to 12 moves)
  • Each missed test removes points, to a minimum of 0/35, even if there are more tests than total points.
• 35 points — A^* test cases (up to 21 moves)
  • Each missed test removes points, to a minimum of 0/35, even if there are more tests than total points.
• 15 points — for a clear description in your README
  • 15 — thorough discussion of design decisions; a few paragraphs of coherent English sentences should be fine
  • 8 — vague or hard to understand; omits important details
  • 0 — little to no effort, or submitted an RTF/DOC/PDF file instead of plain TXT
• 15 points — for code cleanliness
  • 15 — code is mostly clean and well-commented
  • 8 — code is sloppy and/or poorly commented in places
  • 0 — little to no effort to organize and document code

Note: if your solution is based on pseudo-code from a source other than the textbook or the lecture slides, then you must cite the source of the pseudo-code. Otherwise, you will receive a grade of zero for this assignment.