For your implementation, you will run a search using Dijkstra and A* on the graph given to determine the shortest path forNode starttoNode end. The program will output the shortest path between the two nodes

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Objectives

Code in python.

Answer questions too.

Searching problems are central to gaining an understanding of Artificial Intelligence. We will be continuing our work from the last class by implementing two classic algorithms central to the concept of modern AI: Dijkstra’s algorithm and the heuristic-based extension, A*. We will construct an algorithm so that, if fed information in the proper format, our algorithm can find the shortest path between two specified points and, potentially, display the state of the search along the way.

After completing this lab, you will be able to:

• Create and implement a novel design for representing a graph

• Understand the differences in theory and application between Dijkstra's search algorithm and A*

• Understand the principle of an admissible optimistic heuristic

• Design and parameterize robust and necessary output

Resources

While the lab will explain everything that you need to know, you may want to consult the following sources for additional knowledge:

• https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

• https://en.wikipedia.org/wiki/A*searchalgorithm

Deliverables

Instructions & Questions

Dijkstra and A* both work on directed and undirected connected graphs where edge weights are non-negative. Given this, we are going to need to construct a graph of this type and store it within our code. We can then pass this graph to the function which runs the search. The call to the function is to take the form:

searchXxxxx(Graph g, Node start, Node end, bit robust_output)

Where Xxxxx is the name of the algorithm, Graph g is the graph being searched, Node start is the starting point, Node end is the ending point, and bit robust_output represents whether the program will display more output while it is running. When storing your graph, you will need to store each node within the graph and the connections between the nodes. For this lab, we are going to assume that edge weights are determined by Euclidean distance. Therefore, you will also need to store the coordinate of each node.

For your implementation, you will run a search using Dijkstra and A* on the graph given to determine the shortest path for Node start to Node end. The program will output the shortest path between the two nodes, the length of the path, and the number of nodes visited for each algorithm.

Part 1: Design

First, you need to determine certain design aspects regarding your solution.

1. Explain, in detail, how you will store your graph and nodes within your code. Be sure to explain how the data will be structured internally.

 

2. Explain, in detail, what additional information you will display when the robust_output flag is set to true. Information may be displayed before the search algorithm starts, during each iteration of searching, or after the search algorithm completes. Be sure to include when your additional data will be displayed.

 

Part 2: Concept

3. Translate the following maze into your graph storage methodology. You may document this using conceptual representations or code-based representations. Be sure to include “dead end” nodes in your graph.

 

Part 3: Implementation

4. Implement your solution for the searchDijsktra function. You may write any helper functions that you wish. Be sure to test this code with the graph you created in Question 4, above, as well as with any other graph examples that you wish to use.

​

5. Implement your solution for the searchAStar function. You may write any helper functions that you wish. Be sure to test this code with the graph you created in Question 4, above, as well as with any other graph examples that you wish to use.

 

6. How does the performance of your searchDijsktra function compare with the performance of the searchAStar function? Explain, in detail, with whatever relevant data you have from your code.

Related Questions

. The fundamental operations of create, read, update, and delete (CRUD) in either Python or Java

CS 340 Milestone One Guidelines and Rubric  Overview: For this assignment, you will implement the fundamental operations of create, read, update,

. Develop a program to emulate a purchase transaction at a retail store. This  program will have two classes, a LineItem class and a Transaction class

Retail Transaction Programming Project  Project Requirements:  Develop a program to emulate a purchase transaction at a retail store. This

. The following program contains five errors. Identify the errors and fix them

7COM1028   Secure Systems Programming   Referral Coursework: Secure

. Accepts the following from a user: Item Name Item Quantity Item Price Allows the user to create a file to store the sales receipt contents

Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip

. The final project will encompass developing a web service using a software stack and implementing an industry-standard interface. Regardless of whether you choose to pursue application development goals as a pure developer or as a software engineer

CS 340 Final Project Guidelines and Rubric  Overview The final project will encompass developing a web service using a software stack and impleme