-
Notifications
You must be signed in to change notification settings - Fork 89
/
IDAStar.java
executable file
·181 lines (155 loc) · 6.16 KB
/
IDAStar.java
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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
/**
* Copyright (C) 2013-2018 Centro de Investigación en Tecnoloxías da Información (CITIUS) (http://citius.usc.es)
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package es.usc.citius.hipster.algorithm;
import es.usc.citius.hipster.model.node.HeuristicNode;
import es.usc.citius.hipster.model.node.factory.NodeExpander;
/**
* <p>
* Implementation of the IDA* algorithm. Similar to Iterative DFS but using heuristics to limit
* the space search and keeping a very low memory usage.
* </p>
*
* <a href="http://www.sciencedirect.com/science/article/pii/0004370285900840">Original paper</a>:
* Richard E. Korf <i><b>"Depth-first Iterative-Deepening: An Optimal Admissible Tree Search."</b></i>,
* Artificial Intelligence, vol. 27, pp. 97-109, 1985.
*
* @param <A> action type.
* @param <S> state type.
* @param <C> comparable cost used to compare states.
* @param <N> type of the heuristic search node.
*
* @author Pablo Rodríguez Mier <<a href="mailto:pablo.rodriguez.mier@usc.es">pablo.rodriguez.mier@usc.es</a>>
* @author Jennnnyz
*
*/
public class IDAStar<A,S,C extends Comparable<C>,N extends HeuristicNode<A,S,C,N>> extends DepthFirstSearch<A,S,N> {
/**
*
* @param initialNode
* @param expander
*/
public IDAStar(N initialNode, NodeExpander<A,S,N> expander) {
super(initialNode, expander);
}
/**
* IDA iterator. It expands the next state to be explored. Backtracking
* is automatically performed so if the state reaches a dead-end the next
* call to {@code iterator.next()} returns the next state after performing
* backtracking.
*/
public class Iterator extends DepthFirstSearch.Iterator {
protected C fLimit;
protected C minfLimit;
protected int reinitialization = 0;
protected Iterator(){
// Set initial bound
super();
fLimit = initialNode.getEstimation();
minfLimit = null;
}
protected void updateMinFLimit(C currentFLimit){
if (minfLimit == null){
minfLimit = currentFLimit;
} else {
if (minfLimit.compareTo(currentFLimit)>0){
minfLimit = currentFLimit;
}
}
}
@Override
protected StackFrameNode nextUnvisited(){
StackFrameNode nextNode;
do {
nextNode = processNextNode();
// No more neighbors to visit with the current fLimit. Update the new fLimit
if (nextNode == null){
// Reinitialize
if (minfLimit != null && minfLimit.compareTo(fLimit)>0){
fLimit = minfLimit;
reinitialization++;
minfLimit = null;
super.getStack().addLast(new StackFrameNode(initialNode));
nextNode = processNextNode();
}
}
} while(nextNode != null && (nextNode.processed || nextNode.visited));
if (nextNode != null){
nextNode.visited = true;
}
return nextNode;
}
@Override
protected StackFrameNode processNextNode(){
// Get and process the current node. Cases:
// 1 - empty stack, return null
// 2 - node exceeds the bound: update minfLimit, pop and skip.
// 3 - node has neighbors: expand and return current.
// 4 - node has no neighbors:
// 4.1 - Node visited before: processed node, pop and skip to the next node.
// 4.2 - Not visited: we've reached a leaf node.
// mark as visited, pop and return.
// 1- If the stack is empty, change fLimit and reinitialize the search
if (super.getStack().isEmpty()) return null;
// Take current node in the stack but do not remove
StackFrameNode current = (StackFrameNode) super.stack.peekLast();
// 2 - Check if the current node exceeds the limit bound
C fCurrent = current.getNode().getScore();
if (fCurrent.compareTo(fLimit)>0){
// Current node exceeds the limit bound, update minfLimit, pop and skip.
updateMinFLimit(fCurrent);
// Remove from stack
current.processed = true;
return (StackFrameNode) super.getStack().removeLast();
}
// Find a successor
if (current.getSuccessors().hasNext()){
// 3 - Node has at least one neighbor
N successor = current.getSuccessors().next();
// push the node
super.getStack().addLast(new StackFrameNode(successor));
return current;
} else {
// 4 - Visited?
if (current.visited){
current.processed = true;
}
return (StackFrameNode) super.getStack().removeLast();
}
}
public C getfLimit() {
return fLimit;
}
public void setfLimit(C fLimit) {
this.fLimit = fLimit;
}
public C getMinfLimit() {
return minfLimit;
}
public void setMinfLimit(C minfLimit) {
this.minfLimit = minfLimit;
}
public int getReinitialization() {
return reinitialization;
}
public void setReinitialization(int reinitialization) {
this.reinitialization = reinitialization;
}
}
@Override
public Iterator iterator() {
return new Iterator();
}
}