commessoviaggiatore, problemadelcommessoviaggiatore, problemadel (in inglese Travelling Salesman Problem, o più brevemente tsp) problema che consiste nella ricerca su un grafo di un particolare [...] sono indicati i rispettivi pesi:
Un possibile ciclo hamiltoniano di lunghezza 7 è A, C, B, D, A:
È una soluzione delproblema perché la somma minima dei pesi è 7, come si evince dal corrispondente albero che descrive tutti i possibili percorsi di ...
Leggi Tutto
Nel linguaggio scientifico, struttura relazionale formata da un insieme finito di oggetti detti nodi o vertici, e da un insieme di relazioni tra coppie di oggetti dette archi o spigoli. Per indicare un [...] di sequenziamento e, con G. Dantzig e D.R. Fulkerson, riprese il problemadel ciclo hamiltoniano ottimo, detto problemadelcommessoviaggiatore; nel 1955 H.W. Kuhn studiò i sistemi di disequazioni lineari; nel 1956 L.R. Ford e D.R. Fulkerson ...
Leggi Tutto
Informatica
Giorgio Ausiello
Carlo Batini
Vittorio Frosini
(App. IV, ii, p. 189; V, ii, p. 704)
Mentre negli anni 1937-38 venivano pubblicati l'ultimo volume della Enciclopedia Italiana e l'App. I, [...] i filamenti anche rispetto al peso. Per realizzare la soluzione di un problema (per es., il problemadelcommessoviaggiatore) si deve innanzitutto codificare l'istanza delproblema con filamenti, poi si eseguono operazioni che trasformano via via i ...
Leggi Tutto
PROGRAMMAZIONE LINEARE
Amato HERZEL
Claudio NAPOLEONI
. 1. - Generalità e posizione delproblema. - Sotto l'aspetto matematico, il termine p. l. indica una classe di problemi consistenti nella ricerca [...] ideati alcuni algoritmi particolari che sono più semplici del metodo del simplesso.
Connesso al "problema dei trasporti", ma molto più difficile a maneggiarsi, è il cosiddetto "problemadelcommessoviaggiatore" che negli ultimi tempi è stato fatto ...
Leggi Tutto
Storia dei concetti e delle tecniche nella ricerca sulle reti neurali
Jack D. Cowan
(Department of Mathematics, University of Chicago Chicago, Illinois, USA)
In questo saggio descriveremo diverse ricerche [...] Le reti di Hopfield si sono rivelate utili nella risoluzione di problemi computazionali di ottimizzazione. Un esempio ben noto è il problemadelcommessoviaggiatore, in cui un commessoviaggiatore deve visitare una sola volta ogni città di un certo ...
Leggi Tutto
Computer science
Scott Kirkpatrick
La computer science si colloca con caratteristiche peculiari tra le scienze cosiddette esatte e l’ingegneria, costituendo dal punto di vista accademico un settore [...] richieste per la verifica della risposta cresce almeno esponenzialmente con n.
Un esempio tipico è il problemadelcommessoviaggiatore, in cui un commesso nel tempo più breve possibile deve visitare n città, per poi ritornare al punto di partenza ...
Leggi Tutto
La grande scienza. Computer science
Scott Kirkpatrick
Computer science
La computer science si colloca con caratteristiche peculiari tra le scienze cosiddette esatte e dell'ingegneria, costituendo dal [...] richieste per la verifica della risposta cresce almeno esponenzialmente con n.
Un esempio tipico è il 'problemadelcommessoviaggiatore', in cui un commesso nel tempo più breve possibile deve visitare n città, per poi ritornare al punto di partenza ...
Leggi Tutto
Visione artificiale
Pietro Parodi
(Scuola Internazionale di Studi Superiori Avanzati, Trieste, Italia)
Vincent Torre
(Scuola Internazionale di Studi Superiori Avanzati, Trieste, Italia)
La visione artificiale, [...] soluzione, è possibile stabilire con complessità polinomiale se questa è effettivamente una soluzione delproblema. Per esempio, il problemadelcommessoviaggiatore appartiene alla classe NP perché è possibile verificare con una semplice somma (che ...
Leggi Tutto
Sierpinski, curva di
Sierpiński, curva di denominazione di alcune curve frattali piane, continue, definite per ricorrenza, che, al tendere all’infinito del numero dei passi, riempiono il quadrato unitario. [...] racchiudendo una superficie di area finita, non ha lunghezza finita. La curva di Sierpiński trova applicazione nel problemadel → commessoviaggiatore, consistente nell’individuare il percorso più breve che passa per tutti i punti di un dato insieme ...
Leggi Tutto
ciclo hamiltoniano
ciclo hamiltoniano in un grafo orientato G = (X, A), cammino hamiltoniano chiuso: contiene tutti i nodi una sola volta ed esiste un arco che collega l’ultimo nodo al primo. In un grafo [...] non sempre esiste un ciclo hamiltoniano. Un particolare ciclo hamiltoniano è ricercato nel cosiddetto problemadel → commessoviaggiatore. ...
Leggi Tutto
plant sitter (plant-sitter) loc. s.le m. e f. Chi si occupa professionalmente di accudire le piante per conto di persone assenti da casa per un periodo di tempo, di solito per le vacanze. ♦ [tit.] Plant sitter, quando scatta l’SOS piante [sommario]...