TSP: il peggiore rapporto case cresce

Question

Come parte della mia tesi di scuola superiore, sto descrivendo l'euristica per il problema del commesso viaggiatore. leggevo this sorta di caso di studio (pagina 8), ma non riesco a unserstand cosa significano queste frasi:

Il tempo di esecuzione per NN, come descritto è Θ (N^2 ). [...] In particolare, è garantito che NN (I)/OPT (I) ≤ (0. 5) (log_ {2} N + 1).

Questa parte è molto chiara per me. Ma poi:

n sostanzialmente migliore garanzia è possibile, tuttavia, in quanto vi sono casi in cui il rapporto cresce come Θ (log).

Qual è il significato di ci sono casi per cui?

La stessa cosa accade con l'algoritmo greedy:

... Ma il peggio esempi noti per Greedy solo a rendere il rapporto di crescere come (log N)/(3 log log N).

Quindi qual è il significato di tali affermazioni? Ha a che fare con le istanze non euclidee (non lo penserei perché basta leggere la colonna di una matrice di distanze per risolverlo)? O solo istanze con ad es. più nodi alla stessa distanza dal nodo iniziale che richiede l'algoritmo per dividere l'albero della soluzione o qualcosa di simile?

EDIT: Grazie al @templatetypedef (la risposta verrà comunque accettata come corretta), tutto ha un senso. Tuttavia vorrei chiedere se qualcuno conosce un esempio (o anche solo un link) di questi grafici specifici (non importa quale algoritmo). Non penso che sia troppo fuori tema, anzi aggiungerebbe qualcosa di utile all'argomento.

Answer 1

Date un'occhiata a queste due affermazioni side-by-side:

In particolare, abbiamo la garanzia che NN (I)/OPT (I) ≤ (0. 5) (log_ {2} N + 1).

Nessuna garanzia sostanzialmente migliore è possibile, tuttavia, in quanto vi sono casi per i quali il rapporto cresce come Θ (logN).

Questa prima dichiarazione afferma che l'algoritmo NN, nel peggiore dei casi, produce una risposta che è (più o meno) a 1/2 lg N della risposta vera (per vedere questo, basta moltiplicare entrambi i lati da OPT (I)). Questa è una fantastica notizia! La domanda di follow-up naturale, quindi, è se il limite effettivo è ancora più stretto di quello. Ad esempio, tale risultato non esclude la possibilità che potremmo anche avere NN (I)/OPT (I) ≤ log log N o che NN (I)/OPT (I) ≤ 2. Questi sono limiti molto più stretti.

Ecco dove arriva la seconda affermazione.Questa affermazione dice che ci sono casi noti di TSP (ovvero grafici specifici con pesi su di essi) in cui il rapporto NN (I)/OPT (I) è Θ (log n) (ovvero, il rapporto è proporzionale al log del numero di nodi nel grafico). Poiché sappiamo già di input come questo, non c'è modo che NN (I)/OPT (I) possa essere limitato da qualcosa di simile a log log n o 2, poiché questi limiti sono troppo stretti.

Tuttavia, questa seconda affermazione in isolamento non è molto utile. Sappiamo che ci sono degli input che potrebbero causare all'algoritmo di produrre qualcosa che è fuori da un fattore di log, ma potrebbe comunque essere possibile che ci siano degli input che ne causano la perdita molto di più; per esempio, con un fattore esponenziale? Con la prima affermazione, sappiamo che questo non può accadere, poiché sappiamo che non otteniamo mai più di un fattore di log.

Pensate a queste affermazioni in due passaggi: la prima affermazione fornisce un limite superiore su quanto può essere pessima l'approssimazione - non è mai peggio di un fattore N + 1 1/2 lg ottimale. Nella seconda affermazione viene fornito un limite inferiore su quanto può essere errata l'approssimazione - vi sono casi specifici in cui l'algoritmo non può fare meglio di un'approssimazione Θ (log N) della risposta ottimale.

(Si noti che il Θ (log n) qui non ha nulla a che fare con il runtime - "qualcosa logaritmica" è solo un modo di dire)

Andando avanti, tenere d'occhio sia per i limiti superiori e limiti inferiori. I due ti racconteranno molto più di quanto ciascuno faccia individualmente.

Buona fortuna con la tesi!