TSP: отношение к худшему случаю

Question

Как часть моей диссертации в средней школе, я описываю эвристику для проблемы с продавцом. Я читал this вид кейса (Page 8), но я не могу unserstand, что означают эти предложения:

Хронометраж для NN, как описано в Θ (N^2 ). [...] В частности, нам гарантировано, что NN (I)/OPT (I) ≤ (0. 5) (log_ {2} N + 1).

Эта часть очень понятна для меня. Но тогда:

Нет существенно лучшей гарантии можно, однако, есть случаи, для которых отношение растет в Q (LogN).

В чем смысл Есть экземпляры, для которых?

То же самое происходит и с жадным алгоритмом:

... но худшие примеры, известные Жадный только сделать соотношение растут как (LogN)/(3 журнал журнал N).

В чем смысл этих заявлений? Имеет ли это отношение к неевклидовым экземплярам (я бы так не подумал, потому что вам просто нужно прочитать столбец матрицы расстояния, чтобы решить его)? Или просто экземпляры, например. несколько узлов на том же расстоянии от стартового узла, что требует, чтобы алгоритм разбивал дерево решений или что-то подобное?

EDIT: Благодаря @templatetypedef (ваш ответ будет по-прежнему быть приняты как правильно), все это имеет смысл. Однако я хотел бы спросить, знает ли кто-нибудь какой-либо пример (или даже просто ссылку) этих конкретных графиков (я не имею в виду, какой алгоритм). Я не думаю, что это слишком много вне темы, это скорее добавит что-то полезное в эту тему.

Answer 1

Посмотрите на эти два заявления бок о бок:

В частности, гарантируется, что NN (I)/OPT (I) ≤ (0 5) (log_ {2} N + 1).

Однако существенно более высокая гарантия возможна, поскольку существуют случаи, когда отношение растет как Θ (logN).

Это первое утверждение говорит, что алгоритм NN, в худшем случае, дает ответ, что это (примерно) в пределах 1/2 Lg N истинного ответа (чтобы убедиться в этом, просто умножить обе части на OPT (I)). Это замечательные новости! Естественный вопрос о последующих действиях заключается в том, является ли фактическая граница еще более жесткой. Например, этот результат не исключает возможности того, что мы могли бы также иметь NN (I)/OPT (I) ≤ log log N или что NN (I)/OPT (I) ≤ 2. Это гораздо более жесткие границы.

Вот где второе заявление приходит.В этом утверждении утверждается, что существуют известные примеры TSP (то есть конкретные графики с весами на них), где отношение NN (I)/OPT (I) равно Θ (log n) (то есть отношение пропорционально log от числа узлов в графе). Поскольку мы уже знаем о таких источниках, нет никакого способа, чтобы NN (I)/OPT (I) можно было ограничить сверху чем-то вроде log log n или 2, так как эти границы слишком тугие.

Однако это второе заявление в изоляции не очень полезно. Мы знаем, что есть входы, которые заставили бы алгоритм производить что-то, что отключено лог-фактором, но может ли быть возможным, что есть входы, которые заставляют его отключать намного больше; скажем, экспоненциальным фактором? С первым утверждением мы знаем, что этого не может произойти, так как мы знаем, что мы никогда не получаем больше, чем логарифмический фактор.

Подумайте об этих утверждениях в два этапа: первое утверждение дает верхнюю границу о том, насколько плохо может быть аппроксимация - она ​​никогда не хуже, чем 1/2 lg N + 1 фактор оптимальности. Во втором заявлении дается нижняя граница о том, насколько плохим может быть приближение - существуют конкретные случаи, когда алгоритм не может сделать ничего лучше, чем приближение оптимального ответа Θ (log N).

(Обратите внимание, что Θ (журнал N) здесь не имеет ничего общего с выполнением - «что-то логарифмическое» это просто способ сказать)

Забегая вперед, следить за оба верхних границы и нижние границы. Эти двое в совокупности говорят вам намного больше, чем каждый из них в отдельности.

Удачи вам!