If you'd taken a different vertex out to get your lower bound, could you have found a different (possibly greater) lower bound? Also, surely it's possible, by coincidence/chance, to obtain the optimal solution when finding the upper bound if you happen upon the right starting point?
can't agree with the second exapmle. the problem states the starting point is A but you start from B, so you'd have to add 16 to your total to get from A to B...no?
In Travelling Salesman problem you have to visit vertices exactly once. And in your example you visit D twice... How is this relevant to Travelling Salesman problem?
If I'm not mistaken all he did was run a verification algorithm. You can create/run a verification algorithm on an NP-complete problem to demonstrate that the problem is polynomial time but that doesn't mean you can create a solution to the problem in polynomial time. I could demonstrate that I could be anywhere in the world in constant time O(1) by teleportation and going directly to my destination but that doesn't mean that there exists a solution in O(1) time constant time.I hope that makes sense.
I don't think people understand the tutorial at all. He didn't find a solution because there is not always an optimal solution to the problem. What he told you is that if you find a root that has weight between those two values then it is a really good solution.
TSP states you have to arrive back at original position. This vid does not take that into consideration. Plus, how can the distance from A, D, C be 33 and the distance from A, B, C be 34 and the distance from A, E, C be greater than them both at 45 when the triangles have 90 degree angles?
hello... how to write programs using HEAPSORT to solve Travelling Salesman Problem - TSP on programming language C ... and I need code :( im form Viet Nam...thanks
Because the graph must have at least two paths, there must be a circle in the graph. And you have to to reach C via the shortest path, so we have to add 18 and 19.
It's very well known that in the Travelling salesman problem, the salesman starts in a "home" city, visits all the cities on his agenda exactly once and returns to his home city. I'm afraid you are the one speaking BS.
There's no need to be rude, especially when you're wrong it can make you seem a bit ignorant. It's simple deductive reasoning which holds true within, but not limited to, the rules of the traveling salesman problem. Given any route, the shortest route is shorter or equal to that route. That's all I'm stating. It is also well known that, within the traveling salesman problem, one may assume that any node can be connected to any node. Therefore, I suggest taking the shortest route from A to C. This is of course the direct route which the author of the video neglected to draw but can be assumed to be less than or equal to the indirect route through B.
I'm doing an assignment of TSP... I have to find a (non-evolutionary algorithm ) to solve the problem... do u know wt types of algorithms that are not belong to the evolutionary algorithm class? and does the dynamic algorithms consider as a non- evolutionary algorithms?
What kind of question is this?(lol) The initial question asks for the lower and upper bounds and that's literally how he ends the problem.. by telling you those answers. Did you maybe confuse what the question is asking?
Erm, how it C>D shorter than C>E? I know you have 19 for C>D versus 23 for C>E, this is clearly wrong. C>D, (the hypotenuse, as this looks like a right angled tri), should ofcourse be longer than the other two sides. I think you may have made a calculation error...
Yeah, the surface must be curved but it’s somewhat irrelevant to the actual point. It’s just there for a visual help, not to present an actual scale image of the problem.
Don't normally comment on videos but thought the explanation was super clear. Thank you!
I can happily say that this is a maths (or math) teacher at my school and I can get help like this anytime I need it!
0:00 "konitshiwawa wannano"
*Instant Skip*
If you'd taken a different vertex out to get your lower bound, could you have found a different (possibly greater) lower bound? Also, surely it's possible, by coincidence/chance, to obtain the optimal solution when finding the upper bound if you happen upon the right starting point?
You did not mention the fact that you only cann visit a point once. Are you considering that in your problem?
can't agree with the second exapmle. the problem states the starting point is A but you start from B, so you'd have to add 16 to your total to get from A to B...no?
I am writing a math project about TSP, and I am looking for information about Christofides' algorithm. Have you made any videos about that? :)
In Travelling Salesman problem you have to visit vertices exactly once. And in your example you visit D twice... How is this relevant to Travelling Salesman problem?
If I'm not mistaken all he did was run a verification algorithm. You can create/run a verification algorithm on an NP-complete problem to demonstrate that the problem is polynomial time but that doesn't mean you can create a solution to the problem in polynomial time. I could demonstrate that I could be anywhere in the world in constant time O(1) by teleportation and going directly to my destination but that doesn't mean that there exists a solution in O(1) time constant time.I hope that makes sense.
Thank you your heart is in the right place! TSP is tricky no matter who you are!!!
i somehow manage to find upper bound 78 from A > B > C > E > D > A. did i do something wrong? or what did i misunderstood?
Why did you start from B in your minimum spanning tree?
You are travelling D twice, that doesn't fulfill the requirements of TSP!
Liaquath Hassan I
How can in a triangle sum of two sides is smaller than the third... In triangle AEB 16+4
You did not solve anything... Why the title?
yea... not quite
I don't think people understand the tutorial at all. He didn't find a solution because there is not always an optimal solution to the problem. What he told you is that if you find a root that has weight between those two values then it is a really good solution.
TSP states you have to arrive back at original position. This vid does not take that into consideration. Plus, how can the distance from A, D, C be 33 and the distance from A, B, C be 34 and the distance from A, E, C be greater than them both at 45 when the triangles have 90 degree angles?
If it’s on a curved surface.
Nice video..tnx..there is some problem at minute 3..for the problem the path is BE,EA,AD..u have written BE,ED and AD
hello...
how to write programs using HEAPSORT to
solve Travelling Salesman Problem - TSP on programming language C ...
and I need code :(
im form Viet Nam...thanks
You can hear him laughing when talking about the karma at 4.46.
Why the lower bound is 62? Why add 18 and 19?
You will know!
Yukai Zhong Haha, I am solving the NP-Complete problem!
You are the boss!
Yukai Zhong you bet!
Because the graph must have at least two paths, there must be a circle in the graph. And you have to to reach C via the shortest path, so we have to add 18 and 19.
I think you should've made clear why you could travel a node twice, when thinking of an upper bound
Could someone tell me whether or not ABC and ADC are triangles??? 16+18
None of them are triangles, it is only a simple representation and the distances in the draft are not accurate.
"there isn't really an algorithm for giving you the best route"
How about brute force, held-Karp, branch-and-bound?
Bruteforce is not the right way without harming alot due to the needed (energy/time). Think in a big scale
@@PflanzenChirurg It might be feasible if the interval is small enough
@@jamilhneini1002 logic is the only Thing you can apply to improve. Not any CPU Performance
@@PflanzenChirurg reducing the possible values to make it feasible is a very logical way
@@jamilhneini1002 nope, not really. You Need a complete logic to make it feasible ;)
he solved the unsolvable! (not)
Thank you for your great explanation!!!
Is this a typical tsp? cos first it is not complete and second there is no triangular property (such as ABE)
Man ur amazing .My teacher is trash , wish i had someone like u
Right answer is 76, I dont understand, what is 62 in this case
Does anyone know, who got up with the idea of "the optimal TSP-route"?? :-)
TSP can't visit repeated vertex (not even to go back to the "start vertex") You are talking BS!
Irrelevant. The shortest path from A to C has to be
It's very well known that in the Travelling salesman problem, the salesman starts in a "home" city, visits all the cities on his agenda exactly once and returns to his home city. I'm afraid you are the one speaking BS.
There's no need to be rude, especially when you're wrong it can make you seem a bit ignorant.
It's simple deductive reasoning which holds true within, but not limited to, the rules of the traveling salesman problem.
Given any route, the shortest route is shorter or equal to that route. That's all I'm stating.
It is also well known that, within the traveling salesman problem, one may assume that any node can be connected to any node. Therefore, I suggest taking the shortest route from A to C. This is of course the direct route which the author of the video neglected to draw but can be assumed to be less than or equal to the indirect route through B.
Rajiv Krijnen I'm not sure if you thought I was replying to you, but just in case: I was replying to Farzin Shargh
Well that kind of makes sense. I was struggling to see the relevance of your comment in relation to mine. My bad.
Seeing how to do this on a table would be awesome? :)
Thanks for your help!
Can Someone Explain Why 18 and 19 came
Why can't you use Dijkstra's shortest path algorithm?
Because it's greedy.
^Pun intended?? ;) :P
adcbe... avoid 23... since all the outside routes are shorter then inside routes.
It's not certain that 62 works, whereas 76 definitely works
i am sorry but why isn't the lowest also the optimal?
you only show that how to solve the travelling salesman problem but why you doesn't apply methods like dynamic programming and greedy ??
I'm doing an assignment of TSP... I have to find a (non-evolutionary algorithm ) to solve the problem... do u know wt types of algorithms that are not belong to the evolutionary algorithm class? and does the dynamic algorithms consider as a non- evolutionary algorithms?
Can you please make a video on nearest neighbor algorithm on a table pleaseee? :) P.S your videos are awesome
the lower bound isn't 60???
Mic is muffled, can't understand without distraction, skipping. :(
dude u r wrong...!!!! Y u connected C with both 18 and 19?????
Thank you
What is the exact answer?
What kind of question is this?(lol) The initial question asks for the lower and upper bounds and that's literally how he ends the problem.. by telling you those answers. Did you maybe confuse what the question is asking?
helped me a lot...thanks so much
Erm, how it C>D shorter than C>E? I know you have 19 for C>D versus 23 for C>E, this is clearly wrong. C>D, (the hypotenuse, as this looks like a right angled tri), should ofcourse be longer than the other two sides. I think you may have made a calculation error...
the right angled triangles are just for visualisation, if the lengths of the sides were drawn correctly the triangles would not be right angled.
saav khotu chhe. aam kai thay j ny. khotino
le graphe est en contradiction avec la géométrie euclidienne
Yeah, the surface must be curved but it’s somewhat irrelevant to the actual point. It’s just there for a visual help, not to present an actual scale image of the problem.
thanks
>konnichiwag1
AWESOME!
good 😊
thank you!!!
Thanks for that :D
Anyone else get 75?..
Right from the start ....closest neighbor of A is E not D. Your numbers are out of proportion
konichiwagwan!
thnxxxxxxxxxxxxxxxx
koiln chatpa
Anyone notice that in some of the triangles the legs are longer the hypotenuse? You broke geometry.........
That was a graph bro. A graph from graph theory. It was not a geometrical shape. It was several nodes connected via pointers.
doobmar
waste vdo
Stop with mouth sounds.
the fuckkk !!!!! 18+19 is 62????????????? really??????????? at 3:24 minutes.
+guddu bhagat wouldn't it be nice if you try a little hard to keep up with things he added 18 and 19 to 25 which gives 62 😃
guddu chutiya sala
your hypotenuse cannot be shorter(lower value) than either side of the triangle; therefore your solution is invalid.
+Shawn Lapuz Those are not triangles, it's a simplified graph.