Discussion ---------- In this part you will discuss the following related data s
ID: 3841017 • Letter: D
Question
Discussion ---------- In this part you will discuss the following related data structures topics: 1) Discuss the structure, behavior, and practical uses of the two data structures (grid and stack) used in maze solving program. 2) Discuss the space and time efficiencies of the stack-based backtracking algorithm used in our maze solving program. 3) Discuss how you could use a graph data structure to represent and solve a maze. Your discussions should be clear, complete, correct, and well organized. All this should be done in python
Explanation / Answer
Stack Panel acts like a stack of things placed one after another. It can be horizontal or vertical. Unlike Grid you cannot access particular place in a stack panel, every next element will be placed after one another in a sequence.
Stack Panel has Vertical Orientation by default and left to right flow by default if selected horizontal orientation
When you create a new project, grid is there for you by default. This grid has one row and one column and make it a one large cell covering the whole space. Grid is like a matrix and you can place your element by telling it the row and column.
A maze can be thought of an m x n grid of cells.The row numbers are 0..m-1 and the column number are 0..n-1. Each grid cell is like a room with 4 sides. A side of the room is either a complete wall or a wall with an open door (entry way). We can represent a room with 4 bits nesw (using clockwise starting from north) . A bit value of 1 indicates that there is an open entry way on that side of the room and a bit value of 0 indicates that there is no way (i.e. complete wall). Thus 1001 indicates that north and west has doors and other two sides don't. We can associate a position with each bit starting from the rightmost bit. Thus, north has bit position 3, east has bit position 2, south has bit position 1, and west has bit position 0. We can represent this with a single number (in this case 9) in the range 0..15. Assume that there is light in each room so you can see (Is this sentence important for programming? :-)). A mouse is initialized placed in some room and a cheese is placed in another (far from the mouse). Can you help the mouse eat the cheese?
You will solve this problem using two different implementations. The first version uses a stack and the second one uses a queue. So, you need to implement a stack ADT as well as queue ADT. Your application will have two versions, one using stack and one using queue. (Note that the application itself is using a different ADT as opposed to an ADT using a different implementation. There is a difference!! So, you need to rewrite the application). The STD has built-in stack and queue ADTs. You can use them for testing your Maze ADT fast, but you should implement your own stack and queue ADTs. They should use linked-list approach and should not depend on another ADT such as list. In other words, build stack and queue from scratch. Note that your implementations should follow all the guidelines discussed in class.
Build a Maze ADT that can be used to load a maze from a file, solve it, and print the solution. The main program uses the Maze ADT to solve the problem. You need two versions of the Maze ADT, one using stack and the other using queue. Call them maze-stack.h[cc] and maze-queue.h[cc].
2.
Time complexity is an exponential relationship O(bm) where b is the branching factor, and m is the maximal depth of a leaf node. Number of nodes generated:
Space complexity is O(bm) or O(m). It is a linear relationship, not an exponential relationship like the Time complexity.
The time complexity for a Depth first search is O(bm), where b is the branching factor and m is the maximum depth. The time complexity is the same with respect to the Breadth first search. The Depth first search may be faster because it has a better chance of finding a solution with respect to exploring nodes that are deeper in the tree, instead of only a small portion of the beginning nodes.
The drawback to the Depth first search is that it can get stuck gong down the wrong path and never recover, with respect to time, from an unlucky choice at one of the nodes near the top of the tree. The Depth first search will continuing going downward even though a solution may be very close to the top of the tree.
3.graph with each cell representing a node. This gives very easy way to setup walls (no connectivity between nodes), traps (some property of edges), etc. as well as base for solving the maze. As as side effect it doesn't restrict number of connections between cells, i.e. it could be hexagon based maze.
A matrix with 4 bits representing ability to move in each direction. Same graph algorithms applied if the matrix is treated as connectivity matrix. The downside is that non-flat mazes (2D) could be harder to comprehend and cells must be uniform in shape, i.e. more bits that 4 maybe confusing and connection between cells of different shape could be hard to describe.
example