Implementazione algoritmo A *

Question

Quindi sto implementando l'algoritmo A * in C. Ecco la procedura.

Sto usando la coda prioritaria [usando la matrice] per tutti i nodi aperti. Dato che avrò distanze duplicate, cioè più di un nodo con la stessa distanza/priorità, quindi mentre si inserisce un nodo in PQ, se il genitore del nodo inserito ha la stessa priorità, lo scambio ancora entrambi, in modo che il mio più recente il membro inserito rimane in alto (o il più alto possibile), in modo da continuare a seguire una particolare direzione. Inoltre, durante la rimozione, quando scambio l'elemento più in alto con l'ultimo, poi di nuovo, se l'ultimo elemento scambiato ha lo stesso di uno dei suoi figli, allora viene scambiato verso il basso. (Non sono sicuro che questo influenzerà in ogni modo).

Ora il problema è dire che ho una matrice 100 * 100 e ho ostacoli da (0,20) a (15,20) dell'array 2D, in cui mi sto muovendo. Ora per una posizione di partenza (2,2) e una posizione di fine (16,20) ottengo un percorso rettilineo, cioè, prima di tutto andiamo a destra, poi scendo fino a 15 poi muovo di una destra e ho finito.

Ma, se ho iniziato come (2,2) e ultimo come (12,78) cioè i punti sono separati dagli ostacoli e il percorso deve aggirarlo, continuo a passare (16,20) e il mio percorso dopo (16,20) è ancora dritto, ma il mio percorso fino a (16,20) è a zig zag, cioè vado un po 'in basso, poi a destra, poi a destra e così via, raggiungendo infine (16 , 20) e andando subito dopo.

Perché questo percorso a zig zag per la prima metà della distanza, cosa posso fare per assicurarmi che il mio percorso sia dritto, così com'è, quando la mia destinazione è (16,20) e non (12,78) .

Grazie.

void findPath(array[ROW][COLUMN],sourceX,sourceY,destX,destY) { 
    PQ pq[SIZE]; 
    int x,y; 

    insert(pq,sourceX,sourceY); 

    while(!empty(pq)) { 
    remove(pq); 
    if(removedIsDestination) 
     break;     //Path Found 
    insertAdjacent(pq,x,y,destX,destY); 
    } 
} 

void insert(PQ pq[SIZE],element){ 
    ++sizeOfPQ; 
    PQ[sizeOfPQ]==element 
    int i=sizeOfPQ; 
    while(i>0){ 
    if(pq[i].priority <= pq[(i-1)/2].priority){ 
     swapWithParent 
     i=(i-1)/2; 
    } 
    else 
     break; 
    } 
} 

Answer 1

È necessario modificare la parte di calcolo del punteggio. In questo momento calcoli la distanza assoluta. Calcola invece la distanza minima di movimento. Se si contano ogni mossa come uno poi se foste a (x, y) e andando a (dx, dy) che sarebbe

distance moved + (max(x,dX) - min(x,dx) + max(y,dY) - min(y,dY)) 

Un valore basso è considerato un punteggio più alto.

Questa euristica è un'ipotesi su quanti movimenti ci vorrebbe se non ci fosse nulla nel modo.

---

La cosa bella circa l'euristica è che si può cambiare per ottenere i risultati desiderati, per esempio se si preferisce muoversi in linea retta come lei suggerisce, allora si può fare questo cambiamento:

= distance moved + (max(x,dX) - min(x,dx) + max(y,dY) - min(y,dY)) 
    + (1 if this is a turn from the last move) 

Ciò consentirà di "trovare" soluzioni che tendono ad andare nella stessa direzione.

Se si vuole forzare il minor numero di giri possibile:

= distance moved + (max(x,dX) - min(x,dx) + max(y,dY) - min(y,dY)) 
    + (1 times the number of turns made) 

Questo è ciò che è bello su A * - l'euristica informerà la ricerca - si continua a trovare sempre una soluzione, ma se ce n'è più di una che puoi influenzare dove guardi prima - questo è utile per simulare il comportamento di IA.

---

dubbio: come è la prima e la seconda calcolando modo diverso da uno dall'altro?

Il primo mette una priorità più bassa su una mossa che è una svolta. Il secondo pone una priorità più bassa su un percorso con più turni. In alcuni casi (ad esempio, il primo turno) il valore sarà lo stesso, ma su tutto il 2 ° selezionerà i percorsi che hanno il minor numero di giri possibile, dove il primo potrebbe non esserlo.

Inoltre, 1 se si tratta di una svolta dalla ultima mossa, per questo, dire che sono fonte in alto a sinistra e la destinazione in basso a destra, ora il mio percorso normalmente sarebbe, sinistra, sinistra, sinistra. ..down, down, down .... Ora, 1 se questo è un turno dall'ultima mossa, secondo questo, quando cambio da sinistra a giù, aggiungerò 1?

Sì

Wont lo rendono il valore totale di più e la priorità per giù diminuirà.

Sì, esattamente. Non vuoi guardare le scelte che hanno una svolta in loro prima. Questo renderà loro una priorità più bassa e il tuo algoritmo studierà altre opzioni con una priorità più alta - esattamente ciò che desideri.

Oppure 1 se questo è un turno dall'ultima mossa è quando mi sposto in una cella, che non è in aggetto sulla cella precedentemente lavorata? Thnks -

No, non capisco questa domanda - Non penso che abbia senso in questo contesto - tutte le mosse devono superare la cella precedente, non sono consentiti spostamenti diagonali.

---

però, mi piacerebbe davvero grato se mi potesse dire un caso in cui il primo e secondo metodi daranno risposte diverse. Se potessi. Molte grazie. :)

Non è così facile senza vedere i dettagli del vostro algoritmo, ma il seguente potrebbe funzionare:

Il rosso sono blocchi. Il green è quello che mi aspetterei che il primo faccia, che localmente cerchi di trovare la svolta minima. Il blu è la soluzione meno svolta. Nota, quanto sono distanti le aree rosse e i dettagli di come il tuo algoritmo influenza se questo funzionerà. Come ho sopra: avere un turno extra costa solo 1 in euristica. Quindi, se si vuole essere sicuri che questo funzionerà cambiare l'euristica in questo modo:

= distance moved + (max(x,dX) - min(x,dx) + max(y,dY) - min(y,dY)) 
    + (25 times the number of turns made) 

Dove 25 è più grande la distanza per superare il 2 ° turno nel percorso verde. (Quindi, dopo il 2 ° giro, verrà cercato il percorso blu.)