Ricerca ad albero per trovare percorsi - critiche sugli algoritmi

Question

Ricerca ad albero per trovare percorsi - critiche sugli algoritmi

#1 da (3 voti)

2

Quindi, sono abbastanza nuovo per l'intelligenza artificiale in generale e sto cercando di implementare una ricerca basata su albero da un input di file di testo (un labirinto). Un esempio potrebbe essere:

||||||||||||||||||||||
| ||        | |      |    \
|    |||||| | |||||| |     \
||||||       |    P  |      \
|   .| |||||| || |||||       \  P = Start
| |||| |         |   |       /  . = Goal
|        ||| |||   | |      /
||||||||||    |||||| |     /
|          ||        |    /
||||||||||||||||||||||

Capisco gli algoritmi di base in generale (BFS, DFS, A *, ecc.), ma voglio assicurarmi che li sto implementando correttamente, e non in qualche modo tagliare gli angoli perché "So dove è il percorso migliore" . La mia idea di base è:

Analizza il file in un array 2D
Durante l'analisi, se incontro P , annota l'indice di avvio
Durante l'analisi, se incontro . , annota l'indice Obiettivo
Inizia con Index(Start) e valuta gli spazi [vuoti]
Crea Node s per questi e aggiungi le azioni appropriate alle azioni disponibili del nodo corrente --- Aggiungi questi Node s alla mia frontier que
[continua qualsiasi algoritmo da qui]

Quindi immagino che la mia domanda principale sia: sto generando il mio "mondo" correttamente? È giusto non creare realmente Nodi finché non li incontro durante la ricerca? Sembra uno spreco ottenere uno spazio [vuoto], scansionare le 4 direzioni circostanti per altri spazi [vuoti], e se esistono aggiungili alle azioni disponibili e crea Node s per tutte le azioni possibili.

Un'altra alternativa sarebbe quella di generare nodi quando incontro gli spazi [vuoti], ma sarebbe difficile (dato che non sarei a conoscenza degli spazi vuoti in arrivo) ... dovrei analizzare il file completamente e la traversata l'array memorizzato per creare tutti i possibili nodi / collegamenti / azioni? O è considerato cheating in qualche modo ...

python artificial-intelligence search

posta ctote 16.02.2015 - 08:59

fonte

1 risposta

Leggi altre domande sui tag python artificial-intelligence search

Evitare chiusure Un'applicazione dovrebbe recuperare da un'eccezione generata in PHP?

score 3 · Answer 1

L'istinto di un programmatore orientato agli oggetti su questo tipo di problema è che a un certo punto dovranno istanziare un qualche tipo di oggetto Node , ma in realtà non lo fanno. Non è nemmeno necessario creare un array 2D.

Gli algoritmi di individuazione del percorso sono descritti in gran parte in termini di sets . Puoi scrivere implementazioni molto chiare analizzando il tuo labirinto in sets di (row, col) tuple. Ciò ti consente di scrivere operazioni come le seguenti:

(row, col) = starts.pop()
neighbors = {(row+1,col), (row-1,col), (row,col+1), (row,col-1)}
neighborSpaces = neighbors & spaces
unvisitedNeighborSpaces = neighborSpaces - visited
neighborGoals = neighbors & goals

Qui starts , spaces e goals sono sets che hai creato dall'analisi del file e visited è aggiornato nel corso dell'algoritmo. Nota che le operazioni di set sono generalmente O(n) , dove n è l'operando più piccolo . Ciò significa che neighbors & spaces comporterà solo confronti di 4 , indipendentemente dal numero di spazi nel tuo labirinto. Non è l'implementazione più efficiente possibile, ma è abbastanza efficiente e la chiarezza che ti compra vale la pena.