Schneid Kosten Algorithmus Optimierung

Question

Ich habe ein Blatt Holz und haben N Markierung auf Holz gegeben sheet.Now ich alle Markierungen auf Holzplatte geschnitten haben, so dass Kosten alle Markierungen in minimum.Now des Schneidens nehme ich immer zuerst auf der i th Markierung dann werden die Kosten durch Verwendung von zwei Multiplizierern a und b gegeben, die Eingänge sind und die Kosten sind a * (l) + b * (rechts), in dem nach links und rechts sind die Größe des verbleibenden Teils des Holzes nach .für Beispiel Schneiden wenn ich ein holz der länge 10 und a = 3 und b = 4 habe und wenn ich eine markliste für ex habe: [1,3,5,7,10] so kann ich die erste und letzte markierung nicht schneiden, weil sie die anfangs- und die letzte sind Endpunkt des Holzes also angenommen, wenn ich mit Markierung 7 zuerst beginne, dann werden die Kosten des Schneidens 3 * (7-1) + 4 * (10-7) = 18 + 12 = 30 sein und jetzt ist das Holz, das ich haben würde eine, die mit Markierung 1 beginnt, um 7 zu markieren, und andere würde eins mit Markierung 7 bis zum Ende der Holzanzeige sein und ich würde den Prozess wiederholen, bis alle Markierungen geschnitten worden sind.

Jetzt nach dem Lesen der Frage kam mir sofort in den Sinn, dass, um das Holz in minimalen Kosten zu schneiden ich zuerst den Mittelpunkt finden muss (Median der Schnittpunkte) und dort sollte ich das Holz schneiden und diesen Prozess wiederholen immer wieder, bis das Holz keine Schnittpunkte mehr hat, aber ich habe Probleme mit dem Lösen des richtigen Holzes nach dem Schneiden

Beispiel Eingabe: Holz mit [1,3,5,9,16,22] würde geschnitten haben Mindestkosten = 163, wenn wir zuerst mit Median 9 anfangen, dann würden wir Holz der Marke [1,3,5,9] und [9,16,22] haben, das zuerst das linke Holz löst, das wir haben würden [1,3,5 ] [5,9], nun wieder schneidend, haben wir [1,3] [3,5] [5,9] und dasjenige, das übriggeblieben war [9,16,22], jetzt, wo wir dieses Holz bearbeitet haben, haben wir alle geschnitten Noten und die Liste wäre [1,3] [3,5] [5,9] [9,16] [16,22]

for _ in range(int(input())):  #no of test cases 
a,b=map(int,input().split())  #multiplier element of cost ex: 3,4 
n=int(input())     #total number of cuts ex: 6 
x=list(map(int,input().split())) #where the cuts are the wood ex: 
            #[1,3,5,9,16,22] 

lis=[] 
cost=0 

average=sum(x)/len(x) 
median=min(x,key=lambda X:abs(X-average)) #calculated the median 

cost+=a*(median-x[0])+b*(x[-1]-median) #calculated the cost of cutting 
print(cost) 
var=x.index(median)      #found the index of median 
x_left=x[:var+1]       #split the wood in left and right 
x_right=x[var:] 
lis.append(x_right) 
while(len(x_left)>2):  #done the same process going first on left wood  

    average=sum(x_left)/len(x_left) 
    median=min(x_left,key=lambda X:abs(X-average)) 
    cost+=a*(median-x_left[0])+b*(x_left[-1]-median) 
    var=x.index(median) 
    x_left=x_left[:var+1] 
    x_right=x_left[var:] #this wood would again have right component so 
         #stored that right side in list named lis 
    lis.append(x_right) 
print(cost)    #fully solved by moving leftwards 
print(lis) 
tt=len(lis) 
for i in lis:   #but the problem start here i have all the right 
         #pieces of wood that i had stored in lis but now i 
         #can't evaluate them 
    if(len(i)<3): 
     lis.pop(lis.index(i)) 


    else: 
     continue 
print(lis) 
while(tt!=0): 
    xx=lis.pop(0) 
    ttt=len(xx) 
    if(ttt>2): 
     average=sum(xx)/ttt 
     median=min(xx,key=lambda X:abs(X-average)) 
     cost+=a*(median-xx[0])+b*(xx[-1]-median) 
     var=x.index(median) 
     x_left=xx[:var+1] 
     x_right=xx[var:] 
     if(len(x_left)>2): 
      lis.append(x_left) 
     if(len(x_right)>2): 
      lis.append(x_right) 
print(cost) 

Answer 1

Zum einen ist hier eine rekursive Generator solve_gen, die alle möglichen Schnittsequenzen überprüft und wählt dann das Minimum ein. Obwohl der Code kompakt ist und in Ordnung ist, wenn die Anzahl der Markierungen klein ist, wird er bald ziemlich ineffizient, wenn die Anzahl der Markierungen zunimmt. Ich habe auch eine Funktion apply_cuts hinzugefügt, die eine Sequenz von Schnitten auf eine Markierungsreihenfolge anwendet, also können Sie die Schnitte sehen, die in dieser Reihenfolge geschehen.

solve_gen verwendet eine globale count, um die Anzahl der rekursiven Aufrufe zu verfolgen, die gemacht werden. count ist nicht notwendig für den Betrieb des Algorithmus, aber es zeigt uns an, wie viel Arbeit die Funktion macht.

def cost(seq, m): 
    return (seq[-1] - seq[0]) * m 

def solve_gen(seq): 
    global count 
    count += 1 
    if len(seq) == 2: 
     yield 0,() 
     return 
    for i in range(1, len(seq)-1): 
     left, x, right = seq[:i+1], seq[i], seq[i:] 
     val = cost(left, a) + cost(right, b) 
     for lval, lcuts in solve_gen(left): 
      for rval, rcuts in solve_gen(right): 
       yield (val + lval + rval, (x,) + lcuts + rcuts) 

def apply_cuts(seq, cuts): 
    total = 0 
    old = [seq] 
    for x in cuts: 
     new = [] 
     for u in old: 
      if x in u: 
       i = u.index(x) 
       left, right = u[:i+1], u[i:] 
       val = cost(left, a) + cost(right, b) 
       new.extend((left, right)) 
      else: 
       new.append(u) 
     print(x, new, val) 
     total += val 
     old = new[:] 
    return total 

# Test 

# Recursion counter 
count = 0 

a, b = 3, 4 
seq = (1, 3, 5, 9, 16, 22) 
print(seq) 

results = list(solve_gen(seq)) 
val, cuts = min(results) 
print('Cost: {}, Cuts: {}'.format(val, cuts)) 
print('Results length: {}, Count: {}'.format(len(results), count)) 

print('\nCutting sequence') 
print(apply_cuts(seq, cuts)) 

Ausgang

(1, 3, 5, 9, 16, 22) 
Cost: 163, Cuts: (9, 5, 3, 16) 
Results length: 14, Count: 90 

Cutting sequence 
9 [(1, 3, 5, 9), (9, 16, 22)] 76 
5 [(1, 3, 5), (5, 9), (9, 16, 22)] 28 
3 [(1, 3), (3, 5), (5, 9), (9, 16, 22)] 14 
16 [(1, 3), (3, 5), (5, 9), (9, 16), (16, 22)] 45 
163 

FWIW, hier sind die Ergebnisse für die gleiche a & b mit einer längeren Sequenz Marke.

(1, 3, 5, 9, 16, 22, 31, 33, 35, 39, 46) 
Cost: 497, Cuts: (31, 16, 9, 5, 3, 22, 39, 35, 33) 
Results length: 4862, Count: 41990 

---

Wir können effizienter machen dies, indem die Minima auf jeder Stufe der Rekursion zu finden, anstatt das Minimum aller Möglichkeiten zu finden. Da der Algorithmus jedoch die verschiedenen Schneidoptionen untersucht, wiederholt er oft Berechnungen, die zuvor durchgeführt wurden. So können wir den Code durch Verwendung von Caching viel effizienter machen, d. H., Wir speichern frühere Ergebnisse in einem Wörterbuch. Wenn wir also den gleichen Schnitt wieder machen müssen, können wir ihn einfach im Cache nachschlagen, anstatt ihn neu zu berechnen.

Wir könnten unseren eigenen Cache codieren, aber das functools Modul stellt lru_cache zur Verfügung, das als Dekorateur verwendet werden kann. Wir können der cost-Funktion auch einen Cache geben, obwohl ihre Berechnungen ziemlich einfach sind, so dass Caching dort wahrscheinlich nicht viel Zeit spart. Ein nettes Feature von lru_cache ist, dass es auch Cache-Statistiken zur Verfügung stellen kann, die uns wissen lassen, wie nützlich der Cache ist. Zum Glück

from functools import lru_cache 

@lru_cache(None) 
def cost(seq, m): 
    return (seq[-1] - seq[0]) * m 

@lru_cache(None) 
def solve(seq): 
    global count 
    count += 1 
    if len(seq) == 2: 
     return 0,() 
    results = [] 
    for i in range(1, len(seq)-1): 
     left, x, right = seq[:i+1], seq[i], seq[i:] 
     val = cost(left, a) + cost(right, b) 
     lval, lcuts = solve(left) 
     rval, rcuts = solve(right) 
     results.append((val + lval + rval, (x,) + lcuts + rcuts)) 
    return min(results) 

# Test 

# Recursion counter 
count = 0 

a, b = 3, 4 
seq = (1, 3, 5, 9, 16, 22) 
print(seq) 

val, cuts = solve(seq) 
print('Cost: {}, Cuts: {}'.format(val, cuts)) 
print('Count: {}\n'.format(count)) 

print('cost cache', cost.cache_info()) 
print('solve cache', solve.cache_info()) 

Ausgang

(1, 3, 5, 9, 16, 22) 
Cost: 163, Cuts: (9, 5, 3, 16) 
Count: 15 

cost cache CacheInfo(hits=20, misses=20, maxsize=None, currsize=20) 
solve cache CacheInfo(hits=26, misses=15, maxsize=None, currsize=15) 

, erhalten wir die gleichen Ergebnisse wie zuvor. ;) Beachten Sie, dass die Rekursionszahl jetzt viel niedriger ist. Versuchen wir es mit dieser längeren Markenfolge.

(1, 3, 5, 9, 16, 22, 31, 33, 35, 39, 46) 
Cost: 497, Cuts: (31, 16, 9, 5, 3, 22, 39, 35, 33) 
Count: 55 

cost cache CacheInfo(hits=240, misses=90, maxsize=None, currsize=90) 
solve cache CacheInfo(hits=276, misses=55, maxsize=None, currsize=55) 

Die Rekursion zählt nur 55 im Vergleich zum vorherigen 41990; eine deutliche Reduzierung. Und wir können sehen, dass die Caches gut genutzt werden.

---

FWIW, die Zahl aller möglichen Schneidsequenzen durch das Catalan numbers gegeben, die oft in der kombinatorischen Probleme auftauchen.

Answer 2

Diese Frage erfordert Funktionen und Rekursion: und die Kosten für diese Operation würde

hier ist mein Code minimal sein. Was Sie wollen, ist etwas wie das:

function total_cost(a, b, marks): 
    # Do something clever here 

Jetzt haben Sie weniger als 3 Mark, das Problem ist einfach. Keine Schnitte benötigt, und die Kosten sind 0.

function total_cost(a, b, marks): 
    if len(marks) < 3: 
     return 0 
    else 
     # Do something clever here 

Wenn Sie mehr als zwei Marken haben, die Kosten an einem bestimmten Ort des Schneidens sind die Kosten dort schneiden, zuzüglich der Kosten für den Rest des Schneidens. Die Kosten des Schneidens sind daher die minimalen oder die Kosten. Das sollte genug sein, um das Schlaue zu füllen.

Diese Lösung wird langsam mit vielen Schnitten laufen. Um dieses Problem zu lösen, sollten Sie nach "Memoization" suchen.