Thank you for the kind comment on my videos. I am glad that you are finding them helpful. I'm happy to make more videos, but could you explain a bit more about what you mean? Do you mean questions that ask you to explain why an algorithm does something, or do you just mean Decision Maths exam questions in general?
@@mathshelpwithmrorys8555 Hi, I guess the first type so for example Qs when they ask you to explain how an algorithm may change if something was altered, or explain why the algorithm may or may not work. Typically these questions are the last section of a big question, and my further maths teacher says it’s these Qs that separates Bs from As and A*s. Many thanks!
Thanks Mr.Orys for the video. So we now know that the solution must fall within 64 and 71. My question is will this solution be a classical solution (where each vertex is visited only once) or will it be a practical solution (where each vertex is visited at least once). I understand that a classical solution is actually a subset of practical solution.
This provides a lower bound for the classical problem. If you want to find a lower bound for the practical problem, you would need to consider a table of least distances rather than the arcs.
I don't have the space to provide a proof, and there are several already online that you can find, but it can be done as a thought experiment. Consider the perfect route for the salesman. With one location deleted, the remaining part of the optimum route would be a tree. In order to put the location back in, under an optimal solution, you would need to add two more arcs in (think of a perfect loop being the optimum solution). Since we can do this with each vertex, and the method is unliekly to provide a valid solution, it can be taken as a lower bound.
I love your videos!!! However, I’ve reached to a point where my lower bound after eliminating my vertex a was greater than my original minimum spanning tree. What can I conclude from this situation!!!! Thank you!!
I was not sure why the exam questions always ask for lower bound and upper bound for TSP problem; thanks for clarifying!
Love your videos, could you do videos on questions that require you to explain in decision maths?
Thank you for the kind comment on my videos. I am glad that you are finding them helpful. I'm happy to make more videos, but could you explain a bit more about what you mean? Do you mean questions that ask you to explain why an algorithm does something, or do you just mean Decision Maths exam questions in general?
@@mathshelpwithmrorys8555 Hi, I guess the first type so for example Qs when they ask you to explain how an algorithm may change if something was altered, or explain why the algorithm may or may not work. Typically these questions are the last section of a big question, and my further maths teacher says it’s these Qs that separates Bs from As and A*s. Many thanks!
Thanks Mr.Orys for the video. So we now know that the solution must fall within 64 and 71. My question is will this solution be a classical solution (where each vertex is visited only once) or will it be a practical solution (where each vertex is visited at least once). I understand that a classical solution is actually a subset of practical solution.
This provides a lower bound for the classical problem. If you want to find a lower bound for the practical problem, you would need to consider a table of least distances rather than the arcs.
why does thi approach work??can u plz provide a proof of it.
I don't have the space to provide a proof, and there are several already online that you can find, but it can be done as a thought experiment. Consider the perfect route for the salesman. With one location deleted, the remaining part of the optimum route would be a tree. In order to put the location back in, under an optimal solution, you would need to add two more arcs in (think of a perfect loop being the optimum solution). Since we can do this with each vertex, and the method is unliekly to provide a valid solution, it can be taken as a lower bound.
@@mathshelpwithmrorys8555 can u plz provide link to the proof ...plz couldnt find it online
and do u have c++ code of this approach..couldnt find it online
@@divanshmahajan1769 No, sorry.
I love your videos!!! However, I’ve reached to a point where my lower bound after eliminating my vertex a was greater than my original minimum spanning tree. What can I conclude from this situation!!!! Thank you!!
Thanks. Unfortunately I can only conclude that there is an error in your working, without seeing it in person.
yo mUsic!