Mietiskelen tässä korintäyttöä (bin packing) ja sitä, miten ahne menetelmä on joko ylipolynomiaalinen tai sitten epäoptimaalinen. Luultavasti se on vain liian epätehokas algoritmi.

Korintäyttö

Olkoon meillä joukko lukuja väliltä . Kysymys kuuluu, kuinka moneen (yhden suuruiseen) koriin nämä luvut voidaan pienimmillään asettaa.

Tämä ongelma on todistetusti NP-täydellinen, eli aika vaikea tehtävä. Ahneella ratkaisumenetelmällä ongelmaan saadaan hyvin simppeli ratkaisu, mutta se joko tuottaa epäoptimaalisia ratkaisuja tai sitten sen aikavaativuus on eksponentiaalinen. Jotenkin kuulostaisi siltä, että se on hitaampi kuin miltä näyttää.

Ahne algoritmi

Otetaan kasasta lukuja suuruusjärjestyksessä pois, isoimmasta alkaen. Pannaan se simppelisti ensimmäiseen koriin , johon se mahtuu. Jos ei mahdu mihinkään entisistä koreista, niin otetaan uusi, tyhjä kori. Kun alkuperäinen kasa on tyhjentynyt, niin katsotaan korien lukumäärä. Toki totuusarvo-ongelmana (riittääkö koria?) meille riittää lopettaa tarkastelu siihen paikkaan, jos kori numero pitäisi ottaa käyttöön. Huonoin tapaus johtaa kaikkien tarkasteluun.

Ääritapauksessa oletetaan, että kaikki alkiot ovat lukuja , (tai yleisemmin kaikki alkiot lukuja , eli yhteen koriin ei mitenkään mahdu yhtä alkiota enempää. Olkoon näitä lukuja kappaletta. Algoritmi ottaa suurimman, eli alkion kasasta ja valitsee ensimmäisen vapaan korin sille. Toista alkiota valittaessa havaitaan, ettei alkio mahdu ensimmäiseen koriin, koska siten. Induktiolla voitaisiin havaita, että tällä tavalla kappaletta lukuja voidaan täyttää vain koriin, ja että siihen menee askelta, koska vapaita koreja aina aloitetaan tarkastelemaan alusta. Tämähän olisi .

Ja jos luvut ovat niin pieniä, että ne kaikki mahtuvat yhteen koriin, niin algoritmi ajaa lineaarisessa ajassa . Melkein uskaltaisin väittää, että yleinen aikavaativuus on , missä on lukujen lukumäärä ja on lopullinen korien lukumäärä.

Eli tuskinpa on aikavaativuudesta kiinni. Millä ihmeen tavalla tämä ei ole optimaalinen? Vai teinkö virheellisen oikaisun aikavaativuustarkastelussa? Kenties kumpikaan käsittelemistäni tapauksista ei oikeasti ole ajankäytöllisesti pahin tapaus.

Ei optimaalinen

No niin. Sitten uteliaisuus voitti ja menin katsomaan wikipediasta. Esittelemäni algoritmi on nopeampi kuin , mutta ei todellakaan aina optimaalinen. Esittelemäni lajiteltu syöte; keksitään vastaesimerkki. Mutta jopa on vaikea keksiä! Wikipedian artikkelissa esitetään ihan fiksu esitys, että menetelmä ei ole optimaalinen, koska useampien korien ei anneta olla puolityhjiä samanaikaisesti. Helpompi olisi kai löytää vastaesimerkki, jolla epäoptimaalisuus todettaisiin.

Pythonillahan on helppo kirjoittaa tämä ahne algoritmi:

def binpack(items):
  bins = []
  for x in sorted(items):
    for b in bins:
      if sum(b) + x < 1:
        b.append(x)
        break
    else:
      bins.append([x])
  return bins

Harmi vain, että liukulukuaritmetiikka antaa hankaluuksia.
Jos rajoitun kokonaislukuakselille 1..1000, (voidaan ajatella siis liukulukuina 0.001…1.000) niin jännää kyllä, en kykene edes python-ohjelmani avulla löytämään vastaesimerkkiä. Wikipediakin sanoo, että lajitellussa syötteessä tämä ahne approksimointi (nimeltään first fit decreasing order) on erityisen tehokas.

Testiohjelmani hakee vastaesimerkkejä ensin ajamalla approksimoinnin ja sitten optimaalisen. Koska luonnollisesti optimaalinen malli on ylipolynomaalinen, niin kovin isoilla syötteillä ei enää kykene etsimään.

Tässä on esitettynä kokonaisluvuille toimiva algoritmi sekä testiohjelmat:

def binpack_greedy(items):
  bins = []
  for x in items:
    for b in bins:
      if sum(b) + x <= 1000:
        b.append(x)
        break
    else:
      bins.append([x])
  return bins

def binpack_greedy_decr(items):
  "Very powerful variation of the first fit algorithm."
  return binpack_greedy(sorted(items, reverse=True))

def binpack_optimal(items):          
  """Return the optimal number of bins needed. We'll use nonsorted greedy
  algorithm with all possible permutations so the complexity is O(n!)"""
  import itertools

  best_solution = []
  best_size = len(items) + 1 

  for perm in itertools.permutations(items):
    solution = binpack_greedy(perm)
    size = len(solution)
    if size < best_size:
      best_solution = solution
      best_size = size

  return best_solution

##### tests
import random
def randomlist(size):
  l = []
  while size > 0:
    n = random.randint(1, 1000)
    l.append(n)
    size -= 1
  return l

def try_to_find_out(times, number = 5):
  "let's try to find a counterexample"
  for _ in range(times):
    foo = randomlist(number)
    greedy = len(binpack_greedy_decr(foo))
    optimal = len(binpack_optimal(foo))
    if greedy != optimal:
      print "input", sorted(foo, reverse=True)
      print "optimal", binpack_optimal(foo)
      print "greedy ", binpack_greedy_decr(foo)
      break           

Ja mitään tuloksia en ole löytänyt. Kunnes sitten kymmentä minuuttia myöhemmin.

Vastaesimerkki

Vaihdoin syötteet takaisin liukuluvuiksi ja ajelin epätoivoissani sarjoja sisään. Python-tulkki antoi kuin antoikin sopivat syötteet. Ellen väärin ajatellut asiaa, niin tulos vaikuttaa seuraavan ihan aidoista lähtökohdista, ei esimerkiksi liukulukulaskennan epätarkkuuksista (voi syntyä virheellisiä summauksia tjsp):

>>> try_to_find_out(100, 6)
input [0.44604504320199823,
       0.39084470840484253,
       0.36302114260833085,
       0.29242927571305433,
       0.24068549251130467,
       0.21981144650723328]
optimal [[0.39084470840484253,      # kaksi koria
          0.21981144650723328,
          0.36302114260833085],
         [0.44604504320199823,
          0.29242927571305433,
          0.24068549251130467]]
greedy [[0.44604504320199823,       # kolme koria
         0.39084470840484253],
        [0.36302114260833085,
         0.29242927571305433,
         0.24068549251130467],
        [0.21981144650723328]]
>>> ce                              # counter example, sama kuin yo. `input`
[0.44604504320199823,
 0.39084470840484253,
 0.36302114260833085,
 0.29242927571305433,
 0.24068549251130467,
 0.21981144650723328]
>>> sum(ce)                         # katsellaan korien summat
1.9528371089467642
>>> map(sum, binpack_greedy_decr(ce))  # ahne
[0.83688975160684076,
 0.89613591083268984,
 0.21981144650723328]
>>> map(sum, binpack_optimal(ce))   # optimaalinen
[0.97915981142635722,
 0.97367729752040666]

Jooh. Huomenna on aiheesta tentti. Toivottavasti tämä korvasi nyt pänttäilyn riittävän hyvin.