Versioni origjinal nga kjo histori u shfaq në Sa revistë.
Shkencëtarët e kompjuterave shpesh merren me probleme abstrakte që vështirë të kuptohen, por një algoritëm i ri emocionues ka rëndësi për këdo që zotëron libra dhe të paktën një raft. Algoritmi adreson diçka që quhet problem i klasifikimit të bibliotekës (më zyrtarisht, problemi “etiketimi i listës”). Sfida është të krijoni një strategji për organizimin e librave në një lloj rendi të renditur – alfabetikisht, për shembull – kjo minimizon sa kohë duhet për të vendosur një libër të ri në raft.
Imagjinoni, për shembull, që i mbani librat tuaj të grumbulluar së bashku, duke lënë hapësirë boshe në të djathtën e djathtë të raftit. Atëherë, nëse shtoni një libër nga Isabel Allende në koleksionin tuaj, mund të duhet të lëvizni çdo libër në raft për të bërë vend për të. Ky do të ishte një operacion që kërkon kohë. Dhe nëse atëherë merrni një libër nga Douglas Adams, do të duhet ta bëni përsëri. Një aranzhim më i mirë do të linte hapësira të pakujdesshme të shpërndara në të gjithë raftin – por si, saktësisht, a duhet të shpërndahen?
Ky problem u prezantua në një Gazeta 1981Dhe shkon përtej thjesht sigurimit të bibliotekarëve udhëzime organizative. Kjo për shkak se problemi vlen edhe për rregullimin e skedarëve në disqet e vështirë dhe në bazat e të dhënave, ku artikujt që do të organizohen mund të numërohen në miliarda. Një sistem joefikas nënkupton kohë të konsiderueshme të pritjes dhe shpenzime kryesore llogaritëse. Studiuesit kanë shpikur disa metoda efikase për ruajtjen e sendeve, por ata kanë kohë që kanë dashur të përcaktojnë mënyrën më të mirë të mundshme.
Vitin e kaluar, në një studim Kjo u prezantua në Themelet e Konferencës së Shkencave Kompjuterike në agoikago, një ekip prej shtatë studiuesish përshkruan një mënyrë për të organizuar artikuj që i afrohen në mënyrë tantalizuese idealit teorik. Qasja e re kombinon një njohuri të vogël për përmbajtjen e kaluar të raftit të librave me fuqinë befasuese të rastësisë.
“Ashtë një problem shumë i rëndësishëm,” tha Seth PettieNjë shkencëtar i kompjuterave në Universitetin e Miçiganit, sepse shumë nga strukturat e të dhënave ne mbështetemi në informacionin e dyqanit sot në mënyrë sekuenciale. Ai e quajti punën e re “jashtëzakonisht të frymëzuar [and] Lehtësisht një nga tre letrat e mia të preferuara të vitit. “
Ngushtimi i kufijve
Pra, si e mat një raft librash të rregulluar mirë? Një mënyrë e zakonshme është të shihni se sa kohë duhet për të futur një artikull individual. Natyrisht, kjo varet nga sa artikuj ka në radhë të parë, një vlerë që zakonisht tregohet nga nen. Në shembullin Isabel Allende, kur të gjithë librat duhet të lëvizin për të akomoduar një të ri, koha që duhet është proporcionale me nen. Sa më e madhe nenSa më gjatë të duhet. Kjo e bën këtë një “kufi të sipërm” për problemin: kurrë nuk do të zgjasë më shumë sesa një kohë proporcionale me nen Për të shtuar një libër në raft.
Autorët e punimit të vitit 1981 që përdorën në këtë problem donin të dinin nëse ishte e mundur të hartohej një algoritëm me një kohë mesatare të futjes shumë më pak se nen. Dhe me të vërtetë, ata vërtetuan se dikush mund të bënte më mirë. Ata krijuan një algoritëm që ishte i garantuar për të arritur një kohë mesatare të futjes proporcionale me (log nen)))2. Ky algoritëm kishte dy prona: ishte “përcaktuese”, që do të thotë se vendimet e tij nuk vareshin nga ndonjë rastësi, dhe ishte gjithashtu “i qetë”, që do të thotë se librat duhet të përhapen në mënyrë të barabartë brenda nënseksioneve të raftit ku futjet (ose fshirjet) janë bërë. Autorët lanë të hapur pyetjen nëse kufiri i sipërm mund të përmirësohej edhe më tej. Për më shumë se katër dekada, askush nuk arriti ta bëjë këtë.
Sidoqoftë, vitet e ndërhyrjes panë përmirësime në kufirin më të ulët. Ndërsa kufiri i sipërm specifikon kohën maksimale të mundshme të nevojshme për të futur një libër, kufiri i poshtëm jep kohën më të shpejtë të mundshme të futjes. Për të gjetur një zgjidhje përfundimtare për një problem, studiuesit përpiqen të ngushtojnë hendekun midis kufijve të sipërm dhe të poshtëm, në mënyrë ideale derisa të përkojnë. Kur kjo të ndodhë, algoritmi vlerësohet optimal – i kufizuar në mënyrë të paanshme nga lart dhe poshtë, duke mos lënë vend për përsosje të mëtejshme.
