If the TSP wants to find a tour with minimum total weight why can't we just use the smallest of the lower bounds? Why do we want to trap the solution between an upper and a lower bound (that is chose sg that is higher than the current minimum)? So why isn't the lower bound the optimal solution?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
Because a lower bound is not a solution. Finding a lower bound of weight $L$ says that any optimal solution must have weight $W$ such that $L \leq W$. Put differently, finding a lower bound says that the minimal solution cannot have a lower weight than the lower bound.
-
$\begingroup$ Thank you. I think I get that. I think my main problem is what we consider "optimal" in a TSP. Because in general if I want to minimize a distance I would want to choose the shortest I can find. Why isn't the minimum optimal? $\endgroup$ Commented Dec 8, 2022 at 9:45
-
$\begingroup$ To add an example: sorting a list has a lower bound of $n$, because you can't sort a list without inspecting all of its elements, but, in the most general setting, there are no $O(n)$ solutions. That is because, demonstrably, there is a more significant lower bound of $O(n \log n)$ $\endgroup$ Commented Dec 8, 2022 at 9:48
-
$\begingroup$ @KündücsEszkábál For most problems, there are plenty of lower bounds one can find. The best lower bound (in the sense of accuracy) is an exact solution, but that's not always a result you have available, or a result you want to spend the necessary time to calculate. In such a case you have to settle for worse lower bounds. $\endgroup$– ArthurCommented Dec 8, 2022 at 11:18
-
$\begingroup$ To give another example of a lower bound that is not the optimal solution: say that I have a huge graph, I need to solve TSP for. But I find that alle edges have weight $w$. Since any possible solution will need to traverse at least one edge (in reality way more, but at least 1), I know that any solution has <i>at least</i> total weight $w$. So clearly $w$ is not a solution, although it does say that any solution is larger than $w$. Then $w$ is (albeit uninformative) lower bound of a solution. $\endgroup$– LourensCommented Dec 9, 2022 at 10:45
-
$\begingroup$ Thank you all, I appreciate your help. It makes sense know. $\endgroup$ Commented Dec 9, 2022 at 13:02