Definizione e soluzione del problema del commesso viaggiatore (14 pagine formato pdf)
Problema del Commesso viaggiatore visita (tutte) n città C1 , ...,Cn partendo e tornando dalla stessa città passando una sola volta nelle altre Viaggio tra città i e città j costo cij ( distanze e/o i costi di trasporto ) itinerario che minimiza il costo . Applicazioni Programmazione di n lavori (su una stessa macchina ) . cij costi passaggio da lavoro i a lavoro j . Programmazione del lavoro di una macchina automatica (tipo trapano) che deve spostarsi per effettuare ( n buchi su una lastra) Problemi di cristallografia (classificazione) . 2 Non è noto nessun algoritmo che risolva polinomialmente il problema del commesso viaggiatore. [ G grafo non orientato N vertici (citta') costi cij = cji = 1 se esiste l'arco (i,j) cij = cji = 2 se non esiste l'arco (i,j) minimo costo = N esiste circuito Hamiltoniano in G minimo costo > N non esiste circuito Hamiltoniano Problema circuito Hamiltoniano NP-completo Escludere circuito Hamiltoniano problema NP-hard (forse) più difficile di quelli di NP. Il problema del commesso viaggiatore appartiene alla classe NP-hard (problemi difficili almeno come quelli di NP). Continua »
Appunti Correlati a Problema del Commesso Viaggiatore
-
il problema del principio di Talete e Democrito
Il problema del mondo, per gli antichi, e' stato anteriore a quello dell'uomo, prima il naturalismo e poi l'umanesimo, prima la cosmogonia e poi l'antropologia. ( 1 pag - formato word)
Vedi appunto » -
-
Filosofia: Il problema del mito
Il colloquio multidisciplinare - Tema di discussione di Filosofia: IL PROBLEMA DEL MITO (Documento Word, 2 pag.)
TAG:filosofia Vedi appunto » -
il problema del valore: le tesi classiche
Riassunto dettagliato sul problema del valore
Vedi appunto » -
Il problema del lavoro
Componimento in forma di articolo di giornale riguardante le problematiche del mondo del lavoro.(formato word 2 pg)
TAG:lavoro nero, tasso di disoccupazione Vedi appunto » -
Il problema del valore: i primi approcci
Il valore prima di una teoria del valore
Vedi appunto » -
Il problema del valore: la tesi neoclassica
Il rigetto della teoria classica del valore-lavoro; i prezzi dei fattori produttivi; un confronto tra due teorie del valore; osservazioni conclusive
Vedi appunto » -
-
Il problema del federalismo nel pensiero politico di I. Kant
Tesi di R.Gambino. Facolta’ di Lettere e Filosofia.
Vedi appunto »