211service.com
Paprastas sprendimas
Sėdėdamas teismo salėje ir laukdamas, ar jis bus išrinktas prisiekusiųjų pareigoms, Danielis Spielmanas patyrė apreiškimą – visas darbas, kurį jis ir kolega Shanghua Tengas sukūrė per pastaruosius trejus metus, buvo kortų namelis. Aš niekada nepamiršiu, sako Spielmanas, matematikos docentas. Kai sėdėjau ir laukiau – laimei ne būti išrinktam – patyriau siaubingą patirtį, kai supratau, kad viskas, ką darėme, buvo neteisinga. Sugalvojau išmesti savo tyrimų programą. Ir tą akimirką kortelės subyrėjo.
Pora bandė atrasti būdą, kaip patobulinti simplekso metodą, vieną iš plačiausiai naudojamų algoritmų pasaulyje. Tai leidžia daugeliui sudėtingų sistemų, kurias laikome savaime suprantamomis, pavyzdžiui, telekomunikacijų tinklais ir pristatymo transporto priemonių parko ar oro linijų skrydžių planavimu, dirbti kuo efektyviau ir nebrangiai. Kaip naujasis docentas, Spielmanas norėjo įsitvirtinti matematikos pasaulyje ir įgyti darbo MIT, dirbdamas su dideliu iššūkiu, būtent, paprastesnį, greitesnį ir geresnį algoritmą. Tačiau po tos dienos teismo rūmuose, kai jis suprato, kad nesusijusios srities sąvokų taikymas simpleksiniam algoritmui yra aklavietė, jis suprato, kad norėdamas pasiekti savo tikslus turės rasti dar vieną didelį proveržį.
Po kelių dienų, kaip žmogus, kurio namus sugriovė uraganas ar tornadas, Spielmanas pradėjo gelbėti tai, kas liko po jo tyrimų griuvėsių. Ir tada šovė tikrai didelė idėja: nors jo darbas negalėjo patobulinti simplekso metodo, galbūt jis galėjo paaiškinti tai . Metodas buvo sukurtas 1947 m., tačiau po daugiau nei 50 metų analizės niekas negalėjo suprasti, kodėl jis veikė. Spielmano nuojauta pasirodė teisinga. Po dar trejų metų bendro darbo ir šimtų matematinių formulių jis ir Bostono universiteto profesorius Tengas dabar gali paaiškinti, kodėl veikia simplekso metodas. Tai gali leisti vadinamiesiems optimizavimo ekspertams išspręsti dar sudėtingesnes organizacines problemas. Nacionalinis mokslo fondas jau įvardijo paaiškinimą, vadinamą išlyginta analize, kaip didelį informacinių technologijų pažangą.
Kelias į atradimą
Spielmanas ir Tengas pirmą kartą susitiko 1990 m. rudenį, kai Spielmanas, tuometinis Jeilio universiteto bakalauras, apsilankė Carnegie Mellon universitete ir pasakė kalbą. Tengas, doktorantas, sako, kad jis ir kiti universiteto darbuotojai žavėjosi šiuo ilgaplaukiu koledžo jaunesniuoju. Jis jau turėjo du doktorantūros kokybės darbus. Žinoma, jis buvo vienas iš labiausiai vertinamų būsimų studentų, kuriuos visi geriausi universitetai norėjo pritraukti į savo doktorantūros programas. 1992 m. Spielmanas pasirinko MIT. Tengas tais pačiais metais atvyko į institutą instruktoriumi. Jų studentų ir mokytojų santykiai netrukus tapo draugyste, o vėliau – 11 metų trukusiu bendradarbiavimu.
1996 m., po kelerių metų bendro darbo kitoje srityje, duetas pradėjo siekti patobulinti simplekso metodą. Tyrinėjimo procesas labai panašus į bandymą tamsioje saloje su mažu žibintuvėliu rasti lobį, sako Tengas. Mes bandėme ištirti tuos daugybę viltingų patarimų. Danas visada veda išsamius darbo žurnalus, kuriuose sistemingai žymimi žvalgymo žemėlapiai.
Po trejų tokio darbo metų Spielmanas suprato teismo salę. Du matematikai pakeitė savo tikslą ir rimtai ėmėsi naujos tyrimo problemos.
Tengas, kuris tuo metu buvo Ilinojaus universiteto Urbana-Champaign docentas, grįžo į Masačusetsą per atostogas ir išsinuomojo butą penkias minutes nuo Spielman's. Po to abu mokslininkai savo svetaines pavertė darbo erdvėmis. Tengas ant savo svetainės sienos pritvirtino didelę lentą. Spielmanas laikė vieną už savo sofos.
Nuo tada jų bendras darbas vyko visą valandą. Tai buvo vienas iš tų dalykų, kai mano žmona skundėsi, kad keletą metų daugiau mačiau Šanhua, nei mačiau ją, sako Spielmanas. Tengas dirbo visą darbo dieną Akamai Kembridže, bet beveik kiekvieną vakarą po darbo ir savaitgaliais eidavo į Spielmano butą. Mes nemiegodavome daug valandų, tikriausiai iki dviejų, dirbdami, pažymi Spielmanas. Tengas priduria, kad buvau kaip įvaikintas Dano šeimos narys. Net jų katė Chloe taip priprato prie mūsų buvimo, kad tupėdavo priešais lentą ir atidžiai stebėdavo, kai ją pastatydavome. Tyrėjai padėkojo Chloe savo žurnalo dokumente.
Norėdamas sekti jų darbą, Spielmanas tęsė savo darbo žurnalus, prieš ištrindamas lentas užrašydamas kiekvieną mintį ir lygtį. Šiandien tuzinas šių 200 puslapių užrašų knygelės dydžio žurnalų rikiuojasi jo 2 pastato biuro knygų lentynoje. Jis sako, kad apie 60 procentų informacijos, esančios žurnaluose, sudaro sklandi analizė. Tuo tarpu Tengas skaitmeniniu fotoaparatu padarė apie 40 lentų nuotraukų, kol jos buvo ištrintos.
Pagaliau atsakymas Kodėl
Viso šio tyrimo rezultatas buvo atsakymas į paprastą klausimą Kodėl? Spielmanas ir Tengas pagaliau išsiaiškino, kodėl simplekso metodas taip gerai veikė visą šį laiką. Jie tai padarė kurdami naują algoritmo analizės būdą.
Iki jų atradimo dauguma matematikų matavo algoritmus taikydami blogiausio atvejo analizę, kai algoritmui pateikiami sunkiausi duomenys, o tada vertinama, kaip gerai jis gali su jais apskaičiuoti. Tai būtų taip, tarsi kas nors pateiktų jums blogiausią įmanomą ilgo padalijimo problemą, kurią galite įsivaizduoti, o tada patikrintų, ar galite ją išspręsti ir kiek tai užtruks. Bet tai tiesiog neveikė naudojant simplekso metodą.
Taigi Spielmanas ir Tengas rado naują požiūrį. Jie įvedė tam tikrą kintamumą blogiausio atvejo analizėje. Užuot naudoję tikslius skaičius kaip įvestis algoritmui išbandyti, jie leido netikslumą. Pavyzdžiui, jei įvestis buvo 1,31, jie leido atsitiktinai įvesti nuo 1,29 iki 1,33. Jie išsiaiškino, kad sutikdamas netikslumą, simplekso algoritmas visada veiksmingai išspręsdavo problemą, todėl jis buvo toks sėkmingas.
Idėja skamba paprasta, tačiau ją palaikanti matematika yra sudėtinga. Spielmano ir Tengo pirmasis žurnalo straipsnis šia tema, kurį dabar peržiūri Kompiuterinių mašinų asociacija ACM žurnalas , yra 80 puslapių lygčių. Nežinau, ar tiek daug žmonių galėtų vaikščioti per popierių, sako Spielmanas. Tiesą sakant, referato rašymas kartais net supainiodavo Spielmaną ir Tengą. Porą kartų mes tiesiog išmetėme tai, kas buvo parašyta, ir parašėme iš naujo, nes jei mums tai buvo sudėtinga, [kitiems] žmonėms bus dar sudėtingiau, sako Spielmanas.
Spielmanas ir Tengas entuziastingai pristatė savo atradimus visame pasaulyje. Jie paskelbė konferencijos pranešimą 2001 m. ir nuo tada abu skaitė pranešimus ir pagrindinius pranešimus Jungtinėse Valstijose ir Kinijoje, Turkijoje, Italijoje, Šveicarijoje ir Danijoje.
Ši išlyginta analizė yra svarbus pokytis, sako Michelis Goemansas, 90 m. daktaras, MIT taikomosios matematikos profesorius. O Davidas Johnsonas, AT&T Labs-Research Algoritmų ir optimizavimo skyriaus vadovas, sako: [Smooted analizė] suteikia papildomo pasitikėjimo tiems, kurie naudoja simplekso metodą.
Spielmanas sako, kad jis neištraukė lentos nuo praėjusios vasaros, kai žurnalo popierius pagaliau buvo baigtas, bet be jo niekada nebūtume spėję parašyti popieriaus. Dabar Spielman rekomenduoja jauniems tyrėjams įsigyti dideles lentas, nes tai yra geras pirmasis žingsnis siekiant laimėjimų. Tačiau Tengas didelę jų sėkmės dalį sieja su dinamišku Spielmano protu ir puikiu skoniu renkantis tyrimo problemas. Tengas sako, kad jis visada turi drąsos dirbti su sunkiausia atvira problema šioje srityje, ir tai gali būti dar geresnis atspirties taškas tyrinėtojams ir smalsiems žmonėms visur.