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.
CS 340 Milestone One Guidelines and Rubric Overview: For this assignment, you will implement the fundamental operations of create, read, update,
Retail Transaction Programming Project Project Requirements: Develop a program to emulate a purchase transaction at a retail store. This
7COM1028 Secure Systems Programming Referral Coursework: Secure
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
CS 340 Final Project Guidelines and Rubric Overview The final project will encompass developing a web service using a software stack and impleme
