PREV INDEX NEXT

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