News

Come funziona l’algoritmo A*

Trovalost.it

L’algoritmo A* è una tecnica di ricerca di percorso che combina il concetto della ricerca in ampiezza (BFS) con l’euristica per trovare il percorso più breve tra due nodi in un grafo. Si basa sull’espansione dei nodi in base a due valori: il costo effettivo per raggiungere il nodo corrente e una stima del costo rimanente per raggiungere la destinazione desiderata.

Ecco come funziona:

Premesse:

  • Grafo: Si parte da un grafo con nodi e archi.
  • Nodo di partenza e nodo di destinazione: Indicano i nodi tra cui cercare il percorso.
  • Euristica: Una funzione che stima il costo rimanente dal nodo attuale alla destinazione.

Passo 1: Inizializzazione

  • Insieme dei nodi visitati: Inizialmente vuoto.
  • Coda di priorità: Si utilizza una coda che ordina i nodi in base a una combinazione di costo effettivo e stima del costo rimanente.

Passo 2: Espansione dei nodi

  • Scegli il nodo con il costo minore complessivo: Utilizza la coda di priorità per estrarre il nodo con il costo minore, che è la somma del costo effettivo per raggiungere il nodo e dell’euristica verso la destinazione.
  • Verifica se il nodo estratto è la destinazione: Se il nodo estratto è la destinazione, si è trovato il percorso più breve e si può terminare l’algoritmo.
  • Altrimenti, espandi il nodo estratto: Esamina tutti i nodi adiacenti al nodo estratto e calcola il costo effettivo per raggiungerli. Aggiungi questi nodi alla coda di priorità.

Passo 3: Aggiornamento dei costi

  • Aggiorna i costi se necessario: Se il costo effettivo per raggiungere un nodo adiacente è inferiore al costo precedente, aggiorna il costo e il percorso associato a quel nodo.

Passo 4: Ripeti finché non si raggiunge la destinazione o la coda è vuota

  • Continua il processo: Continua a estrarre il nodo con il costo minore finché non si raggiunge la destinazione o finché la coda di priorità non è vuota.

Passo 5: Ottieni il percorso più breve

  • Recupera il percorso più breve: Una volta raggiunta la destinazione, è possibile recuperare il percorso più breve seguendo i nodi precedenti memorizzati durante l’esecuzione dell’algoritmo.

Conclusione

  • Alla fine dell’algoritmo, si ottiene il percorso più breve tra il nodo di partenza e il nodo di destinazione, utilizzando l’euristica e l’informazione dei costi per guidare l’esplorazione del grafo.

Spiegazione in termini di “altezza” dei nodi

Introdurre un concetto di “altezza” dei nodi in A* potrebbe essere simile all’uso di un’altra euristica. L’idea è di assegnare un valore di altezza a ciascun nodo, che rappresenta una sorta di informazione aggiuntiva sulla desiderabilità o sulla probabilità di quel nodo di condurre verso la destinazione. In termini più semplici, i nodi “più alti” potrebbero essere preferiti nel percorso rispetto a quelli “più bassi”.

Per illustrare questo concetto, possiamo introdurre una funzione di altezza che assegna valori di altezza ai nodi in base alla loro posizione o ad altre caratteristiche del grafo. Ad esempio, in un terreno montagnoso, i nodi più alti potrebbero rappresentare aree più difficili da attraversare, mentre quelli più bassi potrebbero essere terreni più agevoli. Quindi, un’altezza maggiore potrebbe corrispondere a una penalità nell’algoritmo.

Implementazione in Python

In Python, l’algoritmo A* può essere implementato utilizzando una coda di priorità per gestire l’espansione dei nodi in base al costo complessivo (costo effettivo più l’euristica).

In questo esempio:

  • graph rappresenta il grafo con i nodi e i relativi pesi sugli archi.
  • La funzione heuristic calcola l’euristica tra due nodi (può essere personalizzata a seconda del problema).
  • La funzione astar esegue l’algoritmo A* per trovare il percorso più breve dal nodo di partenza al nodo di destinazione nel grafo fornito.
  • Restituisce il percorso più breve come lista dei nodi attraverso cui passa il percorso ottimale, o None se non è stato trovato alcun percorso.

Ovvero:

import heapq
def heuristic(node, goal):
# Euristicamente valuta la distanza tra il nodo corrente e il nodo di destinazione
# In questo esempio, si calcola la distanza euclidea (si può personalizzare)
x1, y1 = node
x2, y2 = goal
return ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5
def astar(graph, start, goal):
# Coda di priorità per mantenere traccia dei nodi da esplorare
priority_queue = [(0, start)]
# Dizionario per memorizzare i costi effettivi per raggiungere i nodi
costs = {start: 0}
# Dizionario per memorizzare i nodi precedenti nel percorso più breve
previous = {}
while priority_queue:
current_cost, current_node = heapq.heappop(priority_queue)
if current_node == goal:
# Recupera il percorso più breve una volta raggiunta la destinazione
path = []
while current_node in previous:
path.append(current_node)
current_node = previous[current_node]
path.append(start)
return path[::-1] # Ritorna il percorso in ordine corretto
for neighbor in graph[current_node]:
# Calcola il costo effettivo per raggiungere il vicino
cost = costs[current_node] + graph[current_node][neighbor]
if neighbor not in costs or cost < costs[neighbor]:
# Aggiorna i costi e il nodo precedente se il costo è minore
costs[neighbor] = cost
priority = cost + heuristic(neighbor, goal)
heapq.heappush(priority_queue, (priority, neighbor))
previous[neighbor] = current_node
return None # Se non viene trovato alcun percorso
# Esempio di utilizzo
graph = {
'A': {'B': 5, 'C': 10},
'B': {'D': 7},
'C': {'D': 3},
'D': {}
}
start_node = 'A'
goal_node = 'D'
path = astar(graph, start_node, goal_node)
if path:
print("Il percorso più breve da", start_node, "a", goal_node, ":", path)
else:
print("Nessun percorso trovato da", start_node, "a", goal_node)

Nel successivo esempio, la funzione height assegna un valore di altezza arbitrario a ciascun nodo. Questo valore di altezza viene considerato nel calcolo del costo effettivo per raggiungere i nodi, influenzando la scelta dei percorsi durante l’esecuzione dell’algoritmo A*. È importante notare che la funzione di altezza può essere personalizzata in base alle specifiche del problema.

import heapq
def heuristic(node, goal):
# Euristica basata sulla distanza euclidea tra i nodi
x1, y1 = node
x2, y2 = goal
return ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5
def height(node):
# Funzione di altezza per assegnare un valore di altezza a ciascun nodo (esempio semplice)
# In questo caso, l'altezza è un valore arbitrario associato al nodo
height_values = {
'A': 5,
'B': 2,
'C': 8,
'D': 3
# ... altri nodi e relativi valori di altezza
}
return height_values.get(node, 0) # Ritorna l'altezza associata al nodo, se presente
def astar_with_height(graph, start, goal):
priority_queue = [(0, start)]
costs = {start: 0}
previous = {}
while priority_queue:
current_cost, current_node = heapq.heappop(priority_queue)
if current_node == goal:
path = []
while current_node in previous:
path.append(current_node)
current_node = previous[current_node]
path.append(start)
return path[::-1]
for neighbor in graph[current_node]:
# Calcolo del costo effettivo per raggiungere il vicino, considerando anche l'altezza
cost = costs[current_node] + graph[current_node][neighbor] + height(neighbor)
if neighbor not in costs or cost < costs[neighbor]:
costs[neighbor] = cost
priority = cost + heuristic(neighbor, goal)
heapq.heappush(priority_queue, (priority, neighbor))
previous[neighbor] = current_node
return None
# Utilizzo dell'algoritmo A* con altezza dei nodi
graph = {
'A': {'B': 5, 'C': 10},
'B': {'D': 7},
'C': {'D': 3},
'D': {}
}
start_node = 'A'
goal_node = 'D'
path = astar_with_height(graph, start_node, goal_node)
if path:
print("Il percorso più breve da", start_node, "a", goal_node, ":", path)
else:
print("Nessun percorso trovato da", start_node, "a", goal_node)

👇 Contenuti da non perdere 👇

Questo sito esiste da 4827 giorni (13 anni), e contiene 5883 articoli (circa 4.706.400 parole in tutto), con la bellezza di 32 tool gratuiti.