/
GraphSearch.cs
115 lines (106 loc) · 3.4 KB
/
GraphSearch.cs
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
using System.Collections.Generic;
using System.Linq;
using aima.core.agent;
using aima.core.search.framework;
using aima.core.search.framework.problem;
namespace aima.core.search.framework.qsearch
{
/**
* Artificial Intelligence A Modern Approach (3rd Edition): Figure 3.7, page 77.
* <br>
*
* <pre>
* function GRAPH-SEARCH(problem) returns a solution, or failure
* initialize the frontier using the initial state of problem
* initialize the explored set to be empty
* loop do
* if the frontier is empty then return failure
* choose a leaf node and remove it from the frontier
* if the node contains a goal state then return the corresponding solution
* add the node to the explored set
* expand the chosen node, adding the resulting nodes to the frontier
* only if not in the frontier or explored set
* </pre>
*
* Figure 3.7 An informal description of the general graph-search algorithm.
* <br>
* This implementation is based on the template method
* {@link #search(Problem, Queue)} from superclass {@link QueueSearch} and
* provides implementations for the needed primitive operations. In contrast to
* the code above, here, nodes resulting from node expansion are added to the
* frontier even if nodes with equal states already exist there. This makes it
* possible to use the implementation also in combination with priority queue
* frontiers.
*
* @author Ravi Mohan
* @author Ciaran O'Reilly
* @author Ruediger Lunde
*/
public class GraphSearch : QueueSearch
{
private HashSet<object> explored = new HashSet<object>();
public GraphSearch() : this(new NodeExpander())
{
}
public GraphSearch(NodeExpander nodeExpander): base(nodeExpander)
{
}
/**
* Clears the set of explored states and calls the search implementation of
* <code>QueSearch</code>
*/
public override List<Action> search(Problem problem, Queue<Node> frontier)
{
// initialize the explored set to be empty
explored.Clear();
// expandedNodes = new List<Node>();
return base.search(problem, frontier);
}
/**
* Inserts the node at the tail of the frontier if the corresponding state
* was not yet explored.
*/
protected override void addToFrontier(Node node)
{
if (!explored.Contains(node.State))
{
frontier.Enqueue(node);
updateMetrics(frontier.Count);
}
}
/**
* Removes the node at the head of the frontier, adds the corresponding
* state to the explored set, and returns the node. As the template method
* (the caller) calls {@link #isFrontierEmpty() before, the resulting node
* state will always be unexplored yet.
*
* @return the node at the head of the frontier.
*/
protected override Node removeFromFrontier()
{
Node result = frontier.Dequeue();
// add the node to the explored set
explored.Add(result.State);
updateMetrics(frontier.Count);
return result;
}
/**
* Pops nodes of already explored states from the top end of the frontier
* and checks whether there are still some nodes left.
*/
protected override bool isFrontierEmpty()
{
while (!(frontier.Count==0) && explored.Contains(frontier.Peek().State))
{
frontier.Dequeue();
}
updateMetrics(frontier.Count);
if (frontier.Count == 0)
{
return true;
}
else
return false;
}
}
}