Efficiente algoritmo di individuazione dei percorsi che evita gli zigzag

Question

Sto sviluppando un software che collega oggetti con fili. Questo cablaggio ha una regola che questi fili non possono passare su altri oggetti e nessuna mossa diagonale è accettata.

Tutte le più brevi algoritmi di percorso, che io sappia (A *, Dijkstra ecc) trovare questo tipo di percorsi:

Non voglio gli zigzag inutili nel secondo screenshot. Come posso raggiungere questo obiettivo?

Nota: chiunque desideri provare gli algoritmi può utilizzare l'applicazione this.

Un'altra nota: questa è la situazione esatta che non desidero. Trova il percorso a zigzag invece di quello "vai a destra finché non raggiungi la posizione x del bersaglio, vai su fino a raggiungere la posizione y del bersaglio" che ha lo stesso costo con quello a zigzag.

Answer 1

L'algoritmo corrente trova un percorso più breve, Pmin, ma l'algoritmo migliorato dovrebbe trovare un percorso più breve che richiede il numero minimo di turni (Pmin, Tmin). La soluzione generale richiede che si lavori con una coppia di numeri anziché con un numero singolo. Se la nuova trovata Pnew è inferiore all'attuale Pmin OPPURE se è uguale ma Tnew è minore di Tmin quindi prendere (Pnew, Tnew) come nuovo percorso minimo.

Se la scheda è abbastanza piccolo si potrebbe ancora utilizzare un singolo numero come attualmente in uso, ma questo numero deve essere un numero composto C = P * N + T, dove N è sufficientemente grande e sufficientemente piccolo numero costante. Deve essere più grande di T possibile più grande per quella scheda, che è quasi il numero totale di tessere nel tabellone. Deve essere anche abbastanza piccolo in modo che non vi sia overflow di interi quando l'algoritmo capita di gestire il percorso più grande nella scheda, che è anche il numero totale di tessere nella scheda. Così N deve soddisfare questi due termini (B è il numero totale di piastrelle nella scheda):

N > B 
B * N < INT_MAX 

Se B è più grande di SQRT(INT_MAX) allora questo sistema è irrisolvibile, e si dovrebbe andare con coppia di valori. N dovrebbe essere SQRT(INT_MAX), che per 2 è 2 .

Il problema principale ora è come contare tutte le svolte, ma ciò dipende dall'algoritmo che si ha. Non dovrebbe essere troppo difficile aggiungere quella parte.

Answer 2

Intuitivamente, puoi farlo dando al tuo agente uno "slancio".

In particolare, aumentare la dimensione dello spazio di stato di un fattore quattro; tieni traccia di se l'agente è stato spostato in alto, a destra, a sinistra o in basso. Aumenta i costi della tua rete di qualche fattore importante e assegna una piccola penalità alle mosse che cambiano direzione.

Answer 3

Non ho familiarità con gli algoritmi di ricerca in particolare, ma questo sarebbe il miglior approccio programmatico, pseudo sotto.

oggetti che usiamo:

vertex { //generic x,y coordinate 
    int x; 
    int y; 
} 
vertices[3]; //3 vertices: 0, 1, 2 (0 is start, 1 is mid, 2 is end); 

E il nostro algoritmo, che dipende dal percorso più efficiente già trovato non avere stranezze come ¯ | _ | ¯

boolean hasObstacles = false; 

int increment = 0; 
//there's some other ways to set this up, but this should make the most sense to explaining which way we need to go 
if(vertices[0].x < vertices[2].x) 
    increment = 1; 
else 
    increment = -1; 

for(int i = vertices[0].x; i != vertices[2].x; i = i + increment) { 
    //check for collision at coordinate (i, vertices[0].y), set hasObstacles to true if collision 
} 

if(vertices[0].y < vertices[2].y) 
    increment = 1; 
else 
    increment = -1; 

for(int i = vertices[0].y; i != vertices[2].y; i = i + increment) { 
    //check for collision at coordinate (vertices[2].x, i), set hasObstacles to true if collision 
} 

if(!hasObstacles) { 
    //we can remove these 3 vertices and add this point to our list of vertices. 
    vertex corner = new vertex(vertices[2].x, vertices[0].y) // relocation of point 
} 

La scansione dovrebbe progredire un vertice Al tempo. Se i 3 vertici vengono sostituiti con un singolo vertice, la scansione successiva deve usare quel nuovo vertice come 0.

Answer 4

In questo momento il tuo algoritmo risponde alla domanda "quali quadrati attraversa il percorso ottimale?" Il tuo grafico ha un nodo per ogni quadrato e un bordo per ogni coppia di quadrati adiacenti.

Cambiare in "dove il percorso ottimale attraversa i confini tra i quadrati?"

Il grafico cambierà:

• nodi Grafico: centro di ogni confine tra piazze adiacenti + Start + finitura.
• Spigoli del grafico: in ogni quadrato collegano ogni coppia di bordi quadrati.

E ora è possibile valutare in modo diverso le connessioni dei bordi quadrati opposti e le connessioni dei bordi quadrati adiacenti. Dare un peso maggiore al secondo ridurrà il numero di zig-zag.

Answer 5

Il tuo problema non è banale perché ad es.se vai avidamente il più lontano possibile o verso destra, potresti incontrare un labirinto di oggetti che richiede un pazzesco percorso a zig-zag per finire, mentre se ti fermassi davanti al labirinto stretto potresti essere in grado di cambiare direzioni meno volte essenzialmente andando in giro nel labirinto. E potresti incontrare questo dilemma ovunque lungo il tuo cammino, non solo all'inizio. Un modo per risolvere questo problema è usare Dijkstra e definire una griglia di posizioni a cui puoi viaggiare, e quindi definire una mossa lunga 2 passi invece di 1 passo. Definire la distanza tra due punti della griglia collegati è molto piccola se il movimento è orizzontale puro o verticale in una direzione orientata e molto grande se la mossa cambia direzione nel mezzo. Quindi, assumendo che la lunghezza del percorso dall'inizio alla fine sia pari, il percorso più breve dall'inizio alla fine in questa struttura a doppio movimento sarà il percorso che riduce al minimo la quantità di zig-zag. Se la lunghezza del percorso dall'inizio alla fine è dispari, usa i punti della griglia uno spazio in orizzontale e in verticale per iniziare, quindi la lunghezza del percorso dall'inizio alla fine sarà pari (anche se dovrai eseguire la ricerca del percorso per entrambi possibili posizioni iniziali modificate).

Answer 6

Utilizzare una coppia di valori (doppi, interi o qualsiasi altra cosa) per il calcolo della distanza.

Il primo è la distanza, il secondo il numero di giri.

In ordine lessicale, quindi il primo è più importante del secondo.

Questo è più pulito di "usa una piccola penalità per i turni" sia matematicamente che a livello di programmazione.

Ogni nodo è duplicato. Il nodo "aver inserito verticalmente" e "aver inserito orizzontalmente", in quanto fanno la differenza rispetto al numero di giri.

L'euristica è la distanza di Manhattan, con una svolta se non si è esattamente allineati orizzontalmente o verticalmente con l'obiettivo.

Come lato negativo, questa tecnica interferisce con l'ottimizzazione del punto di salto, in quanto vi sono molti meno percorsi simmetrici verso una posizione (poiché alcuni percorsi hanno più svolte rispetto ad altri).

Answer 7

Internamente, l'algoritmo valuta molti percorsi possibili e sceglie quello più breve.

Se si regola leggermente l'algoritmo, quindi calcola una penalità aggiuntiva per ogni cambio di direzione, quindi sceglierà il percorso più breve con il minor numero di cambi di direzione.

Answer 8

Tutto ciò che serve è modificare leggermente l'euristica dell'algoritmo A *. Uno in cima alla mia testa: se non ti piacciono queste curve puoi penalizzare ogni turno.

Quindi la tua euristica dipenderà dal numero di turni e dalla distanza di Manhattan dal bersaglio. Una cosa importante è non dimenticare che non dovrebbe sopravvalutare la distanza dall'obiettivo. Maggiori informazioni su come selezionare heuristic here.