BFS algoritmo - breve passeggiata sulla griglia con gradini vincolate

StackOverflow https://stackoverflow.com/questions/4237818

Domanda

Il problema è il seguente: Un vagabondo comincia le coordinate reticolo (x, y) e vuole raggiungere le coordinate (0,0). Da ogni GridPoint, il viandante può andare 8 passi a nord oa 3 passaggi sud o 5 passaggi a est oa ovest 6 passi (8N / 3S / 5E / 6W).

Come faccio a trovare il percorso più breve da (X, Y) a (0,0) utilizzando la ricerca in ampiezza?

Chiarimenti:

  • griglia illimitato
  • coordinate negative sono ammessi
  • Una coda (lista o array collegato) devono essere usati
  • Nessun ostacoli presenti
È stato utile?

Soluzione 4

ho intenzione di andare avanti e rispondere alla mia domanda per riferimento futuro.

psuedocodarlo: 

while (true) {
    if (destination reached)
        break;
    addToQueue(go north);
    addToQueue(go south);
    addToQueue(go east);
    addToQueue(go west);
    getNextFromQueue;
}

Si deve anche notare che il tempo di esecuzione per questa applicazione cresce molto, molto veloce, quindi provarlo con piccoli valori di coordinate. Ad esempio, le coordinate (1,1) dà 7 livelli di ampiezza e richiede 16384 iterazioni.

Altri suggerimenti

L'algoritmo per questo problema potrebbe essere:

Per ogni asse, passo verso di essa fino a quando la vostra posizione sull'altro asse è 0.

Pseudocodice: 

while (x!=0) {
  if (x>0) x-=6;
  else x+=5;
}
while (y!=0) {
  if (y>0) y-=8;
  else y+=3;
}

Tuttavia, non capisco perché è necessario per la ricerca di un percorso -. Non è che complicato

"thejh", ha sottolineato non c'è bisogno di una ricerca, ma le chiamate di assegnazione per uno.

Un approccio ragionevole è

  1. Analizza. E 'tutto posizione possibili per arbitraria (x, y) a partire? Controllo delle mosse consentite si vede che essi possono essere combinati per produrre 1-step si muove orizzontali, e 1-step si muove verticali, quindi la risposta è sì (per la vostra mano nella fornire i dettagli di questo).

  2. capire che cosa "ricerca in ampiezza" è. Wikipedia è il tuo amico (anche se, se si ha accesso a una biblioteca universitaria, io davvero consigliare di Patrick Henry Winston vecchia Intelligenza Artificiale , è veramente buono, spiegazioni molto lucide). Provalo con qualche problema più semplice.

  3. Fare il problema del incarico in quasi allo stesso modo. Chiedi qui se si riscontra un problema tecnico C ++.

Saluti e hth.,

Ecco la mia risposta (in realtà in base al largo della risposta di thejh) che utilizza una coda: 

//set x to start position
//set y to start position
do {
  if (x<0) Queue.Push(8N);
  if (x>0) Queue.Push(3S);
  if (y<0) Queue.Push(5E);
  if (y>0) Queue.Push(6W);
  while (!Queue.Empty())
  {
    Move(Queue.Pop());
  }
} while (x && y);

E 'contorto, ma segue le istruzioni.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top