Attenzione
Questa pagina rimane qui per ragioni storiche e può contenere informazioni obsolete o errate.
Note di modifica: 2/22/98, 3/2/98, 12/4/00: Questa versione di questo saggio corregge diversi bug nel codice. 6/10/19: Ritiro difind_shortest_pathcome “quasi ottimale”. 8/11/19: Corretto l’uso accidentale difind_graph()invece difind_path()
Copyright (c) 1998, 2000, 2003, 2019 Python Software Foundation.All rights reserved.Licensed under the PSF license.
I grafi sono reti composte da nodi collegati da spigoli o archi. Nei grafi indiretti, le connessioni tra i nodi hanno una direzione e sono chiamate archi; nei grafi indiretti, le connessioni non hanno direzione e sono chiamate bordi. Discutiamo principalmente i grafi diretti. Gli algoritmi nei grafi includono trovare un percorso tra due nodi, trovare il percorso più breve tra due nodi, determinare i cicli nel grafico (un ciclo è un percorso non vuoto da un nodo a se stesso), trovare un percorso che raggiunge tutti i nodi (il famoso “traveling salesman problem”), e così via. A volte i nodi o gli archi di un grafo hanno pesi o costi associati ad essi, e noi siamo interessati a trovare il percorso più economico.
C’è una notevole letteratura sugli algoritmi dei grafi, che sono una parte importante della matematica discreta. I grafi hanno anche molto uso pratico negli algoritmi informatici. Esempi ovvi possono essere trovati nella gestione delle reti, ma gli esempi abbondano in molte altre aree. Per esempio, le relazioni chiamante-calleato in un programma per computer possono essere viste come un grafico (dove i cicli indicano la ricorsione, e i nodi irraggiungibili rappresentano il codice morto).
Pochi linguaggi di programmazione forniscono un supporto diretto per i grafi come tipo di dati, e Python non fa eccezione. Tuttavia, i grafi sono facilmente costruiti a partire da liste e dizionari. Per esempio, ecco un semplice grafico (non posso usare disegni in queste colonne, quindi scrivo gli archi del grafico):
A -> B A -> C B -> C B -> D C -> D D -> C E -> F F -> C
Questo grafico ha sei nodi (A-F) e otto archi. Può essere rappresentato dalla seguente struttura di dati Python:
graph = {'A': , 'B': , 'C': , 'D': , 'E': , 'F': }
Questo è un dizionario le cui chiavi sono i nodi del grafico. Per ogni chiave, il valore corrispondente è una lista contenente i nodi che sono collegati da un arco diretto da questo nodo. Questo è il massimo della semplicità (ancora più semplice, i nodi potrebbero essere rappresentati da numeri invece che da nomi, ma i nomi sono più convenienti e possono essere facilmente resi per portare più informazioni, come i nomi delle città).
Scriviamo una semplice funzione per determinare un percorso tra due nodi. Prende un grafico e i nodi iniziali e finali come argomenti. Restituisce una lista di nodi (inclusi i nodi iniziali e finali) che compongono il percorso; se non si trova alcun percorso, restituisce None. Lo stesso nodo non apparirà più di una volta nel percorso restituito (cioè non conterrà cicli). L’algoritmo usa un’importante tecnica chiamata backtracking: prova ogni possibilità a turno finché non trova una soluzione.
def find_path(graph, start, end, path=): path = path + if start == end: return path if not graph.has_key(start): return None for node in graph: if node not in path: newpath = find_path(graph, node, end, path) if newpath: return newpath return None
Un esempio di esecuzione (usando il grafico sopra):
>>> find_path(graph, 'A', 'D') >>>
La seconda dichiarazione ‘if’ è necessaria solo nel caso in cui ci siano nodi che sono elencati come punti finali per archi ma che non hanno archi uscenti, e non sono elencati affatto nel grafico. Tali nodi potrebbero anche essere contenuti nel grafico, con una lista vuota di archi in uscita, ma a volte è più conveniente non richiederlo.
Nota che mentre l’utente chiama find_path() con tre argomenti, esso chiama se stesso con un quarto argomento: il percorso che è già stato percorso. Questo argomento è usato per evitare cicli (il primo ‘if’ all’interno del ciclo ‘for’). L’argomento ‘path’ non viene modificato: l’assegnazione “path = path + ” crea una nuova lista. Se avessimo scritto “path.append(start)” invece, avremmo modificato la variabile’path’ nel chiamante, con risultati disastrosi. (Usando le tuple, avremmo potuto essere sicuri che questo non sarebbe successo, al costo di dover scrivere “path = path + (start,)” poiché “(start)” non è una tupla singleton — è solo un’espressione tra parentesi.)
È semplice cambiare questa funzione per restituire una lista di tutti i percorsi (senza cicli) invece del primo percorso che trova:
def find_all_paths(graph, start, end, path=): path = path + if start == end: return if not graph.has_key(start): return paths = for node in graph: if node not in path: newpaths = find_all_paths(graph, node, end, path) for newpath in newpaths: paths.append(newpath) return paths
Un’esecuzione di esempio:
>>> find_all_paths(graph, 'A', 'D') , , ] >>>
Un’altra variante trova il percorso più breve:
def find_shortest_path(graph, start, end, path=): path = path + if start == end: return path if not graph.has_key(start): return None shortest = None for node in graph: if node not in path: newpath = find_shortest_path(graph, node, end, path) if newpath: if not shortest or len(newpath) < len(shortest): shortest = newpath return shortest
Esecuzione di esempio:
>>> find_shortest_path(graph, 'A', 'D') >>>
Queste funzioni sono semplici quanto lo sono. Eppure, sono quasi ottimali (per il codice scritto in Python). In un’altra colonna di Python Patterns, cercherò di analizzare la loro velocità di esecuzione e migliorare le loro prestazioni, al costo di più codice.
AGGIORNAMENTO: Eryk Kopczyński ha sottolineato che queste funzioni non sono ottimali. Al contrario, “questo programma gira in tempo esponenziale, mentre find_shortest_path può essere fatto in tempo lineare usando BFS. Inoltre un BFS lineare è più semplice:”
# Code by Eryk Kopczyński def find_shortest_path(graph, start, end): dist = {start: } q = deque(start) while len(q): at = q.popleft() for next in graph: if next not in dist: dist = , next] q.append(next) return dist.get(end)
Nota che questo restituisce il percorso in un formato strano, ad esempio,, 'B'], 'D']. In particolare,len(find_shortest_path(graph, 'A', 'D'))darà la risposta sbagliata (2, perché la lista esterna è di lunghezza 2). Questo perché append è fatto come, next]invece didist+. Il secondo metodo userebbe tempo e memoria quadratici, ma dovrebbe comunque andare bene per grafi relativamente piccoli; altrimenti, è facile trasformare la lista nel formato corretto.
Un’altra variazione sarebbe quella di aggiungere più astrazione dei dati: creare una classe per rappresentare i grafi, i cui metodi implementano i vari algoritmi. Anche se questo fa appello al desiderio di programmazione strutturata, non rende il codice più efficiente (al contrario). Rende più facile aggiungere varie etichette ai nodi o agli archi e aggiungere algoritmi che tengano conto di queste etichette (ad esempio per trovare il percorso più breve tra due città su una mappa). Anche questo sarà oggetto di un’altra rubrica.