Author: Stan Eisenstat
Subject: Re: [Cs223] Strategies for reducing time for backtracking
Date: Friday, 14 Feb 2020, 07:57:34
> Message Posted By: AH > > My time is always around 4-5 with Heuristic E. It seems all the previous > Heuristics passed. > > Are there any suggestions for making the program more efficient? Not without knowing more about how your code works. However, you might find the following posting of use: Subject: Why Binpack does twice as many backtracks I added some print statements to your bp() and ran a very simple example: % ./Binpack 13 9 5 5 3 2 2 -opt Add item[0] = 9 to bin #0 1 Add item[1] = 5 to bin #1 2 Add item[2] = 5 to bin #1 3 Add item[3] = 3 to bin #0 4 Add item[4] = 2 to bin #1 5 Add item[5] = 2 to bin #2 6 Remove item[5] = 2 from bin #2 7 Remove item[4] = 2 from bin #1 8 Add item[4] = 2 to bin #2 9 Remove item[4] = 2 from bin #2 10 Remove item[3] = 3 from bin #0 11 Add item[3] = 3 to bin #1 12 Add item[4] = 2 to bin #0 13 Add item[5] = 2 to bin #0 14 (the line numbers were added later for reference). Note that bp() finds a complete assignment using 3 bins after Line #6. But in Line #9 it assigns Item #4 to Bin #2 (a third bin), which Heuristic C should prevent. This may explain why bp() does twice as many backtracks as Hwk2/Binpack. --Stan-PREV INDEX NEXT