0 votes 0 votes Travelling Salesman problem considering the triangle inequality ,tell the procedure of finding the approximate solution in polynomial time using a suitable example. Graph Theory travelling-salesman-problem + – LavTheRawkstar asked Apr 15, 2017 recategorized Jun 24, 2022 by Arjun LavTheRawkstar 1.5k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply Devshree Dubey commented Apr 15, 2017 reply Follow Share Take up a sample prob and use either Dynamic Programming or Greedy Technique. U can search for examples ol. :) 1 votes 1 votes LavTheRawkstar commented Apr 15, 2017 reply Follow Share dear sir please i beg you please solve it 0 votes 0 votes Devshree Dubey commented Apr 15, 2017 reply Follow Share lav, Don't beg. I'll try to ans. Yeah. :) 1 votes 1 votes Please log in or register to add a comment.
1 votes 1 votes Refer d link mentioned below for more information: http://www.geeksforgeeks.org/travelling-salesman-problem-set-1/ https://www.quora.com/How-do-I-solve-the-traveling-salesman-problem-using-dynamic-programming The above mentioned two links provide solution using Dynamic Programming. Please read thru them. Explanation is very gud. :) Devshree Dubey answered Apr 15, 2017 Devshree Dubey comment Share Follow See all 4 Comments See all 4 4 Comments reply LavTheRawkstar commented Apr 15, 2017 reply Follow Share dear sir i visited the links i know how to solve prolbme using dynamic programming but i do not know triangle inequality. please tell what is this triangle inequality? 0 votes 0 votes Devshree Dubey commented Apr 15, 2017 reply Follow Share @Lav, https://en.wikipedia.org/wiki/Triangle_inequality. For information regarding Triangle Inequality. :) 1 votes 1 votes LavTheRawkstar commented Apr 15, 2017 reply Follow Share i am not understanding anything written in wiki only scientists can understand written over there. dear sir please you explain in simple words what is this triangle ineuqality in regard with tsp problem 0 votes 0 votes Devshree Dubey commented Apr 15, 2017 reply Follow Share @LavTheRawkstar, Excerpt from GeeksForGeeks. http://www.geeksforgeeks.org/travelling-salesman-problem-set-2-approximate-using-mst/ In mathematics, the triangle inequality states that for any triangle, the sum of the lengths of any two sides must be greater than or equal to the length of the remaining side. [Definition of Triangle Inequality] Now did u understand? The above Principle is used as a basis and application in TSP for further solution. Ab samajh aaya. Triangle Inequality ka basic rule use hota hai for further solving the costs of TSP. I hope I m clear. Once u said u want d explanation in Hindi??Okay. :) Triangle-Inequality: The least distant path to reach a vertex j from i is always to reach j directly from i, rather than through some other vertex k (or vertices), i.e., dis(i, j) is always less than or equal to dis(i, k) + dist(k, j). The Triangle-Inequality holds in many practical situations. When the cost function satisfies the triangle inequality, we can design an approximate algorithm for TSP that returns a tour whose cost is never more than twice the cost of an optimal tour. The idea is to use Minimum Spanning Tree (MST). Following is the MST based algorithm. 1 votes 1 votes Please log in or register to add a comment.