To get you started with handling graphs, implement and test breadth-first search over the test network.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Tasks

Priority queue

In all searches that involve calculating path cost or heuristic (e.g. uniform-cost), we have to order our search frontier. It turns out the way that we do this can impact our overall search runtime.

To show this, you'll implement a priority queue which will help you in understanding its performance benefits. For large graphs, sorting all input to a priority queue is impractical. As such, the data structure you implement should have an amortized O(1) insertion and O(lg n) removal time. It should do better than sorting the entire list after every insertion.

In this implementation of priority queue, if two elements have the same priority, they should be served according to the order in which they were enqueued (see Hint 3).

Notes:

1. Please note that the algorithm runtime is not the focus. The already-imported heapq library should achieve the desired runtime.

2. If you use the heapq library, keep in mind that the queue will sort entries as a whole upon being enqueued, not just on the first element. This means you need to figure out a way to keep elements with the same priority in FIFO order.

3. You may enqueue nodes however you like, but when your Priority Queue is tested, we feed node in the form (priority, value).

 

BFS

To get you started with handling graphs, implement and test breadth-first search over the test network.

You'll complete this by writing the breadth_first_search() method. This returns a path of nodes from a given start node to a given end node, as a list.

 

For this part, it is optional to use the PriorityQueue as your frontier. You will require it from the next question onwards. You can use it here too if you want to be consistent.

Notes:

1. You need to include start and goal in the path.

2. If your start and goal are the same then just return [].

3. You can access all the neighbors of a given node by calling graph[node], or graph.neighbors(node) ONLY.

4. You are not allowed to maintain a cache of the neighbors for any node. You need to use the above mentioned methods to get the neighbors.

5. In BFS, make sure you process the neighbors in alphabetical order. Because networkx uses dictionaries, the order that it returns the neighbors is not fixed. This can cause differences in the number of explored nodes from run to run. If you sort the neighbors alphabetically before processing them, you should return the same number of explored nodes each time.

6. For BFS only, requires implementing an optimization trick which fully explores fewer nodes.

 

Uniform-cost search

Implement uniform-cost search, using PriorityQueue as your frontier. From now on, PriorityQueue should be your default frontier.

uniform_cost_search() should return the same arguments as breadth-first search: the path to the goal node (as a list of nodes).

Notes:

1. You need to include start and goal in the path.

2. If your start and goal are the same then just return [].

3. The above are just to keep your results consistent with our test cases.

4. You can access all the neighbors of a given node by calling graph[node], or graph.neighbors(node) ONLY.

5. You can access the weight of an edge using: graph.get_edge_weight(node_1, node_2). Not using this method will result in your explored nodes count being higher than it should be.

 

6. You are not allowed to maintain a cache of the neighbors for any node. You need to use the above mentioned methods to get the neighbors and corresponding weights.

7. We will provide some margin of error in grading the size of your 'Explored' set, but it should be close to the results provided by our reference implementation.

 

A* search

Implement A* search using Euclidean distance as your heuristic. You'll need to implement euclidean_dist_heuristic() then pass that function to a_star() as the heuristic parameter.

Hint: You can find a node's position by calling the following to check if the key is

available: graph.nodes[n]['pos']

 

Notes:

1. You need to include start and goal in the path.

2. If your start and goal are the same then just return [].

3. The above are just to keep your results consistent with our test cases.

4. You can access all the neighbors of a given node by calling graph[node], or graph.neighbors(node) ONLY.

5. You can access the weight of an edge using: graph.get_edge_weight(node_1, node_2). Not using this method will result in your explored nodes count being higher than it should be.

6. You are not allowed to maintain a cache of the neighbors for any node. You need to use the above mentioned methods to get the neighbors and corresponding weights.

7. You can access the (x, y) position of a node using: graph.nodes[n]['pos']. You will need this for calculating the heuristic distance.

 

Bidirectional uniform-cost search

Implement bidirectional uniform-cost search. Remember that this requires starting your search at both the start and end states.

bidirectional_ucs() should return the path from the start node to the goal node (as a list of nodes).

 

Notes:

1. You need to include start and goal in the path. Make sure the path returned is from start to goal and not in the reverse order.

2. If your start and goal are the same then just return [].

3. The above are just to keep your results consistent with our test cases.

4. You can access all the neighbors of a given node by calling graph[node], or graph.neighbors(node) ONLY.

5. You can access the weight of an edge using: graph.get_edge_weight(node_1, node_2). Not using this method will result in your explored nodes count being higher than it should be.

6. You are not allowed to maintain a cache of the neighbors for any node. You need to use the above mentioned methods to get the neighbors and corresponding weights.

 

 

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. 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. The LineItem class will represent an individual

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

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of