complessità

cover cercato fra tutte le combinazioni
percorso cercato fra tutte le permutazioni
…

programmi veloci su grafi piccoli
diventano lenti su grafi grandi

esistono modi più rapidi

ordinamento topologico

ordinamento dei nodi
tale che a precede b
se nel grafo c'è l'arco (a,b)

problema di esempio
modo lento e modo veloce di trovarlo

verificare se un ordinamento è topologico

se il grafo contiene un arco (a,b)
allora a deve venire prima di b
sequenza.index(a) < sequenza.index(b)

condizione contraria

se il grafo contiene un arco (a,b)
ma a non viene prima di b
allora l'ordine non e' topologico

sequenza.index(a) > sequenza.index(b) ⇒ ordine non topologico

verificare se un ordine è topologico


# verifica un ordinamento topologico

def verificatopologico(grafo, sequenza):

	for a,b in grafo.insiemearchi():

		if sequenza.index(a) > sequenza.index(b):

			return False

	else:

		return True

se due nodi non sono nella sequenza giusta
l'ordine non è topologico

se non è così per nessun arco
l'ordine è topologico

trovare un ordinamento topologico

sequenza ordinata = permutazione

itertools.permutations(grafo.insiemenodi())

trova tutte le permutazioni di nodi
tutte le sequenze di nodi

prova:


print(*itertools.permutations(grafo1.insiemenodi()), sep = '\n')

verificare tutte le permutazioni


# trova un ordinamento topologico con le permutazioni

def topologicopermutazioni(grafo):

	for o in itertools.permutations(grafo.insiemenodi()):

		if verificatopologico(grafo, o):

			return o

	return None

per ogni permutazione di nodi:
verifica se è un ordine topologico

caso limite

le permutazioni sono:


(1, 2, 3, 4, 5, 6)

(1, 2, 3, 4, 6, 5)

(1, 2, 3, 5, 4, 6)

(1, 2, 3, 5, 6, 4)

(1, 2, 3, 6, 4, 5)

…

(6, 5, 4, 1, 3, 2)

(6, 5, 4, 2, 1, 3)

(6, 5, 4, 2, 3, 1)

(6, 5, 4, 3, 1, 2)

(6, 5, 4, 3, 2, 1)

l'unico ordine topologico è l'ultimo

tempo di esecuzione

numero di permutazioni:

n! = n × (n-1) × (n-2) × … × 2 × 1

solo l'ultima permutazione è un ordine topologico
vanno viste tutte

numero di verifiche simile a un esponenziale
stesso ordine di grandezza


n × (n-1) × (n-2) × … × 2 × 1

n × (n)   × (n)   × … × n × n

grafi piccoli e grafi grandi

grafi di 6, 10 e 20 nodi:

fattoriale di 6: 720
fattoriale di 10: 3628800
fattoriale di 20: 2432902008176640000

un grafo di venti nodi è anche relativamente piccolo
facile che un grafo abbia anche cento o più nodi

numero di operazioni, tradotto in tempo

computer che svolge un milione di operazioni al secondo

grafi di 6, 10 e 20 nodi:

720 operazioni = 0.000720 secondi
3628800 operazioni = 3.6288 secondi
2432902008176640000 operazioni =
2432902008176.64 secondi =
27032244 giorni =
74010 anni

modo più rapido

il primo nodo della sequenza non può avere predecessori

se ha un predecessore
allora il predecessore deve venire prima
e quindi il nodo non può essere il primo

proprietà inversa

un nodo senza predecessori può essere il primo nodo della sequenza

non ha predecessori
mettendolo per primo si rispetta l'ordine

primo nodo della sequenza

il primo nodo della sequenza è un qualsiasi nodo senza precedecessori
se non ci sono, il grafo non ha un ordine topologico

nodi successivi?

primo nodo del grafo di esempio

unico senza predecessori: 1

nodi successivi

il nodo 1 è il primo
il vincolo che deve precedere 6 è rispettato

si può eliminare il nodo 1

secondo nodo

il 6 non ha predecessori
può essere il primo della sequenza
ed è l'unico che può essere il primo

terzo nodo

il nodo 6 è il secondo della sequenza
tutti gli altri vengono dopo
non serve più fare niente per rispettare l'ordine di 6 con gli altri

i nodi senza predecessori sono 2 e 5
ecc.

ordinamento topologico per esclusioni successive

si cerca un nodo senza predecessori
se non c'è il grafo non ha un ordine topologico
si aggiunge il nodo in fondo alla sequenza
si elimina il nodo dal grafo
e gli archi che partono dal nodo
si ripete

nodo senza predecessori

se il grafo contiene un arco (p,n) allora n non va bene
se non ci sono archi (p,n) allora n va bene

nodo senza predecessori

arco (a,b) = b ha un predecessore
non è il primo nodo dell'ordine


	for (a,b) in grafo.insiemearchi():

		if b == c:

			# c ha un predecessore

			break

	else:

		# c non ha predecessori

diverso allineamento degli else:

primo: un singolo arco esclude c
secondo: se non è così per nessuno, allora c può essere il primo

ricerca nodo senza predecessori

serve un nodo c senza predecessori

per ogni nodo del grafo, si verifica se è senza predecessori

se non c'è, non esiste un ordinamento topologico

ricerca nodo senza predecessori


	for c in grafo.insiemenodi():

		for (a,b) in grafo.insiemearchi():

			if b == c:

				# c ha un predecessore

				break

		else:

			# c non ha predecessori

	else:

		# non esiste c senza predecessori

per ogni nodo del grafo, si verifica se è senza predecessori

se non c'è, non esiste un ordinamento topologico

ordinamento topologico


# trova un ordinamento topologico per esclusioni successive

def topologicoesclusioni(grafo):

	risultato = []

	for c in grafo.insiemenodi():

		for (a,b) in grafo.insiemearchi():

			if b == c:

				# 1. c ha un predecessore

				#    non va bene per la prima posizione

				break

		else:

			# 2. c non ha predecessori

			#    va bene per la prima prima posizione

			risultato += [c]

			break

	else:

		# 3. nessun nodo e' privo di predecessori

		#    non esiste ordinamento topologico

		return None

	return risultato

se c ha un predecessore, non è il primo
se c non ha predecessori, va bene come primo
se non esiste un nodo c senza predecessori,
il grafo non ha un ordinamento topologico

nodi successivi


# trova un ordinamento topologico per esclusioni successive

def topologicoesclusioni(grafo):

	risultato = []

	for c in grafo.insiemenodi():

		for (a,b) in grafo.insiemearchi():

			if b == c:

				# 1. c ha un predecessore

				#    non va bene per la prima posizione

				break

		else:

			# 2. c non ha predecessori

			#    va bene per la prima prima posizione

			risultato += [c]

			nodi = grafo.insiemenodi() - {c}

			archi = {(a,b) for (a,b) in grafo.insiemearchi() if a != c and b != c}

			grafo = Grafo(nodi, archi)

			break

	else:

		# 3. nessun nodo e' privo di predecessori

		#    non esiste ordinamento topologico

		return None

	return risultato

se c non ha predecessori:
viene aggiunto all'ordinamento
viene tolto dal grafo

ripetizione

dopo aver tolto il nodo senza predecessori
si ripete

fino a che l'ordine non è completo
deve avere tutti i nodi del grafo

ripetizione


# trova un ordinamento topologico per esclusioni successive

def topologicoesclusioni(grafo):

	risultato = []

	# finche' l'ordinamento non contiene tutti i nodi del grafo...

	lunghezza = len(grafo.insiemenodi())

	while len(risultato) < lunghezza:

		for c in grafo.insiemenodi():

			for (a,b) in grafo.insiemearchi():

				if b == c:

					# 1. c ha un predecessore

					#    non va bene per la prima posizione

					print('no ', c, ': ', (a,b), sep='')

					break

			else:

				# 2. c non ha predecessori

				#    a. va bene per la prima prima posizione

				#    b. va tolto dal grafo

				print('ok', c)

				risultato += [c]

				nodi = grafo.insiemenodi() - {c}

				archi = {(a,b) for (a,b) in grafo.insiemearchi() if a != c and b != c}

				grafo = Grafo(nodi, archi)

				print(grafo)

				break

		else:

			# 3. nessun nodo e' privo di predecessori

			#    non esiste ordinamento topologico

			return None

	return risultato

si ripete dall'inizio
fino a che ci sono ancora nodi nel grafo

solo allora si termina

ricerca per esclusioni successive


# trova un ordinamento topologico per esclusioni successive

def topologicoesclusioni(grafo):

	risultato = []

	# finche' l'ordinamento non contiene tutti i nodi del grafo...

	lunghezza = len(grafo.insiemenodi())

	while len(risultato) < lunghezza:

		for c in grafo.insiemenodi():

			for (a,b) in grafo.insiemearchi():

				if b == c:

					# 1. c ha un predecessore

					#    non va bene per la prima posizione

					print('no ', c, ': ', (a,b), sep='')

					break

			else:

				# 2. c non ha predecessori

				#    a. va bene per la prima prima posizione

				#    b. va tolto dal grafo

				print('ok', c)

				risultato += [c]

				nodi = grafo.insiemenodi() - {c}

				archi = {(a,b) for (a,b) in grafo.insiemearchi() if a != c and b != c}

				grafo = Grafo(nodi, archi)

				print(grafo)

				break

		else:

			# 3. nessun nodo e' privo di predecessori

			#    non esiste ordinamento topologico

			return None

	return risultato

cerca nodo c senza archi (a,b) con b==c
aggiungi c al risultato
elimina c e i suoi archi in uscita
ripeti

operazioni elementari

cerca nodo c senza archi (a,b) con b==c: per ogni nodo e per ogni arco
verifica se b==c
aggiungi c al risultato
elimina c e i suoi archi in uscita: per ogni arco (a,b)
se b==c
elimina arco
ripeti: numero di volte = numero di nodi

numero di volte delle operazioni elementari

N = numero nodi
A = numero archi

cerca nodo c senza archi (a,b) con b==c: per ogni nodo e per ogni arco
verifica se b==c
N × A operazioni
aggiungi c al risultato 1 operazione
elimina c e i suoi archi in uscita: per ogni arco (a,b)
se b==c
elimina arco
A operazioni
ripeti: numero di volte = numero di nodi
tutto quello sopra per N

totale:

N × (N × A + 1 + A)

confronto

grandezza totale grafo: N+A

N × (N × A + 1 + A) ∼ N³

numero di operazioni dei due algoritmi:

grandezza grafo	metodo con permutazioni	metodo con esclusioni
`6`	`720`	`216`
`10`	`3628800`	`1000`
`20`	`2432902008176640000`	`8000`

con sei nodi la differenza non è tanto
720 contro 216

con venti nodi è enorme
2432902008176640000 contro 8000

tempi di esecuzione

1000000 operazioni al secondo

grandezza grafo	metodo con permutazioni	metodo con esclusioni
`6`	`0.000720` secondi	`0.000216` secondi
`10`	`3.6288` secondi	`0.001` secondi
`20`	`74010` anni	`0.008` secondi

miglioramento ulteriore

costo N × (N × A + 1 + A)

parte principale: N × (N × A)

si può ridurre N × A?

ordine topologico con insiemi dei predecessori

si memorizzano i predecessori dei nodi
il primo nodo dell'ordinamento è uno con insieme vuoto
si elimina il nodo da tutti gli insiemi di predecessori
si ripete

ordine topologico con insiemi dei predecessori


# trova un ordinamento topologico per esclusioni successive con insiemi di predecessori

def topologicoinverso(grafo):

	# insiemi di predecessori

	predecessori = {}

	for n in grafo.insiemenodi():

		predecessori[n] = set()

	for (a,b) in grafo.insiemearchi():

		predecessori[b] |= {a}

	print('predecessori:', predecessori)



	# ordine topologico

	risultato = []

	candidati = grafo.insiemenodi()

	while candidati:

		print(risultato)

		for c in candidati:

			if predecessori[c] <= set(risultato):

				risultato += [c]

				candidati -= {c}

				break

		else:

			return None

	return risultato

numero operazioni

nodo senza predecessore:

cercato ogni volta

per ogni nodo c
per ogni arco (a,b)
se b==c, escludi c
costo N × A

con gli insiemi di predecessori

per ogni nodo arco (a,b)
memorizza a come predecessore di b
costo A
nodo senza predecessori
trova nodo c con insieme di predecessori vuoto
costo N
eliminazione nodo dall'indice
per ogni arco (a,b)
se b == c
elimina a dall'insieme dei predecessori di b
costo N

costo N invece di N × A

complessivo: N × N invece di N × N × A

confronto

grandezza grafo	metodo con permutazioni	metodo con esclusioni	metodo con predecessori
6	`720`	`216`	`36`
10	`3628800`	`1000`	`100`
20	`2432902008176640000`	`8000`	`400`

tempi di esecuzione

1000000 operazioni al secondo

grandezza grafo	metodo con permutazioni	metodo con esclusioni	metodo con predecessori
`6`	`0.000720` secondi	`0.000216` secondi	`0.000036` secondi
`10`	`3.6288` secondi	`0.001` secondi	`0.0001` secondi
`20`	`74010` anni	`0.008` secondi	`0.0004` secondi

programma con le tre versioni

topologico.py

cosa si è capito

uno stesso problema può essere risolto in più modi diversi
alcuni possono essere lenti, altri veloci
ma sono comunque modi diversi di risolvere lo stesso problema
ordine topologico ha sia algoritmi lenti che algoritmi veloci

l'ultima cosa vale anche per percorso più breve:
controllare ogni permutazione ha tempo esponenziale
ma gli altri algoritmi sono veloci

copertura minima no
si conoscono solo algoritmi lenti, al momento

come classificare i problemi di questo tipo?

itertools + verifica = NP


def ricerca_insieme_o_sequenza(grafo):

	for s in itertools.permutations/combinations(grafo):

		if verifica_insieme_o_sequenza(grafo, s)

			return s

	return None

diversi metodi usano questo schema:

copertura minima
percorso più breve
ordine topologico

i problemi di questo tipo sono nella classe NP

NP contiene quindi i problemi di trovare
una copertura minima,
un percorso più breve,
un ordine topologico

tempo di soluzione di un problema in NP


def ricerca_insieme_o_sequenza(grafo):

	for s in itertools.permutations/combinations(grafo):

		if verifica_insieme_o_sequenza(grafo, s)

			return s

	return None

la verifica richiede tempo lineare
circa N

numero esponenziale di permutazioni o combinazioni
numero operazioni complessivo dell'ordine di 2^N

a volte si può fare di meglio

la classe P

classe NP = esiste una soluzione con itertools + verifica
numero di operazioni 2^N

se esiste anche un algoritmo con costo lineare, o quadratico, o cubico
il problema è anche nella classe P
soluzione efficente

problemi facili e problemi difficili

classe P: problemi per i quali esiste un algoritmo veloce
percorso più breve
ordine topologico
classe NP: include la classe P
ma anche problemi per i quali non c'è un algoritmo veloce

copertura minima dove si trova?

il problema della copertura minima

trovare la copertura minima:
non esiste attualmente un algoritmo veloce

uno dei problemi più difficili della classe NP
probabilmente un algoritmo veloce non esiste