MiniProjectPResentationTemplate (1)1.pptx

Presentation

1. Bangalore Institute of Technology K.R. Road, V.V. Pura m , Bengaluru.-560004. D epartment of Computer Science & Engineering TICKET TO RIDE Presented by [Diploma] 1.Tejaswini N 2. Hemalatha D 3. Pooja M . Benakatti 4.Sunil R Under the Guidance of Neetha Das B.E., MTech. Associate Professor

2. Bangalore Institute of Technology K.R. Road, V.V. Pura m , Bengaluru.-560004. D epartment of Computer Science & Engineering INTRODUCTION

3. Bangalore Institute of Technology K.R. Road, V.V. Pura m , Bengaluru.-560004. D epartment of Computer Science & Engineering TICKET TO RIDE [BOARD GAME] EXPLAINED:- Ticket to Ride is a railway-themed German-style board game designed by Alan R. Moon. It was illustrated by Julien Delval and Cyrille Daujean and published in 2004 by Days of Wonder. The game is also known as Zug um Zug (German).

4. Bangalore Institute of Technology K.R. Road, V.V. Pura m , Bengaluru.-560004. D epartment of Computer Science & Engineering

5. Bangalore Institute of Technology K.R. Road, V.V. Pura m , Bengaluru.-560004. D epartment of Computer Science & Engineering Gameplay At the beginning of the main game, players are dealt four train car cards as their playing hand. They are also dealt three Destination Ticket cards, each showing a pair of cities on a map of the United States and southern Canada. These become goals, representing two end-points that players secretly attempt to connect. The player must keep at least two of these destination cards and discard unwanted tickets, if any, to the bottom of the stack. Once kept, a destination ticket may not be discarded for the rest of the game. Each player selects a group of 45 colord train pieces with a matching scoring marker. Each turn, the player has to choose from one of three options: 1.draw two railway car cards in various colours from the draw piles (with the restriction that drawing a wild Locomotive card face up forfeits drawing another card), or draw three additional destination ticket cards and keep at least one (replacing undesired tickets at the bottom of the stack), or play their collected railway car cards from their hand to claim a route on the board and place the corresponding number of train pieces from their store on the claimed route, thereby earning points. 2.The routes are of varying lengths (requiring varying numbers of matching coloured cards), and only a single player can claim each discrete route marked on the board. Some cities are connected by two parallel routes that can each be claimed by a different player (unless the game is played by three or fewer players, in which case only one of the routes can be claimed). The same player may not claim both parallel routes between two adjacent cities. Longer routes are worth progressively more points than shorter routes, e.g., a route of length four is worth more than two routes of length two. 3.On their turn, a player can claim any route on the board that has not already been claimed, regardless of whether the route helps to complete their destination tickets. The routes score points by themselves, as mentioned above, but routes not connected to a player's destination do not help them reach the destination or complete their destination ticket.

6. Bangalore Institute of Technology K.R. Road, V.V. Pura m , Bengaluru.-560004. D epartment of Computer Science & Engineering Introduction To The Project Description and Explanation

7. Bangalore Institute of Technology K.R. Road, V.V. Pura m , Bengaluru.-560004. D epartment of Computer Science & Engineering Ticket to Ride Simon received the board game Ticket to Ride as a birthday present. After playing it with his friends, he decides to come up with a strategy for the game. There are n cities on the map and n-1 road plans. Each road plan consists of the following: Two cities which can be directly connected by a road. The length of the proposed road. The entire road plan is designed in such a way that if one builds all the roads, it will be possible to travel between any pair of cities. A ticket enables you to travel between two different cities. There are m tickets, and each ticket has a cost associated with it. A ticket is considered to be useful if there is a path between those cities.

8. Bangalore Institute of Technology K.R. Road, V.V. Pura m , Bengaluru.-560004. D epartment of Computer Science & Engineering Simon wants to choose two cities, u and v , and build a minimal number of roads so that they form a simple path between them. Let (st) be the sum of costs of all useful tickets and ( sr) be the sum of lengths of all the roads Simon builds. The profit for pair ( u,v ) is defined as ( st-sr) . Note that u and v are not necessarily unique and may be the same cities. Given n road plans and m ticket prices, help Simon by printing the value of his maximum possible profit on a new line.

9. Bangalore Institute of Technology K.R. Road, V.V. Pura m , Bengaluru.-560004. Department of Computer Science & Engineering INPUT FORMAT:- The first line contains single positive integer , n , denoting the number of cities. 1. Each of the n-1 subsequent lines contains three space-separated integers describing the respective values of u, v , and l for a road plan, where 1 < u, v < n, and u!=v 2. Here, u and v are two cities that the road plan proposes to connect and l is the length of the proposed road. 3. The next line contains a single positive integer u, v , denoting the number of tickets. 4. Each of the m subsequent lines contains three space-separated integers describing the respective values of u , v , and c for a ticket from city u to city v (where c is the cost of the ticket).

10. Bangalore Institute of Technology K.R. Road, V.V. Pura m , Bengaluru.-560004. D epartment of Computer Science & Engineering Constraints:- 1. 1 < n < 2x10^5 2. 1 < m < 10^5 3. 1 < l, c < 10^9 Output Format:- Print a single integer denoting the maximum profit Simon can make.

11. Bangalore Institute of Technology K.R. Road, V.V. Pura m , Bengaluru.-560004. D epartment of Computer Science & Engineering 2. Various approaches to solve the problem – Graph representations: Adjacency List, Adjacency Matrix – Shortest paths: Dijkstra, Floyd Warshall – Graph traversal: BFS, DFS – Minimum Spanning Tree: Prim, Kruskal – Topological sorting of directed graphs

12. Bangalore Institute of Technology K.R. Road, V.V. Pura m , Bengaluru.-560004. D epartment of Computer Science & Engineering One of the concept that can be applied is:- Minimum Spanning Tree: Prim, Kruskal Minimum Spanning Tree :- • A spanning tree of the full graph would guarantee that any destination ticket is fulfilled. • But payers do not have enough train tokens to claim a spanning tree of the full graph (45 vs 108). • Thus, the best strategy is to capture a minimum spanning tree or forest of a subset of vertices (based on the destination tickets). • Steiner Tree / Forest: Given an undirected, weighted graph

13. Bangalore Institute of Technology K.R. Road, V.V. Pura m , Bengaluru.-560004. D epartment of Computer Science & Engineering 3.Data structures applied and their usage in the application Graphs - Vertices and Undirected Edges * A Vertex is a synonym for a node. A vertex is represented by a circle. * Undirected Edge : No direction b/w 2 vertices. (1,2) is same as (2,1) is a undirected edge. 2. Graph Representation - Adjacency List :- An array of linked list is used. The size of the array is equal to the number of vertices. Let the array be an array[]. An entry array[ i ] represents the linked list of vertices adjacent to the ith vertex. This representation can also used to represented a weighted graph

14. Bangalore Institute of Technology K.R. Road, V.V. Pura m , Bengaluru.-560004. D epartment of Computer Science & Engineering Traversal [Depth First Search]:- * DFS is a method of traversing a graph by visiting each node of the graph systematic order i,e to search deeper in the graph. *In DFS, a vertex u is picked as a source and is visited. The vertex u is at the point is unexploded. The exploration of vertex u is postponed and a vertex v adjacent to u is picked and visited. Now search begins at vertex v. * The search will be terminated when all vertex have been examined. * DFS is implemented using STACK. - Weighted Graph :- *A graph in which the edges are already specified with suitable weight is known as a weighted graph. * Weighted graphs can be further classified as directed weighted graphs and undirected weighted graphs .

15. Bangalore Institute of Technology K.R. Road, V.V. Pura m , Bengaluru.-560004. D epartment of Computer Science & Engineering - Stack Approach :- * Stack is a linear data structure that follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out). LIFO implies that the element that is inserted last, comes out first and FILO implies that the element that is inserted first, comes out last. Brute Force Approach :- * A brute force approach is an approach that finds all the possible solutions to find a satisfactory solution to a given problem. The brute force algorithm tries out all the possibilities till a satisfactory solution is not found.

16. Bangalore Institute of Technology K.R. Road, V.V. Pura m , Bengaluru.-560004. D epartment of Computer Science & Engineering 4.Problem Explained:- Sample Input 7 U V L 1 2 1 1 3 1 1 4 4 4 5 1 4 6 1 4 7 1 5 U V C 5 7 3 3 6 2 3 4 10 2 7 15 1 6 7 Sample Output 13 Simon can maximize his profit by choosing the pair(3,6) . The roads on the path between them are (3,1),(1,4),and (4,6). The total length is sr=1+4+1=6 The useful tickets are (3,6), (3,4),and (1,6). The total ticket cost is st=2+10+7=19 . The profit is st - sr=19-6 = 13

17. Bangalore Institute of Technology K.R. Road, V.V. Pura m , Bengaluru.-560004. D epartment of Computer Science & Engineering 1.N is number of vertex. 2. n-1 should be edges . 3. M= cost returns :- returns max in such a way that 4. U and V are nodes and vertices . 5. L is length between the U & V 6. C is the cost of the ticket from on path to another. Formula is Sum of any pair ( a,b ) travel cost – sum of length of the city ( s,d ) road length(L)

18. Bangalore Institute of Technology K.R. Road, V.V. Pura m , Bengaluru.-560004. D epartment of Computer Science & Engineering Conclusion :- Ticket to ride is a board game of 90’s where we have n number of routes to travel from source to destination , But in case to travel in spite of cost here we specify the number of tickets we need to travel , once we have the, Sufficient tickets using that we want to find the best routes for travelling with maximum profit is the ultimate , Goal of the game. Using graph data structure we solved the problem to get the maximum profit with best routes, We have used adjacent list and DFS is the best technique to solved the query and return the maximum efficiency.

19. Bangalore Institute of Technology K.R. Road, V.V. Pura m , Bengaluru.-560004. D epartment of Computer Science & Engineering 5. Question and Answers : - Why DFS is used not BFS traversal in the problem? DFS uses the stack approach which traverse and keep the track of the traversed path so can at finally we can have the maximum sum by comparing with every possible returned. But BFS also same as DFS but uses the queue approach it also traverses but deletes the traversed once and doesn't keep the track of the path so we can return the max but can’t compare with all. 2. Why to use undirected graph, adjacency list ? Here, the traversal should be of both bidirectional because we are checking each and every path in both directions so, we don’t miss and portable path, but we cant do it in directed it is one way traversal. Adjacency list has the approach of linked list where the efficiency, traversal and implementa - -tion, is quite and efficient compared to adjacency matrix.