THIS IS RELATED TO DISCRETE MATHMATICS. THIS CAN BE PERSONEL OPINION, I CANT THI
ID: 3567836 • Letter: T
Question
THIS IS RELATED TO DISCRETE MATHMATICS. THIS CAN BE PERSONEL OPINION, I CANT THINK OF ANYTHING.
1) Describe the real-life problem you chose and explain how you solved it (now this was before you know the graph theory).
2)Consider the problem again now but as a graph, please describe/draw your graph and how it represent your problem?
3)Give a short description on what known algorithm in graph theory would you use to come up with your desired solution to the real-life problem you have chosen. Comment
Explanation / Answer
a) The real world problem of snake and ladder game can be the one:
Given a snake and ladder board, find the minimum number of dice throws required to reach the destination or last cell from source or 1st cell. Basically, the player has total control over outcome of dice throw and wants to find out minimum number of throws required to reach last cell.
If the player reaches a cell which is base of a ladder, the player has to climb up that ladder and if reaches a cell is mouth of the snake, has to go down to the tail of snake without a dice throw.
Before knowing the concepts of graph theory we would just randomly/manually count the total possibilities to reach from source cell to target cell considering all possibilites of reaching a ladder if present in between and not landing snake.
b)The above problem can be represented graphically as..
The idea is to consider the given snake and ladder board as a directed graph with number of vertices equal to the number of cells in the board. Every vertex of the graph has an edge to next six vertices if next 6 vertices do not have a snake or ladder. If any of the next six vertices has a snake or ladder, then the edge from current vertex goes to the top of the ladder or tail of the snake.
c) . The problem reduces to finding the shortest path in a graph. Since all edges are of equal weight, we can efficiently find shortest path using Breadth First Search of the graph.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.