-
Notifications
You must be signed in to change notification settings - Fork 0
/
BreadthFirstSearch.h
67 lines (52 loc) · 1.88 KB
/
BreadthFirstSearch.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#ifndef BIUPROJECT2_BFS_H
#define BIUPROJECT2_BFS_H
#include <vector>
#include <queue>
#include "PQSearcher.h"
#include "State.h"
template <class P, class S>
class BreadthFirstSearch : public ISearcher<P,S> {
private:
int numberOfNodesEvaluated;
public:
BreadthFirstSearch() {
numberOfNodesEvaluated = 0;
}
S search(ISearchable<P>* searchable) override {
/* Get the initial state and the goal state from the searchable. */
State<P> *initial = searchable->getInitialState();
State<P> *goal = searchable->getGoalState();
std::queue<State<P>*> qs;
qs.push(initial);
initial->setVisited(true);
State<P>* node;
/* Loop on every node. */
while (!qs.empty()) {
node = qs.front();
qs.pop(); //delete the element we have just gotten.
this->numberOfNodesEvaluated++;
if (node->Equals(searchable->getGoalState())) {
return goal;
}
/* Iterate on all of node's children. */
std::vector<State<P>*> possibles = searchable->getAllPossibleStates(node);
typename std::vector<State<P>*>::iterator itor;
for (itor = possibles.begin(); itor != possibles.end(); itor++) {
/* If a child node wasn't visited, add to queue. */
if (!(*itor)->isVisited()) {
(*itor)->setVisited(true);
qs.push(*itor);
/* Update where we got to the node from.*/
(*itor)->setCameFrom(node);
/* Update node's cost. */
(*itor)->setCost((*itor)->getCost() + node->getCost());
}
}
}
return node; //all sons weren't goal.
}
int getNumberOfNodesEvaluated() {
return this->numberOfNodesEvaluated;
}
};
#endif //BIUPROJECT2_BFS_H