Ciao a tutti,

stavo provando ad implementare l'algoritmo BFS per risolvere un problema...

Nello specifico, stavo leggendo un libro di AI, e descriveva il BFS per risolvere un problema coi secchi:

"Hai due secchi, uno da 4 litri e uno da 3, e una canna dell'acqua per riempirli. Come puoi ottenere esattamente 2 litri di acqua nel secchio da 4?"

Il programma fa una "ricerca nello spazio degli stati": parte da uno stato, e applicando delle regole, cerca di ottenere uno stato che sia considerato una soluzione del problema.

Quindi, io ho definito la class State:
codice:
class State
{
    private:
    char _x;  //Secchio da 4 litri
    char _y;  //Secchio da 3 litri

    public:
    State(int x, int y) { _x = x; _y = y; }
    char X() { return _x; }
    char Y() { return _y; }
};
Che rappresenta lo stato dei due secchi. (Ovviamente lo stato è costante una volta creato: l'obiettivo non è modificarlo ma ottenerne uno nuovo).

Poi ho definito il tipo Rule facendo un typedef:
codice:
typedef State* (*Rule)(State*);
In questo modo Rule è un alias per un puntatore a funzione che prende un puntatore a State e ne ritorna un altro. Ho poi implementato le 10 regole a disposizione del problema in 10 funzioni separate, ognuna con le sue condizioni etc.

L'algoritmo di ricerca è questo:
codice:
bool contains(vector<State*> vec, State* val)
{
    for (unsigned int i = 0; i < vec.size(); i++)
        if (vec[i] == val) return true;
    return false;
}

State* bfs(State s0, vector<Rule> rules, vector<State*> finalStates)
{
    queue<State*> searchSpace;
    State* exState = &s0;
    State* retState = NULL;

    while (!(contains(finalStates, exState)))
    {
        for (unsigned int i = 0; i < rules.size(); i++)
        {
            retState = rules[i](exState);
            if (retState != NULL)
                searchSpace.push(retState);
        }

        exState = searchSpace.front();
        searchSpace.pop();
    }

    return exState;
}
La logica è:
_prendi il primo stato dalla coda
_verifica se è contenuto tra le soluzioni accettabili
_se lo è, ritornalo
_altrimenti, applica ogni regola a questo stato e aggiungi lo stato che ne risulta alla coda
(se la regola non si può applicare, la regola ritorna NULL che non viene aggiunto alla coda)
_ricomincia dal punto 1.

Sembrerebbe giusto, no? Il punto è che questo problema si può risolvere con una sequenza di meno di 10 passi... e io sono costretto a terminare il processo con la forza, dato che non raggiunge una soluzione (però mi segna un'occupazione di memoria di più di 3GB), il che mi fa pensare che ci sia qualche problema nell'algoritmo di ricerca che non lo fa mai terminare...

Posto il codice completo compilabile:

codice:
#include <iostream>

#include <vector>
#include <queue>

using namespace std;

class State
{
    private:
    char _x;
    char _y;

    public:
    State(int x, int y) { _x = x; _y = y; }
    char X() { return _x; }
    char Y() { return _y; }
};

typedef State* (*Rule)(State*);

bool contains(vector<State*> vec, State* val)
{
    for (unsigned int i = 0; i < vec.size(); i++)
        if (vec[i] == val) return true;
    return false;
}

State* bfs(State s0, vector<Rule> rules, vector<State*> finalStates)
{
    queue<State*> searchSpace;
    State* exState = &s0;
    State* retState = NULL;

    while (!(contains(finalStates, exState)))
    {
        for (unsigned int i = 0; i < rules.size(); i++)
        {
            retState = rules[i](exState);
            if (retState != NULL)
                searchSpace.push(retState);
        }

        exState = searchSpace.front();
        searchSpace.pop();
    }

    return exState;
}

vector<Rule> get_rules();

int main()
{
    State start_state(0,0); //Stato di partenza: secchi vuoti
    State* solution = NULL;

    vector<State*> solutions;   //Stati soluzione (contiene solo (4,0))
    solutions.push_back(new State(4, 0));

    cout << "Starting search...\n";

    solution = bfs(start_state, get_rules(), solutions);

    cout << "Solution found: (" << solution->X() << ", " << solution->Y() << ")\n";

    return 0;
}

/* ######## Regole ######## */
State* r1(State* s)
{
    if (s->X() < 4)
        return new State(4, s->Y());
    else
        return NULL;
}

State* r2(State* s)
{
    if (s->Y() < 3)
        return new State(s->X(), 3);
    else
        return NULL;
}

State* r3(State* s)
{
    if (s->X() > 0)
        return new State(0, s->Y());
    else
        return NULL;
}

State* r4(State* s)
{
    if (s->Y() > 0)
        return new State(s->X(), 0);
    else
        return NULL;
}

State* r5(State* s)
{
    if ( (s->X() + s->Y()) >= 4 && s->Y() > 0 )
        return new State( 4, (s->Y() - (4 - s->X())) );
    else
        return NULL;
}

State* r6(State* s)
{
    if ( (s->X() + s->Y()) >= 3 && s->X() > 0 )
        return new State( s->X() - (3 - s->Y()), 3);
    else
        return NULL;
}

State* r7(State* s)
{
    if ( (s->X() + s->Y()) <= 4 && s->Y() > 0 )
        return new State( (s->X() + s->Y()), 0 );
    else
        return NULL;
}

State* r8(State* s)
{
    if ( (s->X() + s->Y()) <= 3 && s->X() > 0 )
        return new State( 0 , (s->X() + s->Y()));
    else
        return NULL;
}

State* r9(State* s)
{
    if ( s->X() == 0 && s->Y() == 2 )
        return new State( 2 , 0 );
    else
        return NULL;
}

State* r10(State* s)
{
    if ( s->X() == 2 )
        return new State( 0 , s->Y());
    else
        return NULL;
}

vector<Rule> get_rules()
{
    vector<Rule> result;

    result.push_back(r1);
    result.push_back(r2);
    result.push_back(r3);
    result.push_back(r4);
    result.push_back(r5);
    result.push_back(r6);
    result.push_back(r7);
    result.push_back(r8);
    result.push_back(r9);
    result.push_back(r10);

    return result;
}