[C++] Breadth First Search

**Ippo343** · 11-08-2010, 14:41

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;
}

**Ippo343** · 13-08-2010, 01:42

Ok, quello in C++ continua a non funzionare e ormai, sinceramente, ho lasciato perdere, soprattutto considerando che in Haskell sono riuscito a risolverlo molto più facilmente.

Non è ancora completo (infatti si limita a trovare lo stato finale e non il percorso che ci arriva: quello non so ancora come farlo, però intanto riesce a risolvere il problema, e già così è tanta roba), però almeno questo termina.

Se a qualcuno interessasse qui c'è il codice:

codice:

import Data.Maybe

s0 = [(0,0)]
solution = (2,0)

applyRule :: (Integer, Integer) -> ( (Integer, Integer) -> Maybe (Integer, Integer) ) -> Maybe (Integer, Integer)
applyRule state rule = rule state

bfs :: [ (Integer, Integer) -> Maybe (Integer, Integer)] -> [(Integer, Integer)] -> (Integer, Integer) -> Maybe (Integer, Integer)
bfs _ [] _ = Nothing
bfs rls (s:ss) sln
	| s == sln = Just s
	| otherwise = bfs rls searchSpace sln where
		searchSpace = ss ++ catMaybes (map (applyRule s) rules)

----- Rules -----

rules :: [ (Integer, Integer) -> Maybe (Integer, Integer) ]
rules = [rule1, rule2, rule3, rule4, rule5, rule6, rule7, rule8, rule9, rule10]

rule1 :: (Integer, Integer) -> Maybe (Integer, Integer)
rule1 (x, y)
	| x < 4 = Just (4, y)
	| otherwise = Nothing

rule2 (x, y)
	| y < 3 = Just (x, 3)
	| otherwise = Nothing

rule3 (x, y)
	| x > 0 = Just (0, y)
	| otherwise = Nothing

rule4 (x, y)
	| y > 0 = Just (x, 0)
	| otherwise = Nothing

rule5 (x, y)
	| ((x + y) >= 4 && (y > 0)) = Just (4, y-(4-x))
	| otherwise = Nothing

rule6 (x, y)
	| ((x + y) >= 3 && (x > 0)) = Just (x-(3-y), 3)
	| otherwise = Nothing

rule7 (x, y)
	| ((x + y) <= 4 && (y > 0)) = Just (x + y, 0)
	| otherwise = Nothing

rule8 (x, y)
	| ((x + y) <= 3 && (x > 0)) = Just (0, x + y)
	| otherwise = Nothing

rule9 (x, y)
	| (x,y) == (0,2) = Just (2, 0)
	| otherwise = Nothing

rule10 (x, y)
	| (x,y) == (2,y) = Just (0, y)
	| otherwise = Nothing

Credo che si possa chiudere.

**Ippo343** · 13-08-2010, 11:37

E questo trova anche il percorso per raggiungere uno stato:

codice:

import Data.Maybe

-- State definition
data State = State { state :: (Int, Int), route :: [(Int, Int)] } deriving (Show)

-- Initial state and final state
s0 :: [State]
solution :: State
s0 = [ (State (0,0) []) ]
solution = State (2,0) []

-- Compares states
sameState :: State -> State -> Bool
sameState (State {state = s1}) (State {state = s2}) = s1 == s2

-- Applies a rule to a state
applyRule :: State -> ( State -> Maybe State ) -> Maybe State
applyRule state rule = rule state

bfs :: [State] ->  [ State -> Maybe State] -> State -> Maybe State
bfs _ [] _ = Nothing
bfs [] _ _ = Nothing
bfs (sc:slist) rules sln
	| sameState sc sln = Just sc
	| otherwise = bfs searchSpace rules sln where
		searchSpace = slist ++ catMaybes (map (applyRule sc) rules)
	

----- Rules -----
rules :: [ State -> Maybe State ]
rules = [rule1, rule2, rule3, rule4, rule5, rule6, rule7, rule8, rule9, rule10]

rule1 :: State -> Maybe State
rule1 (State (x, y) parents)
	| x < 4 = Just (State (4, y) (parents ++ [(x,y)]) )
	| otherwise = Nothing

rule2 (State (x, y) parents)
	| y < 3 = Just (State (x, 3) (parents ++ [(x,y)]) )
	| otherwise = Nothing

rule3 (State (x, y) parents)
	| x > 0 = Just (State (0, y) (parents ++ [(x,y)]) )
	| otherwise = Nothing

rule4 (State (x, y) parents)
	| y > 0 = Just (State (x, 0) (parents ++ [(x,y)]) )
	| otherwise = Nothing

rule5 (State (x, y) parents)
	| ((x + y) >= 4 && (y > 0)) = Just (State (4, y-(4-x)) (parents ++ [(x,y)]) )
	| otherwise = Nothing

rule6 (State (x, y) parents)
	| ((x + y) >= 3 && (x > 0)) = Just (State (x-(3-y), 3) (parents ++ [(x,y)]) )
	| otherwise = Nothing

rule7 (State (x, y) parents)
	| ((x + y) <= 4 && (y > 0)) = Just (State (x + y, 0) (parents ++ [(x,y)]) )
	| otherwise = Nothing

rule8 (State (x, y) parents)
	| ((x + y) <= 3 && (x > 0)) = Just (State (0, x + y) (parents ++ [(x,y)]) )
	| otherwise = Nothing

rule9 (State (x, y) parents)
	| (x,y) == (0,2) = Just (State (2, 0) (parents ++ [(x,y)]) )
	| otherwise = Nothing

rule10 (State (x, y) parents)
	| (x,y) == (2,y) = Just (State (0, y) (parents ++ [(x,y)]) )
	| otherwise = Nothing

**Ippo343** · 14-08-2010, 14:16

Ed ecco la versione finale. Ora se uno stato è irraggiungibile non blocca più il programma, ma la ricerca finisce con risultato Nothing.

Vorrei richiamare la vostra attenzione su quella che considero la linea di codice più figa mai vista :P

codice:

u = [ (x,y) | x <- [1..4], y <- [1..3] ]

Che definisce u come l'insieme di tutte le coppie di interi tali che x è compresa tra 1 e 4 e y è compresa tra 1 e 3...

codice:

import Data.Maybe

-- State definition
data State = State {state :: (Int, Int), route :: [(Int, Int)]} deriving (Show)
instance Eq State where
  State s1 r1 == State s2 r2 = s1 == s2

-- Initial state and final state
s0 :: [State]
solution :: State
s0 = [ (State (0,0) []) ]
solution = State (2,0) []

-- Applies a rule to a state
applyTo :: State -> ( State -> Maybe State ) -> Maybe State
applyTo state rule = rule state

-- BFS Search

u :: [(Int, Int)]
u = [ (x,y) | x <- [1..4], y <- [1..3] ]

search :: (Int, Int) -> [(State -> Maybe State)] -> (Int, Int) -> Maybe State
search (x0,y0) rules (x',y') =
	bfs [(State (x0,y0) [])] [] rules (State (x',y') [])

bfs :: [State] -> [State] -> [(State -> Maybe State)] -> State -> Maybe State
bfs [] _ _ _ = Nothing
bfs (sc:ss) visited rules sln
	| sc == sln = Just sc
	| otherwise = bfs searchSpace visitedSpace rules sln where
		visitedSpace = sc : (listrm1 visited sc)
		searchSpace = listrm (ss ++ newStates) visitedSpace where
			newStates = catMaybes (map (applyTo sc) rules)

-- listrm
listrm :: (Eq a) => [a] -> [a] -> [a]
listrm [] _ = []
listrm ls [] = ls
listrm ls (y:ys) = listrm1 (listrm ls ys) y

listrm1 :: (Eq a) => [a] -> a -> [a]
listrm1 [] _ = []
listrm1 (x:xs) y
	| x == y = g
	| otherwise = x : g where
		g = listrm1 xs y

----- Rules -----
rules :: [ State -> Maybe State ]
rules = [rule1, rule2, rule3, rule4, rule5, rule6, rule7, rule8, rule9, rule10]

rule1 :: State -> Maybe State
rule1 (State (x, y) parents)
	| x < 4 = Just (State (4, y) (parents ++ [(x,y)]) )
	| otherwise = Nothing

rule2 (State (x, y) parents)
	| y < 3 = Just (State (x, 3) (parents ++ [(x,y)]) )
	| otherwise = Nothing

rule3 (State (x, y) parents)
	| x > 0 = Just (State (0, y) (parents ++ [(x,y)]) )
	| otherwise = Nothing

rule4 (State (x, y) parents)
	| y > 0 = Just (State (x, 0) (parents ++ [(x,y)]) )
	| otherwise = Nothing

rule5 (State (x, y) parents)
	| ((x + y) >= 4 && (y > 0)) = Just (State (4, y-(4-x)) (parents ++ [(x,y)]) )
	| otherwise = Nothing

rule6 (State (x, y) parents)
	| ((x + y) >= 3 && (x > 0)) = Just (State (x-(3-y), 3) (parents ++ [(x,y)]) )
	| otherwise = Nothing

rule7 (State (x, y) parents)
	| ((x + y) <= 4 && (y > 0)) = Just (State (x + y, 0) (parents ++ [(x,y)]) )
	| otherwise = Nothing

rule8 (State (x, y) parents)
	| ((x + y) <= 3 && (x > 0)) = Just (State (0, x + y) (parents ++ [(x,y)]) )
	| otherwise = Nothing

rule9 (State (x, y) parents)
	| (x,y) == (0,2) = Just (State (2, 0) (parents ++ [(x,y)]) )
	| otherwise = Nothing

rule10 (State (x, y) parents)
	| (x,y) == (2,y) = Just (State (0, y) (parents ++ [(x,y)]) )
	| otherwise = Nothing

Discussione: [C++] Breadth First Search

Strumenti discussione

Ricerca discussione

Visualizza

[C++] Breadth First Search

Permessi di invio