Assignment 1 AI - 8 Puzzle Problem,DFS and BFS PDF

Preview

Summary

8 Puzzle Problem,DFS and BFS...

Description

CS 7375 Spring 2022 Assignment 1 Abstract:The answer to the 8-puzzle problem is described in this puzzle. Given a 3 -square board with 8 tiles (each with a number from 1 to 8) and one vacant place. The goal is to use the vacant space to position the numbers on tiles to match the final configuration. Four neighboring tiles (left, right, above, and below) can be moved into the vacant area. Initial puzzle:

1

3

4

8

0

5

7

2

6

Goal puzzle:

1

2

3

8

0

4

7

6

5

DFS (Brute-Force) We can do a depth-first search on the state-space tree. In this solution, subsequent steps may lead us farther from the objective rather than closer to it. Regardless of the initial state, the state-space tree search takes the leftmost path from the root. In this strategy, an answer node may never be located .

BFS(Brute-Force) We may execute a Breadth-first search on the state space tree using BFS (Brute-Force). This always returns a goal state that is close to the root. Ho wever, regardless of the initial state, the algorithm attempts the same sequence of movements as DFS.

UCS: Uniform-cost search is an ignorant search algorithm that finds the path from the source to the destination with the lowest cumulative cost. Starting with the root, nodes are enlarged based on the lowest cumulative cost. A Priority Queue is then used to carry out the uniform-cost search.

Algorithm ucs:

From the python program the below is the output by using BFS algorithm.

From the python program the below is the output by using DFS algorithm

From the python program the below is the output by using uniform cost algorithm....