Larghezza prima ricerca: Knight cover

Question

Sto provando a seguire il corso di formazione USACO su algoritmi (http://ace.delos.com/usacogate) - e attualmente sono a una pagina che descrive DFS, BFS ecc. Capisco questi concetti, ma il problema di esempio loro dato per BFS - copertina del cavaliere - mi ha lasciato perplesso. Ecco la descrizione del problema:

Posiziona il minor numero di cavalieri possibile su una scacchiera n x n in modo che ogni quadrato venga attaccato. Un cavaliere non è considerato per attaccare il quadrato su cui si trova.

Questo è BFS, la pagina dice, dal momento che cerca di vedere se c'è una soluzione con n cavalieri prima di provare n+1 cavalieri - che è abbastanza chiaro.

Tuttavia, non capisco come formulare la soluzione da solo. Qualcuno può aiutarmi con lo pseudocodice per questo?

Grazie molto in anticipo!

Answer 1

È BFS, ma non si cerca la scacchiera; cercare lo spazio di posizionamenti:

Stato iniziale: nessun cavaliere è posto

mossa valido: posto un cavaliere su qualsiasi tessera non occupata

stato

Obiettivo: tutte le tessere sono o occupati o attaccati

base algoritmo (BFS dello spazio di stato):

• inserire lo stato iniziale nella coda BFS.
• mentre c'è qualcosa nella coda:
  • rimuovere uno stato dalla coda.
  • per ogni riquadro non occupato:
    • creare una copia dello stato corrente.
    • aggiungi un cavaliere a quella tessera.
    • se il nuovo stato non esiste nella coda:
      • se il nuovo stato è uno stato obiettivo, terminare.
      • altro aggiungerlo alla coda.

Si noti che sto supponendo che tutti i percorsi di uno stato sono della stessa lunghezza. Questo è vero quando si cerca un insieme di posizionamenti in questo modo, ma non è vero in generale. Nei casi in cui ciò non è vero, è necessario memorizzare l'insieme di tutti i nodi visitati per evitare di rivedere gli stati già esplorati.

---

Potrebbe essere necessario aggiungere i cavalieri da sinistra a destra, dall'alto verso il basso. Quindi non è necessario verificare la presenza di duplicati nella coda. Inoltre, puoi scartare uno stato in anticipo se sai che una tessera non attaccata non può essere attaccata senza violare l'ordine di inserimento.

Se non si esegue questa operazione e si lascia il controllo duplicato, l'algoritmo produrrà comunque risultati corretti, ma lo farà molto più lentamente. 40.000 volte più lento, approssimativamente (8! = 40 320 è il numero di duplicati di uno stato di 8 cavalieri).

---

Se si desidera un algoritmo più veloce, esaminare A *. Qui, una possibile euristica è:

• contare il numero di tessere unattacked e non occupati
• dividere il conteggio da nove, arrotondamento (cavaliere non può attaccare otto nuove piastrelle o occupare più di uno)
• la distanza (il numero di cavalieri necessari per essere aggiunto) non è più di questo numero.

Un euristico migliore noterebbe il fatto che un cavaliere può attaccare solo le tessere dello stesso colore e occupare una tessera del colore opposto. Ciò potrebbe migliorare leggermente l'euristica precedente (ma potrebbe comunque aiutare molto).

Un euristico migliore dovrebbe essere in grado di sfruttare il fatto che un cavaliere può coprire punti liberi in non più di 5x5 quadrati. Un euristico dovrebbe calcolare velocemente, ma questo può aiutare quando ci sono pochi punti da coprire.

---

Dettagli tecnici:

Si può rappresentare ogni stato come una maschera di bit a 64-bit. Sebbene ciò richieda una manipolazione bit a bit, aiuta davvero la memoria e il controllo di uguaglianza dei numeri a 64 bit è veloce. Se non puoi avere un numero a 64 bit, usa due numeri a 32 bit - questi dovrebbero essere disponibili.

La coda di array circolare è efficiente, e non è che difficile espandere la sua capacità. Se devi implementare la tua coda, scegli questa.

Answer 2

Ecco un'implementazione in C++.

Utilizza solo la forza bruta di base, quindi è valido solo fino a n = 5.

#include <iostream> 
#include <vector> 
#include <queue> 

using namespace std; 

bool isFinal(vector<vector<bool> >& board, int n) 
{ 
    for(int i = 0; i < n; ++i) 
    { 
     for(int j = 0; j < n; ++j) 
     { 
      if(!board[i][j]) 
       return false; 
     } 
    } 
    return true; 
} 

void printBoard(vector<pair<int,int> > vec, int n) 
{ 
    vector<string> printIt(n); 
    for(int i = 0; i < n; ++i) 
    { 
     string s = ""; 
     for(int j = 0; j < n; ++j) 
     { 
      s += "."; 
     } 
     printIt[i] = s; 
    } 

    int m = vec.size(); 

    for(int i = 0; i < m; ++i) 
    { 
     printIt[vec[i].first][vec[i].second] = 'x'; 
    } 

    for(int i = 0; i < n; ++i) 
    { 
     cout << printIt[i] << endl; 
    } 
    cout << endl; 
} 

void updateBoard(vector<vector<bool> >& board, int i, int j, int n) 
{ 
    board[i][j] = true; 

    if(i-2 >= 0 && j+1 < n) 
     board[i-2][j+1] = true; 

    if(i-1 >= 0 && j+2 < n) 
     board[i-1][j+2] = true; 

    if(i+1 < n && j+2 < n) 
     board[i+1][j+2] = true; 

    if(i+2 < n && j+1 < n) 
     board[i+2][j+1] = true; 

    if(i-2 >= 0 && j-1 >= 0) 
     board[i-2][j-1] = true; 

    if(i-1 >= 0 && j-2 >= 0) 
     board[i-1][j-2] = true; 

    if(i+1 < n && j-2 >= 0) 
     board[i+1][j-2] = true; 

    if(i+2 < n && j-1 >= 0) 
     board[i+2][j-1] = true; 
} 

bool isThere(vector<pair<int,int> >& vec, vector<vector<pair<int,int> > >& setOfBoards, int len) 
{ 
    for(int i = 0; i < len; ++i) 
    { 
     if(setOfBoards[i] == vec) 
      return true; 
    } 
    return false; 
} 

int main() 
{ 
    int n; 
    cin >> n; 

    vector<vector<pair<int,int> > > setOfBoards; 
    int len = 0; 

    vector<vector<bool> > startingBoard(n); 
    for(int i = 0; i < n; ++i) 
    { 
     vector<bool> vec(n,0); 
     startingBoard[i] = vec; 
    } 

    vector<pair<int,int> > startingVec; 

    vector<vector<vector<vector<bool> > > > q1; 

    vector<vector<vector<pair<int,int> > > > q2; 

    vector<vector<vector<bool> > > sLayer1; 

    vector<vector<pair<int,int> > > sLayer2; 

    sLayer1.push_back(startingBoard); 

    sLayer2.push_back(startingVec); 

    q1.push_back(sLayer1); 

    q2.push_back(sLayer2); 

    int k = 0; 

    bool flag = false; 

    int count = 0; 

    while(!flag && !q1[k].empty()) 
    { 
     int m = q1[k].size(); 

     vector<vector<vector<bool> > > layer1; 

     vector<vector<pair<int,int> > > layer2; 

     q1.push_back(layer1); 

     q2.push_back(layer2); 

     for(int l = 0; l < m; ++l) 
     { 
      vector<vector<bool> > board = q1[k][l]; 

      vector<pair<int,int> > vec = q2[k][l]; 

      if(isFinal(board, n)) 
      { 
       while(l < m) 
       { 
        board = q1[k][l]; 
        vec = q2[k][l]; 

        if(isFinal(board, n)) 
        { 
         printBoard(vec, n); 

         ++count; 
        } 

        ++l; 
       } 

       flag = true; 
       break; 
      } 

      for(int i = 0; i < n; ++i) 
      { 
       for(int j = 0; j < n; ++j) 
       { 
        if(!board[i][j]) 
        { 
         pair<int,int> p; 
         p.first = i; 
         p.second = j; 

         vector<vector<bool> > newBoard = board; 

         vector<pair<int,int> > newVec = vec; 

         newVec.push_back(p); 

         updateBoard(newBoard, i, j, n); 

         sort(newVec.begin(), newVec.end()); 

         if(!isThere(newVec, setOfBoards, len)) 
         { 
          q1[k+1].push_back(newBoard); 
          q2[k+1].push_back(newVec); 

          setOfBoards.push_back(newVec); 
          ++len; 
         } 
        } 
       } 
      } 
     } 

     ++k; 
    } 

    cout << count << endl; 
}