Finding a Path and the Minimum-Length Path Given map information places, direct connections, and distances use search to find paths between any 2 locations

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Finding a Path and the Minimum-Length Path

Given map information (places, direct connections, and distances), use search to find paths between any 2 locations. The ultimate goal is to find the minimum-length path.

Specifically, you will use different versions of the search to return the path between any two pairs of locations. You can test your code on the map in Figure 1.

We will need to represent the edge information so that you can find out 1) all edges leading from a location, and 2) the distance on each of those edges. You could use a set of tuples of the form (place1,  place2,  distance), where these represent a link on the map such as (v,  m,   4).  You can represent the states in different ways, but your search code should return a list containing the path from source to destination (which is a list) and the cost of that path.

For example, on the above map, the search from E to S should return the path [E, J, M, S].

We will use three types of search: two versions that search blindly (i.e. breadth-first or depth-first) until you have found a non-cyclic path from the start to the destination and another version that uses A∗ search using path cost plus estimated distance to goal as an evaluation function. I used the following (x , y) locations for the places and used straight-line distance as an estimate of distance to goal. These are provided as starter code attached to the assignment.

N	(0.2, 1)
P	(1.35, 4.25)
U	(2.15, 0.875)
E	(3.42, 2.125)
J	(3.8, 4.575)
M	(6.7, 3.875)
S	(6.7, 1.875)
V	(5.6, 0.1)

 

Search Strategies

We will make use of some well-known search strategies without much discussion. You will learn more about these in future classes. This will serve as a brief introduction.

Exploring a graph, such as the graph of cities in this example, can be viewed as traversing a tree structure where the cities that can be traveled to directly are children of a particular city in the tree.  In fact, this is the way we will view solving this problem.  Surprisingly, we can do this without building an  actual  tree  data  structure.   The  idea  is  that  we  will  represent  cities/locations  as  nodes  in  some tree structure and expand a node to get its children in the tree.  The different search strategies will be determined  by  the  order  in  which  we  choose  the  next  node  to  expand/explore.  Instead  of  building an actual tree structure (like the binary trees we used this semester) we will store nodes waiting to be expanded/explored in an ADT. The type of ADT will determine the order in which these nodes are removed which therefore determines the order in which nodes are explored in the tree.  You are provided with an abstract search function which takes a container (implementation of one of these ADTs) as well as a starting and destination nodes.  Just by changing the type of container, we can change the order in which nodes are explored,  which changes the search strategy with the very same abstract search function.

When traversing the tree of locations, the nodes waiting to be explored are collectively referred to as the fringe. The search strategy will determine which of the nodes in the fringe will be the next to be explored. Once expanded, all adjacent nodes are added to the fringe. The search starts with the starting location/node as the only node in the fringe.

 

Uninformed Search

Breadth-First Search The strategy for Breadth-First Search (BFS) is to expand all neighbors of a node before any of its successors. So, we want to expand the shallowest unexpanded node in the tree. In this case, the fringe is a FIFO queue ADT where new nodes go to the end of the queue. The intuition is that  we don’t want to venture too deep in the tree if a shorter path to our destination exists. So, we explore all the “closest” locations first before venturing deeper into the tree.

The following sequence shows an example of the order in which nodes are explored using BFS. The red arrow indicates the next node to be expanded. Grey nodes have been already explored. White nodes are nodes that are currently in the fringe waiting to be explored. Green nodes have not been discovered at that stage of the search.

So, the full order would be A, B, C, D, E, F, G using a BFS strategy.

 

Depth-First  Search  The strategy for Depth-First Search (DFS) is the opposite strategy as BFS. With  DFS we expand all successors (children) of a node before any of its neighbors. So, we want to expand the deepest unexpanded node in the tree. In this case, the fringe is a LIFO stack ADT where new nodes go to the top of the stack. The intuition is that we don’t want to waste too much time exploring local nodes if the destination is deep in the tree. So, we explore all the “farthest” locations first before venturing in another direction/branch in the tree.

The following sequence shows an example of the order in which nodes are explored using DFS. The red arrow indicates the next node to be expanded. Grey nodes have been already explored. White nodes are nodes that are currently in the fringe waiting to be explored. Green nodes have not been discovered at that stage of the search.

So, the full order would be A, B, D, H, I, E, J, K, C, F, L, M, G, N, O using a DFS strategy.

 

Finding the Minimal Path     Uninformed search strategies use no particular knowledge to guide the search.  These search strategies will keep expanding nodes until the find a path from the starting location to the desired destination.  There is no way to determine if the first path found is the shortest path.  To find the shortest path, one would need to continue searching the entire tree to find all paths and then compare them all to find the shortest.

 

Informed Search

Informed search strategies use additional information to guide the search. One informed search strategy, A (pronounced “A star”), uses a heuristic to determine which node to explore next. If the heuristic function has particular properties, it guarantees an optimal solution. That is, a proper heuristic finds the minimum distance path from the start to destination cities as the first solution found. The heuristic we will use takes the distance traveled so far in the search from start city, through the locations so far, to the current location. It also adds the distance “as the crow flies” from the current location to the location of the destination city (e.g. using the euclidean distance formula). You  will notice that the (x , y) coordinates (think GPS coordinates) of the cities in this problem are given. This sum provides an estimate of the total distance from the starting city, to the location that has a node in the fringe, onward to the destination. A search will choose the node in the fringe with the smallest estimated path distance from source to the destination when selecting the next node to expand. For A , we can view the fringe as a priority queue ADT.

 

Tree Search

The general tree search algorithm represents the state of the search with the current node and the path of nodes visited to reach that node. The search function begins with just one node in the fringe which represents the starting state.  The search function then continues removing the front node in the fringe.  It then checks if this is the solution/goal node. If so, it returns this node. Otherwise, it expands the node and adds all of the resulting nodes to the fringe.

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