Esercizio - Materiale supplementare di ricerca in Python - multimap, zip, slicing e Counter (laboratorio 3)

Il materiale supplementare del laboratorio 3 (corso di Intelligenza Artificiale, Ing. dell'Informazione UniPD) è una raccolta di piccoli esperimenti sugli strumenti di Python che servono nelle classi Map, RouteProblem, PancakeProblem e CountCalls: i blocchi di codice si eseguono uno alla volta e si guarda l'output. Qui sono ripresi nell'ordine, con la spiegazione di che cosa fanno e perché servono. Il contesto è in Esercizio - Route finding sulla Romania e pancake sorting con euristica del gap (laboratorio 3) e Esercizio - Confronto degli algoritmi di ricerca con CountCalls, report e grafici (laboratorio 3). Tutti gli output sono stati riprodotti.

1. defaultdict e multimap: i vicini di ogni città

Obiettivo. Dato l'insieme dei collegamenti {(v1, v2): distanza}, costruire il dizionario dei vicini vertice -> [vicini].

Un dizionario normale darebbe KeyError alla prima chiave nuova: bisognerebbe controllare if key not in d a ogni inserimento. Un defaultdict(list) crea da solo una lista vuota alla prima lettura di una chiave mancante:

from collections import defaultdict

result = defaultdict(list)
print(result)        # defaultdict(<class 'list'>, {})

def multimap(pairs) -> dict:
    "Date coppie (chiave, valore), costruisce {chiave: [valore, ...]}."
    result = defaultdict(list)
    for key, val in pairs:
        result[key].append(val)
    return result

Applicata ai collegamenti della mappa della Romania (le chiavi del dizionario links sono coppie, e iterare su un dizionario dà le chiavi, cioè le coppie (v1, v2)):

links = {('O', 'Z'): 71, ('O', 'S'): 151, ('A', 'Z'): 75, ('A', 'S'): 140, ('A', 'T'): 118,
         ('L', 'T'): 111, ('L', 'M'): 70, ('D', 'M'): 75, ('C', 'D'): 120, ('C', 'R'): 146,
         ('C', 'P'): 138, ('R', 'S'): 80, ('F', 'S'): 99, ('B', 'F'): 211, ('B', 'P'): 101,
         ('B', 'G'): 90, ('B', 'U'): 85, ('H', 'U'): 98, ('E', 'H'): 86, ('U', 'V'): 142,
         ('I', 'V'): 92, ('I', 'N'): 87, ('P', 'R'): 97}
multimap(links)

defaultdict(list,
            {'O': ['Z', 'S'], 'A': ['Z', 'S', 'T'], 'L': ['T', 'M'], 'D': ['M'],
             'C': ['D', 'R', 'P'], 'R': ['S'], 'F': ['S'], 'B': ['F', 'P', 'G', 'U'],
             'H': ['U'], 'E': ['H'], 'U': ['V'], 'I': ['V', 'N'], 'P': ['R']})

Si vede che qui compare solo un verso di ogni strada: Zerind ('Z') non è una chiave, perché nessun collegamento comincia con 'Z'. La classe Map aggiunge i versi opposti (directed=False) prima di chiamare multimap, così dopo la mappa ogni vicino compare in entrambi i versi. L'ordine dei vicini è quello di inserimento nel dizionario ed è lo stesso con cui gli algoritmi li espandono.

2. zip e la distanza in linea retta

Obiettivo. Capire come straight_line_distance calcola la distanza tra due punti con una sola riga.

zip accoppia gli elementi nella stessa posizione di più sequenze e si ferma alla più corta:

a = ("John", "Charles", "Mike")
b = ("Jenny", "Christy", "Monica", "Vicky")
for e in zip(a, b):
    print(e)

('John', 'Jenny')
('Charles', 'Christy')
('Mike', 'Monica')

'Vicky' non compare, perché a ha solo tre elementi. Con due punti A = (x1, y1) e B = (x2, y2), zip(A, B) dà le coppie delle coordinate omologhe (x1, x2), (y1, y2), e la distanza euclidea è la radice della somma dei quadrati delle differenze:

A = [1, 2, 3, 4]
B = [5, 6, 7, 8]
print(sum(abs(a - b)**2 for (a, b) in zip(A, B)) ** 0.5)     # 8.0

s = (1-5)**2 + (2-6)**2 + (3-7)**2 + (4-8)**2
print(s)           # 64
print(s ** 0.5)    # 8.0

La somma dei quadrati è $4 \cdot 16 = 64$ e la distanza è $\sqrt{64} = 8$ (il corso stampa $64$, cioè la somma dei quadrati: il passo finale è la radice). Funziona per punti con qualsiasi numero di dimensioni (qui quattro), e ** 0.5 è la radice. Nella mappa le coordinate hanno due dimensioni.

3. Pancake: sorted, range e fette

Obiettivo. Capire le operazioni su tuple che compaiono in PancakeProblem.

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

sorted(pancake_stack)             # [1, 2, 3, 4, 5, 6]: l'obiettivo è la pila ordinata

sorted restituisce una lista nuova (la tupla è immutabile); nel problema l'obiettivo si costruisce con tuple(sorted(initial)), che dà una tupla.

x = range(2, len(pancake_stack) + 1)
print(x)                          # range(2, 7)
print(list(x))                    # [2, 3, 4, 5, 6]

Le azioni sono gli indici $i$ delle frittelle da capovolgere, da 2 a $n$: range(2, n + 1) perché l'estremo superiore è escluso, e il valore 1 non cambierebbe niente. Per capovolgere le prime $i$ frittelle:

i = 3
print(pancake_stack[:i])           # (2, 1, 4)      le prime i
print(pancake_stack[:i][::-1])     # (4, 1, 2)      rovesciate
print(pancake_stack[i:])           # (6, 3, 5)      il resto, invariato
print(pancake_stack[:i][::-1] + pancake_stack[i:])   # (4, 1, 2, 6, 3, 5)

t[:i] è la fetta dall'inizio all'indice $i$ escluso; [::-1] rovescia (passo $-1$); + concatena le tuple. Questa è proprio result(state, i) del problema.

4. L'euristica del gap in una riga

print(sum(abs(pancake_stack[i] - pancake_stack[i - 1]) > 1 for i in range(1, len(pancake_stack))))   # 4

Il generatore produce un booleano per ogni coppia di frittelle vicine (per $i = 1, \dots, 5$ confronta pancake_stack[i] con quella prima): abs(...) > 1 è True se le taglie differiscono per più di 1. Per (2, 1, 4, 6, 3, 5) i cinque booleani sono [False, True, True, True, True], e sum li somma come $0 + 1 + 1 + 1 + 1 = 4$ (True vale 1). La versione estesa del corso è un ciclo con un contatore count incrementato quando diff > 1: dà ancora 4.

5. Counter: contare le chiamate

Counter è un dizionario specializzato nel conteggio: una chiave mancante vale 0 (non solleva KeyError), e update aggiunge i conteggi di un iterabile (o di un altro dizionario) invece di sostituirli:

from collections import Counter

coun = Counter()
print(coun)                                # Counter()

coun.update([1, 2, 3, 1, 2, 1, 1, 2])
print(coun)                                # Counter({1: 4, 2: 3, 3: 1})

coun.update([1, 2, 2, 4])
print(coun)                                # Counter({1: 5, 2: 5, 3: 1, 4: 1})

Prima chiamata: l'elemento 1 compare 4 volte, il 2 tre volte e il 3 una volta. Seconda chiamata: i conteggi si sommano ($1$: $4 + 1 = 5$; $2$: $3 + 2 = 5$; $3$: invariato; $4$: nuovo con 1). Altre due utilità: coun['zz'] vale 0 senza creare la chiave, e coun.most_common(2) dà [(1, 5), (2, 5)]. Nel laboratorio Counter conta quante volte l'algoritmo chiama result, is_goal, action_cost e così via (Esercizio - Confronto degli algoritmi di ricerca con CountCalls, report e grafici (laboratorio 3)); counts.update(actions=len(soln), cost=soln.path_cost) aggiunge due conteggi con argomenti con nome.