percorso non ciclo a tutti i nodi

Question

C'è un algoritmo o un insieme di algoritmi che avrebbe lasciato a trovare il più breve distanza a piedi da un nodo di inizio arbitrario in modo che ogni nodo viene visitato in un peso, grafo non orientato? Non è del tutto Traveling Salesman, perché non mi importa se un nodo viene visitato più di una volta. (Non importa nemmeno se si rendono di nuovo al punto di partenza -. L'escursionista può finire in qualche lontano nodo fino a quando è stato l'ultimo necessario per visitare tutti i nodi) Non è abbastanza albero di copertura minimo, perché può essere che andando a -> B -> C -> a -> D è un (non univoco) percorso più breve per visitare a, B, C, e D. il mio intuito dice che questo isn' t piuttosto un problema NP, perché non ha le restrizioni che rendono problemi NP così difficile. Potrei, naturalmente, essere completamente sbagliato.

Answer 1

L'idea qui è questa:

var super_get_name = that.superior('get_name');

.

rende super_get_name in una funzione che - ogni volta che viene chiamato - Invoca il metodo that Original get_name Method. Ciò consente NUOVO get_name di chiamare la Old (Super-Class) get_name.

Ora, se il metodo originale get_name non avrà mai alcun effetto diverso da quello di restituire un singolo valore che non cambia mai, sì, questo è un po 'inutile; Puoi semplicemente salvare quel valore singolo-che-mai-cambiamenti e quindi usarlo nel nuovo get_name. Ma se il get_name originale può effettivamente fare le cose (come ad esempio, eseguire una richiesta Ajax o modificare lo stile di un elemento HTML) o se il suo valore di ritorno può cambiare (dire, se c'erano un metodo set_name corrispondente), Poi ci sarebbe una differenza importante tra ciò che fa il tuo codice (salva il valore di ritorno originale e lo use) e cos'è il codice di Crockford (salva il metodo originale e lo invoco).

Answer 2

Non sono sicuro che il galateo è quello di aggiungere una risposta ad una domanda con una risposta già accettato.

Io sono l'aggiunta questa risposta solo per il gusto di non dover passare a un'altra pagina, di non avere a che fare con i grafi planari e disuguaglianza triangolare e il fatto che questo è semplice e probabilmente più facile da capire.

hamiltoniano problema Path può essere ridotta a questo:

Supponiamo di avere un algoritmo di tempo polinomiale per risolvere il nostro problema di trovare un minimo di passeggiata di peso che le visite tutti i vertici.

Dato un grafico che dobbiamo decidere esiste o meno un percorso hamiltoniano, abbiamo alimentano così com'è, all'algoritmo problema attuale, modificando pesi giuntati = 1. Se l'algoritmo restituisce un valore> n-1 , allora non v'è alcun percorso hamiltoniano nel grafico originale, il resto c'è.

Quindi questo problema è NP-hard.