Free Help for beginner's programmers  

Go Back   Free Help for beginner's programmers > Public forum. > C++ Programming Help

Reply
 
Thread Tools Display Modes
  #1  
Old 09-28-2017, 06:21 PM
MarkIt MarkIt is offline
Junior Member
 
Join Date: Sep 2017
Posts: 3
Default 8Puzzle A* search

Task: Create a C++ program which uses random actions to generate random starting states for the 8-puzzle problem (random_board.cpp)

The goal configuration for the 8-puzzle is defined as follows (zero is the "blank" square):

0 1 2
3 4 5
6 7 8

The input file will be uploaded. (same as the goal state above)

Your random board generator should read the input configuration from standard input, and two command-line arguments (integer: random number generator seed, integer: number of random moves to make), and should print the final configuration to standard output in the same format as the input file format (see above)

Create a C++ program which performs A* search for the 8-puzzle problem (a-star.cpp)

Your program should read an 8-puzzle from standard input, and take a single command line argument (integer: heuristic to use)

0 - h(n) = 0
1 - h(n) = Number of tiles displaced from the goal
2 - h(n) = Sum of Manhattan (city-block) distances of all tiles from the goal
3 - h(n) = A novel heuristic of your own design

Each node should be given a unique ID number, starting with zero for the root node

When sorting nodes in the frontier by f(n), ties should be broken by using the node ID number so that newer nodes will be preferred over older nodes

Your program should output:

-The total number of nodes visited/expanded (V)
-The maximum number of nodes stored in memory (closed list + open list size) (N)
-The depth of the optimal solution (d)
-The -approximate- effective branching factor (b) where N = b^d
-Each state along the optimal path from the starting state to the goal state


Utilize your programs to analyze the performance of the heuristics.

Use your random_board program to generate 100 unique starting states

-Use a unique seed for each board
-Use the goal state as the starting configuration
-Use exactly 100 random moves to generate each board

Run your a-star code on the 100 unique starting states using each heuristic (0,1,2,3)

Compile the following statistics for V, N, d, and b:

-Minimum
-Median
-Mean
-Maximum
-Standard Deviation

Write a report (at least 2 pages, single spaced, 12 point font, 1 inch margins, no more than four pages) describing:

- the 8-puzzle problem
the code you developled to solve the problem
- the heuristics you implemented
- the performance of the code using the different algorithms/heuristics (using the statistics above for justification)
- any limitations of the overall approach
any additional implementation details that improved the performance of your code.
Detailed explanations: Yes
Specific requirements: Use insightful comments in the code to illustrate what is happening on each step.


Include a Makefile with your code which allows it to compile by simply typing 'make'.

Your code should only print the information listed above, in the following format:
V=379
N=654
d=14
b=1.58896

6 3 4
1 0 2
7 5 8

6 3 4
0 1 2
7 5 8

...
Write your report such that a peer NOT taking this course would understand the problem, your approach to solving it, justification of various choices (heuristic, newest node first, etc.), and your final comments.

Include a table of all of the statistics compiled for your report

Include at least one figure to illustrate the 8-puzzle problem

All sources must be properly cited; failure to do so may result in accusations of plagiarism

Your report should be submitted in PDF format.



Updated requirements: This is What I need as a submission:
A zipped file (.zip) containing:

random_board.cpp
a-star.cpp
Makefile
report.pdf
Reply With Quote
Reply

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT. The time now is 04:08 PM.


Powered by vBulletin® Version 3.8.2
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.