-
Notifications
You must be signed in to change notification settings - Fork 0
/
IDAStar.py
143 lines (117 loc) · 4.51 KB
/
IDAStar.py
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
import HungarianPuzzle
import heapq
import gc
##########################################################################################################
################## Code for the data structures ##########################################################
##########################################################################################################
class IDAstarController():
def __init__(self, puzzle):
self.Root = IterativeDeepeningAStar(puzzle)
self.f_limit = 1
self.PQ = []
self.NodesExpanded = 0
heapq.heappush(self.PQ, (self.Root.GetSum(), self.Root))
self.SolvedNode = None
def ida_star(self):
print("Solving...")
self.f_limit = self.Root.GetHeuristic()
while True:
f_next, self.SolvedNode = self.search(heapq.heappop(self.PQ)[1])
if f_next == 0:
print("Number of moves to solution :",self.SolvedNode.GetDepth())
print("Nodes Expanded in final iteration :", self.NodesExpanded)
return self.NodesExpanded, self.SolvedNode.GetDepth()
else:
pass
#print("f_next : ", f_next, " (",self.NodesExpanded,")")#Progress Check
self.PQ = []
gc.collect()
heapq.heappush(self.PQ, (self.Root.GetSum(), self.Root))
self.f_limit = f_next
self.NodesExpanded=0
def search(self, node):
f_next = 100
temp, SolvedNode = self.expand(node)
self.NodesExpanded+=1
while True:
if temp == 0:
#print("Solution found, (",SolvedNode.GetSum(),")")
return 0, SolvedNode
if temp < f_next:
f_next = temp
if len(self.PQ) == 0:
return f_next, None
nextNode = heapq.heappop(self.PQ)[1]
temp, SolvedNode = self.expand(nextNode)
#if self.NodesExpanded%1000==0:
#print("f_next : ", f_next, " (",self.NodesExpanded,")")#Progress Check
return f_next, None
def expand(self, node):
self.NodesExpanded+=1
f = node.GetSum()
#node.InfoPrint()#Debuging
if f > self.f_limit:
#print("f > f_limit: ", f)
return f, None
if node.GetHeuristic() == 0:
#print("Moves made : ", node.GetDepth())
return 0, node
f_next = 100
for i in range(4):
temp = IterativeDeepeningAStar(node.GetPuzzle(), node.GetDepth()+1,i)
if temp.GetSum() <= self.f_limit:
if temp.GetHeuristic() == 0:
return 0, temp
heapq.heappush(self.PQ, (temp.GetSum(),temp))
elif temp.GetSum() < f_next:
f_next = temp.GetSum()
return f_next, None
def GetSolvedPuzzle(self):
if self.SolvedNode != None:
return self.SolvedNode.GetPuzzle()
else:
return self.Root.GetPuzzle()
class IterativeDeepeningAStar():
def __init__(self, puzzle, depth=0, move=None):
self.Puzzle = HungarianPuzzle.HungarianRings(puzzle)
self.Depth = depth
self.Direction = move
if(self.Direction == 0):
self.Puzzle.rotateCCL()
elif(self.Direction == 1):
self.Puzzle.rotateCCR()
elif(self.Direction == 2):
self.Puzzle.rotateCL()
elif(self.Direction == 3):
self.Puzzle.rotateCR()
self.HeuristicVal = self.Puzzle.getHeuristicVal()
self.Sum = self.HeuristicVal + self.Depth
def __lt__(self, other):
if self.GetSum() == other.GetSum():
return self.GetHeuristic() < other.GetHeuristic()
else:
return self.GetSum() < other.GetSum()
def __gt__(self, other):
if self.GetSum() == other.GetSum():
return self.GetHeuristic() > other.GetHeuristic()
else:
return self.GetSum() > other.GetSum()
def InfoPrint(self):
print("Depth : ", self.Depth)
print("Heuristic Value : ", self.HeuristicVal)
print("My Move : ", self.Direction)
print("")
def GetSum(self):
return self.Sum
def GetHeuristic(self):
return self.HeuristicVal
def GetDepth(self):
return self.Depth
def GetMove(self):
return self.Direction
# def GetParentIndex(self):
# return self.PredecessorIndex
# def GetIndex(self):
# return self.MyIndex
def GetPuzzle(self):
return self.Puzzle