Newsgroup: it.scienza.informatica
Titolo: np-completo?????

domandina per evitarmi di andare a spulciare i vecchi libri.
In un grafo trovare il cammino  (senza cicli) che passa per tutti i nodi è
un problema np-complesso?
E' risovilvile in un tempo polinomiale? (dipendente chiaramente dal numero
di archi)
Esiste un algoritmo ottimo per farlo?
Grazie a quanti vorranno rispondermi?

se non ho capito male, vuoi trovare un albero di supporto...
ci sono molti algoritmi per farlo: prim, dijkstra...
devi pero' attribuire un costo ad ogni lato...
la complessita' e' polinomiale, o(n^2)
ciao, cusa se sono un po sbrigativo...
--- / --- / --- / --- / ---
Davide Piras
pir...@bbk.org
http://www.pirasdi.bbk.org
--- \ --- \ --- \ --- \ ---

...


un problema np-complesso?
Il problema e' la ricerca dei cammini Hamiltoniani. Si tratta di un problema
NP completo. Puo' essere risolto per n abbastanza piccolo utilizzando varie
tecniche di ricerca. A suo tempo ho risolto il problema per n=60 (una decina
di anni fa') su una SUN con un algoritmo in C; il programma ha comunque
impiegato qualche settimana.
Riferimenti utili si trovano su: "Sorting and searching - by D. Knuth"; si
tratta del terzo volume della serie "The art of Computer Programming".
Bye, Sonic.

 NP completo. 
Volendo essere pignoli, occorrerebbe dire che č _fortemente_ NP-completo, ovvero
non ammette neppure un algoritmo pseudo-polinomiale...
(sai com'č, ho appena dato ricerca operativa ^___^)
saluti,
	Denis

 (sai com'č, ho appena dato ricerca operativa ^___^)
Essendo ancora piu` pignoli e` NP-hard, NP-completo e` per i problemi decisionali.
-- 
# Giorgio Vecchiocattivi.
# Dip. Informatica, Universita` di Pisa. 

decisionali. 
NP-difficile.. ti prego, NP-hard mi ha sempre fatto venire in mente Moana
Pozzi (buonanima) :) 
Ridendo,
 Cris
-- 
God is Real, unless declared Integer

Scusate se mi intrometto e oltretutto in ritardo, ma vorrei fare una
precisazione:
- trovare un cammino in un grafo che passi una e una sola volta .... ecc
ecc.... NON e' NP, nè tantomeno NP hard, difficile, completo o altro. A dire
la verita' non saprei dare un algoritmo, ma avendo tempo si trova.
- trovare il cammino ecc. ecc. MINIMO e' NP !!!!!!!!!
Capito?
Se non si precisa il problema che scopo ha poi discutere sull'hard,
difficile, completezza o quant'altro? Ritengo che prima di disquisire sulle
finezze linguistiche bisognerebbe sapere di cosa si parla, e questo,
purtroppo, non esiste esame che lo insegni.
Alex
--
Posted from 
ro...@polic.cilea.it
 [131.175.215.1]
via Mailgate.ORG Server - 
http://www.mailgate.org

 - trovare il cammino ecc. ecc. MINIMO e' NP !!!!!!!!!
Il problema che hai indicato e' NP-Completo trattandosi di un problema 
decisionale "Dire se esiste un cammino che passi una e una sola volta su
tutti i nodi", quello di trovare il minimo e' un problema ottimale associato
al problema decisionale presentato, quindi e' NP-hard (e' il problema del 
commesso viaggiatore).
		- Tommaso Schiavinotto -

Non ho capito bene se mi hai dato ragione o torto (ma mi sembra torto).
Vorrei specificare che, almeno nel caso di un grafo interamente connesso,
l'algoritmo per trovare un cammino NON minimo che passi per tutti i nodi 1 e
1 sola volta è:
1 - carica tutti i nodi in una lista (o array o altro) invece che in un
grafo: tempo lineare
2 - prendi il primo nodo e stampalo
3 - passa al nodo successivo e stampalo
4 - se ultimo nodo STOP, altrimenti torna al punto 3
Questo algoritmo è lineare!!! Ovviamente darà in stampa un cammino pessimo,
ma funziona.
Questo è ciò che intendo con cammino QUALSIASI e non minimo.
Il fatto poi che un qualsiasi problema decisionale sia NP-completo è falso,
come appena mostrato sul grafo interamente connesso.
ES: dato un grafo interamente connesso (come di solito è il problema del
commesso viaggiatore tra l'altro) esiste un cammino che passi 1 e 1 sola
volta per ogni nodo? Risposta in tempo costante: SI. Qual'è? risposta in
tempo lineare: quello stampato dall'algoritmo di prima.
Nota: anche il problema decisionale è risolvibile in tempo costante:
Dato un grafo interamente connesso esiste un cammino che passi 1 e 1 sola
volta per ogni nodo e che minimizzi una certa funzione di costo (distanza
totale per esempio)? Risposta: Si, sempre!
Qual'è? Risposta NP-completa: dammi un migliaio di secoli (per n grande ma
non troppo) e te lo stampo!!!
Alessandro Monti
