[Rucksackproblem (Wikipedia)](https://ja.wikipedia.org/wiki/%E3%83%8A%E3%83%83%E3%83%97%E3%82%B5%E3%83%83 % E3% 82% AF% E5% 95% 8F% E9% A1% 8C) Zweigbegrenzungsmethode (Wikipedia) % 9E% 9D% E9% 99% 90% E5% AE% 9A% E6% B3% 95). Neulich habe ich das Rucksackproblem mit einer gierigen Methode gelöst. Lösen des Python-Rucksackproblems mit dem gierigen Algorithmus
Die gierige Methode war keine Methode, um eine genaue Lösung zu finden, sondern eine Methode, um eine Lösung zu finden, die gut aussah. Dieses Mal werden wir die Verzweigungsbegrenzungsmethode implementieren, um die genaue Lösung zu finden.
(Informationen zur Verzweigungsbegrenzungsmethode aus Wikipedia)
Verzweigungsbegrenzungsmethode (Bunshigen Teiho, Englisch: branch and bound,BB)
Dies ist ein Allzweckalgorithmus zum Finden optimaler Lösungen für verschiedene Optimierungsprobleme (insbesondere diskrete Optimierung und Kombinationsoptimierung).
Filialbetrieb (Englisch:Verzweigungsbetrieb) und eingeschränkter Betrieb (Englisch:Begrenzungsvorgang).
Es listet systematisch alle Lösungskandidaten unter Verwendung einer optimierten Schätzung der oberen und unteren Grenze auf.
Nicht optimale Kandidaten werden "in großen Mengen" weggeworfen.
Das Überprüfen aller Kandidaten wäre zu viele, daher ist es möglich, ein Minderungsproblem zu verwenden (die Lösung von x ist 0 oder 1, aber finden Sie die Lösung mit 0 <= x <= 1). Wenn es keinen gibt, habe ich das Gefühl, dass ich ihn von den Kandidaten abschneiden werde. Wenn die Lösung des Minderungsproblems kleiner ist als die Lösung der vorläufigen Lösung, wird sie von den Kandidaten entfernt.
Wir würden uns freuen, wenn Sie uns mitteilen könnten, ob es Mängel oder Verbesserungsvorschläge bezüglich des Codes gibt.
2*x1 + 3*x2 + 5*x3 + 6*x4 <= 9
xi = 0 or 1 (i = 1, 2, 3, 4)
Unter den oben genannten Bedingungen
4*x1 + 5*x2 + 12*x3 + 14*x4
Um zu maximieren( x1, x2, x3, x4 )Verwenden Sie die Verzweigungsbegrenzungsmethode.
import numpy as np
from pandas import DataFrame
import copy
class BranchAndBound:
def __init__(self, weights, values, max_weight, answer_val):
self.weights = np.array(weights)
self.values = np.array(values)
self.max_weight = max_weight
self.answer_val = answer_val
self.evaluates = self.values/self.weights
self.index_list = []
for index in range(1, len(weights) + 1):
self.index_list.append('x' + str(index))
self.target_df = DataFrame(np.c_[self.evaluates, self.weights, self.values, np.array(self.answer_val)], index=self.index_list, columns=["evaluate", "weight", "value", "ans"])
self.target_df = self.target_df.sort_values('evaluate', ascending=False)
self.answer_val = list(self.target_df['ans']) # answer_Der Wert wurde in absteigender Reihenfolge des Bewertungswerts in eins sortiert
del self.target_df['ans'] #Die Spalte "ans" wurde entfernt, da sie für DataFrame nicht mehr benötigt wird
self.target_ans = np.dot(np.array(answer_val), values)
self.index_list = self.target_df.index #Indexreihenfolge ändern
def __judgeValue(self, fixed_list): # fixed_Lösen Sie das Schadensbegrenzungsproblem mit dem festen Wert von x, der in der Liste übergeben wurde, und beurteilen Sie die Fortsetzung der Verzweigung. Wenn eine bessere Lösung gefunden wird, wird die vorläufige Lösung ausgetauscht.
sum_weight = 0 #Das Gesamtgewicht des angenommenen x
evaluate_list = [] #Speichert die Akzeptanzentscheidung
evaluate_list.extend(fixed_list)
for index, val in enumerate(fixed_list):
sum_weight += self.target_df.ix[self.index_list[index]]['weight']*val # fixed_Das Gesamtgewicht der in der Liste übergebenen x-Werte
for index in range(len(fixed_list), len(self.index_list)):
if sum_weight > self.max_weight: #max_Wenn das Gewicht überschritten wird, endet der Zweig
return False #Zweigende
elif sum_weight == self.max_weight: #max_Da das Gewicht erreicht wurde, ist das andere x 0
evaluate_list.append(0)
continue
else:
if sum_weight + self.target_df.ix[self.index_list[index]]['weight'] < self.max_weight: # x=Auch wenn es 1 ist, max_Wenn das Gewicht nicht erreicht ist
sum_weight += self.target_df.ix[self.index_list[index]]['weight']
evaluate_list.append(1)
else: # 0 < x <=Wenn es 1 wird
evaluate_list.append((self.max_weight - sum_weight)/self.target_df.ix[self.index_list[index]]['weight'])
sum_weight = self.max_weight
if (self.max_weight - sum_weight) == self.target_df.ix[self.index_list[index]]['weight']: # x=Wenn 1, ersetzen Sie die vorläufige Lösung
evaluate_list_count = len(evaluate_list)
for i in range(evaluate_list_count, len(self.index_list)): #Geben Sie 0 für alle x ein, die noch nicht entschieden wurden
evaluate_list.append(0)
self.target_ans = np.dot(np.array(evaluate_list), np.array(self.target_df.value)) #Vorläufiges Lösungsziel_Ans ersetzen
self.answer_val = evaluate_list #Vorläufige Antwort Antwort_Val ersetzen
return False #Zweigende
if len(fixed_list) == len(self.index_list): #Vergleich mit der vorläufigen Lösung, wenn alle x-Werte fest sind
if (sum_weight <= self.max_weight) and (np.dot(np.array(fixed_list), np.array(self.target_df.value)) > self.target_ans): #Vergleich mit der vorläufigen Lösung
self.target_ans = np.dot(np.array(fixed_list), np.array(self.target_df.value)) #Vorläufiges Lösungsziel_Ans ersetzen
self.answer_val = fixed_list #Vorläufige Antwort Antwort_Val ersetzen
return False
if np.dot(np.array(evaluate_list), np.array(self.target_df.value)) > self.target_ans: #Wenn die Lösung des Minderungsproblems die vorläufige Lösung überschreitet
return True #Fortsetzung der Niederlassung
else: #Wenn die vorläufige Lösung nicht überschritten wird
return False #Zweigende
def breadthFirstSearch(self): #Suche nach Breitenpriorität
search_lists = [[0], [1]] #Element[0]、[1]Zuerst einsetzen
while len(search_lists) != 0: # search_Fahren Sie fort, bis die Listen leer sind
first_list = search_lists[0] #Denken Sie in der Warteschlange, holen Sie sich eine von oben
search_lists.pop(0) #Löschen Sie das erfasste Element
if self.__judgeValue(first_list): #Ob die Suche fortgesetzt wird
new_list_cp = copy.deepcopy(first_list) #Tief kopieren, um dem nächsten Element "1" hinzuzufügen
new_list_cp.append(0) #Fügen Sie am Ende 0 hinzu
search_lists.append(new_list_cp) #Suche nach neuen Elementen_Am Ende der Listen speichern
new_list_cp = copy.deepcopy(first_list) #Tief kopieren, um dem nächsten Element "0" hinzuzufügen
new_list_cp.append(1) #Addiere 1 zum Ende
search_lists.append(new_list_cp) #Suche nach neuen Elementen_Am Ende der Listen speichern
print("-----Suche nach Breitenpriorität-----")
for index, val in enumerate(self.index_list):
print(val + ": " + str(self.answer_val[index]))
print("ans: " + str(self.target_ans))
def depthFirstSearch(self): #Tiefenprioritätssuche
search_lists = [[0], [1]] #Element[0]、[1]Zuerst einsetzen
while len(search_lists) != 0: # search_Fahren Sie fort, bis die Listen leer sind
first_list = search_lists[0] #Denken Sie mit Stach, holen Sie sich einen von oben
search_lists.pop(0) #Löschen Sie das erfasste Element
if self.__judgeValue(first_list): #Ob die Suche fortgesetzt wird
new_list_cp = copy.deepcopy(first_list) #Tief kopieren, um dem nächsten Element "1" hinzuzufügen
new_list_cp.append(1) #Addiere 1 zum Ende
search_lists.insert(0, new_list_cp) #Suche nach neuen Elementen_Am Anfang von Listen speichern
new_list_cp = copy.deepcopy(first_list) #Tief kopieren, um dem nächsten Element "0" hinzuzufügen
new_list_cp.append(0) #Fügen Sie am Ende 0 hinzu
search_lists.insert(0, new_list_cp) #Suche nach neuen Elementen_Am Anfang von Listen speichern
print("-----Tiefenprioritätssuche-----")
for index, val in enumerate(self.index_list):
print(val + ": " + str(self.answer_val[index]))
print("ans: " + str(self.target_ans))
# BranchAndBound(weight_list(a1, a2, a3, a4), value_list(c1, c2, c3, c4), max_weight(a_max), first_values(x1, x2, x3, x4))
# first_Werte können alles sein, aber hier gierig-Die durch den Algorithmus erhaltene Lösung wird als Anfangswert angegeben.
bb = BranchAndBound([2, 3, 5, 6], [4, 5, 12, 14], 9, [1, 0, 0, 1] )
bb.breadthFirstSearch()
bb = BranchAndBound([2, 3, 5, 6], [4, 5, 12, 14], 9, [1, 0, 0, 1] )
bb.depthFirstSearch()
Bei der Verzweigungsbegrenzungsmethode scheint es eine Tiefenprioritätssuche und eine Breitenprioritätssuche zu geben, daher habe ich beide Methoden ausprobiert.
Es scheint, dass die Menge an Code etwas mehr reduziert werden kann. ..
-----Suche nach Breitenpriorität-----
x3: 0
x4: 1
x1: 0
x2: 1
ans: 19.0
-----Tiefenprioritätssuche-----
x3: 0
x4: 1
x1: 0
x2: 1
ans: 19.0
Deshalb, ( x1, x2, x3, x4 ) = ( 0, 1, 0, 1 )
Recommended Posts