-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathBS.py
163 lines (116 loc) · 6.18 KB
/
BS.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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#imports
import copy
import operator
import queue
from numpy import sort
from functions import *
from Node import *
class BS:
instance = []
flowList =[]
distanceList=[]
size = 0
same_value_solution = 0
upperBound =0
resolutionsQueue = queue.Queue()
percentage_acceptable = 60
#methods
def __init__(self,w,d,percent):
self.flowList = w
self.distanceList = d
self.size = len(w)
self.percentage_acceptable = percent
def initUpperBound(self):
best = 0
for x in range(0, 9):
problem_list = init_problem_instance(self.size)
if x == 0:
best = objective_function(problem_list, self.flowList, self.distanceList)
continue
problem_value = objective_function(problem_list, self.flowList, self.distanceList)
if problem_value >= best:
best = problem_value
self.upperBound = best
def solve(self):
#inicjowanie potencjalnie najlepszego rozwiazania
self.initUpperBound()
for x in range(0, self.size ): #dodaj pierwsze node'y
temp_instance=Node([x], objective_function([x],self.flowList, self.distanceList))
self.resolutionsQueue.put(temp_instance)
while( self.resolutionsQueue.empty() != True ):
instance = self.resolutionsQueue.get()
if(len(instance.node_list) == self.size): #jesli jest lisciem
if instance.value < self.upperBound : # jezeli rozwiazanie lepsze to je zapisz
self.instance = copy.copy(instance.node_list)
self.upperBound = copy.copy(instance.value)
self.same_value_solution = 0
print("New value: ", self.upperBound, "New best sequence", self.instance)
if instance.value == self.upperBound:
self.same_value_solution += 1
else: ##jeśli nie jest liściem
best_kids_of_all_time = []
bs_child_list = []
for x in range(0,self.size): #kolejne dzieci
if x in instance.node_list: #jesli zaklad zostal juz przydzielony pomiń
continue
child_list = copy.copy(instance.node_list)
child_list.append(x)
bs_child_list.append(Node(child_list, objective_function(child_list,self.flowList, self.distanceList)))
##dodanie wszystkich dzieci do listy
for bs in bs_child_list:## zachłannie przydzielana wartosc dla dziecka dziecka
best_child = []
best = 0
for x in range( 0, self.size): #ZNAJDZ NAJLEPSZE DZIECKO I ZAPISZ DO BEST I BEST_CHILD
if x in bs.node_list:
continue
child = copy.copy(bs.node_list)
child.append(x)
if best_child == [] : # jesli pusty to ustaw pierwszy
best_child = copy.copy(child)
best = objective_function(best_child, self.flowList, self.distanceList)
c = objective_function(child, self.flowList, self.distanceList)
if c < best:
best_child = copy.copy(child)
best = c #Najlepsze dziecko dziecka (najlepszy wnuk)
best_kids_of_all_time.append(Node(best_child, best))
newlist = sorted(best_kids_of_all_time, key=operator.attrgetter("value"))
elements_count = int((len(newlist) * (self.percentage_acceptable/100) )) + 1
for x in range(0,elements_count):
elem = copy.copy(newlist[x])
if elem.value > self.upperBound: ##jeśli wartość tymczasowego rozwiazanie jest wieksza od upperBound nie rozwijaj drzewa dalej
continue
self.resolutionsQueue.put(elem)
return 0
def solveSecond(self):
#inicjowanie potencjalnie najlepszego rozwiazania
self.initUpperBound()
for x in range(0, self.size ): #dodaj pierwsze node'y
temp_instance=Node([x], objective_function([x],self.flowList, self.distanceList))
self.resolutionsQueue.put(temp_instance)
while( self.resolutionsQueue.empty() != True ):
instance = self.resolutionsQueue.get()
if(len(instance.node_list) == self.size): #jesli jest lisciem
if instance.value < self.upperBound : # jezeli rozwiazanie lepsze to je zapisz
self.instance = copy.copy(instance.node_list)
self.upperBound = copy.copy(instance.value)
self.same_value_solution = 0
print("New value: ", self.upperBound, "New best sequence", self.instance)
if instance.value == self.upperBound:
self.same_value_solution += 1
else: ##jeśli nie jest liściem
bs_child_list = []
for x in range(0,self.size): #kolejne dzieci
if x in instance.node_list: #jesli zaklad zostal juz przydzielony pomiń
continue
child_list = copy.copy(instance.node_list)
child_list.append(x)
bs_child_list.append(Node(child_list, objective_function(child_list,self.flowList, self.distanceList)))
##dodanie wszystkich dzieci do listy
newlist = sorted(bs_child_list, key=operator.attrgetter("value"))
elements_count = int((len(newlist) * (self.percentage_acceptable/100) )) + 1
for x in range(0,elements_count):
elem = copy.copy(newlist[x])
if elem.value > self.upperBound: ##jeśli wartość tymczasowego rozwiazanie jest wieksza od upperBound nie rozwijaj drzewa dalej
continue
self.resolutionsQueue.put(elem)
return 0