CS170程序代做、Python编程设计代写

日期：2024-02-10 10:23

Project 1: Search Algorithms in a Grid

Environment and Path-finding

CS170 Artificial Intelligence, UCR, Winter 2024

1 Introduction

Explore the world of search algorithms in a grid-based environment. In this

project, you will implement different search strategies to navigate from a

starting cell to a target cell, while encountering obstacles and open paths.

This hands-on exercise aims to deepen your understanding of the fundamental search algorithms frequently employed in Artificial Intelligence. This

project also involves determining the shortest path based on the search algorithm you use for exploring the route.

2 Code Structure

You’ll be given a code template containing the SearchAlgorithms class. Your

task is to fill in the methods corresponding to each search algorithm and

ensure they return both the status of the target’s discovery and the final

state of the grid:

? uniform search(): Implement the Uniform Search algorithm.

? dfs(): Implement the DepthFirst Search algorithm.

? bfs(): Implement the BreadthFirst Search algorithm.

? best first(): Implement the Best First Search algorithm, based on

a heuristic you design or choose. Use the Manhattan distance as the

heuristic.

1

? a star(): Implement the A Search algorithm, combining both cost

and heuristic (Manhattan distance).

? agreedy(): Implement the Greedy Search algorithm, focusing solely

on the heuristic (Manhattan distance).

For algorithms that use a priority queue, utilize the heapq module from

Python’s standard library to manage the queue efficiently. The grid is represented as a list of lists, containing:

? s: Starting position.

? t: Target or goal position.

? 0: Empty cells that you can traverse.

? -1: Walls or obstacles that you cannot traverse.

As you traverse the grid, mark the order of cells you visit by replacing the

0s with consecutive numbers. The starting and target positions, represented

by s and t, should remain unchanged.

3 Requirements

? Follow the provided class and method names precisely. This ensures

compatibility with the autograder on Gradescope.

? The function signatures or class names must not be altered.

? Use the Manhattan distance as the heuristic for the Best First, A*, and

Greedy algorithms.

? Utilize the heapq module for implementing priority queues in applicable

algorithms.

? Each search algorithm function must return a tuple containing two

elements: a numeric indicator and the final state of the grid. The

numeric indicator should be 1 if the target is found, and -1 if it is

not found. The final state of the grid should display the marked cells

according to the path found by the search algorithm. For instance,

2

if the target is found, the function could return (1, grid), where 1

represents the successful search and grid represents the final state of

the board.

? When adding to your queue or stack, follow this order: Right, Down,

Left, Up, or the reverse. The order can be reversed as well.

? Return the shortest path from the source to the target using a list of

tuples.

4 Example

Below is an example grid before and after applying the DFS algorithm:

5 Submission

Submit your completed Python script through Gradescope by the specified

deadline.

? You must follow the class and method names exactly for compatibility

with the autograder on Gradescope.

? Do not change the function signatures or class names.

6 Submission

Please submit your Python script through Gradescope by the specified deadline. Note: This project also includes a report, which should be

submitted separately.

3

Figure 1: The initial state of the board.

4

Figure 2: The board after applying DFS. The returned value is 1 and the

final state of the board is displayed. Note that DFS is LIFO, so we explore

up, left, down, right.

5