Description of task:
You need to find a cheapest solution to the 8-puzzle. Given the initial state and the goal state of 8-puzzle, you need to use BFS, DFS, and Dijkstra algorithms.
For the BFS and DFS algorithms, the cost of moving tile is 1 and ordering of a move is: left, up, right, and down. For example
1 3 4
8 0 2
7 6 5
1 3 4 1 0 4 1 3 4 1 3 4
0 8 2 8 3 4 8 2 0 8 6 2
7 6 5 7 6 5 7 6 5 7 6 5
For the Dijkstra algorithm, suppose that the cost of a move in the 8-puzzle is equal to the number of the moved tile plus the number of displaced tiles. That is, the cost of moving tile 1 is $1+the number of displaced tiles of 1, the cost of moving tile 2 is $2+the number of displaced tiles of 2, and so on. Calculate the number of displaced tiles, for each states and implement the Dijkstra algorithm that finds a cheapest solution; it should read a start state from a file, and print out the shortest path cost and a cheapest sequence of moves that leads to the goal state given in Figure below:
1 2 3
8 4
7 6 5
Use the programming language of your choice.
You may assume that the puzzle always has a solution; that is, the program does not have to deal with unsolvable states.
The format for encoding start states is as follows:
Each is a digit from 0 to 8, where 0 marks the blank space, and the other digits are real tiles. For example, the following file encodes the start state:
7 2 4
5 0 6
8 3 1
Sample file 1:
1 34
8 02
7 65
Solutions: The shortest path cost =11
Sample file 2:
1 3 4
8 0 6
7 5 2
Solution: The shortest path cost = 30
Final report, slides, and codes: A report that represents the performance evaluation of your solution should include the description of your task, summary of results, main conclusions, comparison of solutions, using different algorithms, and discussion of any surprising discoveries (including the title page, abstract, 3-5 pages, font 12, double space).
Demonstration and presentation: The project concludes with a 10-15 min presentation held during the classes.
Don't waste your worthy time by roaming here and there and approach our professional Dijkstra Algorithm Assignment Help tutors for getting assured great academic success!
Tags: Dijkstra Algorithm Assignment Help, Dijkstra Algorithm Homework Help, Dijkstra Algorithm Course Help, Dijkstra Algorithm Solved Assignments
Attachment:- Dijkstra algorithm.rar