211service.com
Vienkāršais risinājums
Sēžot tiesas zālē un gaidot, lai uzzinātu, vai viņš tiks izvēlēts žūrijas amatam, Daniels Spīlmans guva atklāsmi — viss darbs, ko viņš un kolēģi Šanhua Tenu bija izveidojuši pēdējo trīs gadu laikā, bija kāršu namiņš. Es nekad neaizmirsīšu, saka Spīlmens, matemātikas asociētais profesors. Kamēr es tur sēdēju un gaidīju - par laimi nē lai tiktu izvēlēts — man bija šī šausmīgā pieredze, kad sapratu, ka viss, ko bijām darījuši, ir nepareizi. Es domāju izmest savu pētniecības programmu. Un tajā mirklī kārtis sabruka.
Pāris bija mēģinājuši atklāt veidu, kā uzlabot simplekso metodi, kas ir viens no pasaulē visplašāk izmantotajiem algoritmiem. Tas ļauj daudzām sarežģītajām sistēmām, kuras mēs uzskatām par pašsaprotamām, piemēram, telekomunikāciju tīkliem un piegādes transportlīdzekļu flotu vai aviokompāniju lidojumu plānošanu, strādāt pēc iespējas efektīvāk un lētāk. Kā jauns docents Spīlmans vēlējās nostiprināties matemātikas pasaulē un iegūt pilnvaras MIT, strādājot pie liela izaicinājuma, proti, padarot algoritmu vienkāršāku, ātrāku un labāku. Taču pēc šīs dienas tiesas namā, kad viņš saprata, ka nesaistītas jomas jēdzienu pielietošana vienkāršā algoritmā ir strupceļš, viņš zināja, ka, lai sasniegtu savus mērķus, būs jāatrod vēl viens liels izrāviens.
Dažas dienas vēlāk, tāpat kā cilvēks, kura māju iznīcināja viesuļvētra vai viesuļvētra, Spīlmens sāka glābt to, kas bija palicis pāri no viņa pētījumu drupām. Un tas bija tad, kad nāca patiešām lielā ideja: lai gan viņa darbs nevarēja uzlabot simplekso metodi, iespējams, to varēja izskaidro to . Metode tika izstrādāta 1947. gadā, bet pēc vairāk nekā 50 gadu analīzes neviens nevarēja saprast, kāpēc tā strādāja. Spīlmana nojauta izrādījās pareiza. Pēc vēl trīs gadu sadarbības un simtiem matemātisko formulu viņš un Bostonas universitātes profesors Tengs tagad var izskaidrot, kāpēc darbojas simpleksa metode. Tas var ļaut tā sauktajiem optimizācijas ekspertiem atrisināt vēl sarežģītākas organizatoriskas problēmas. Nacionālais zinātnes fonds jau ir minējis skaidrojumu, ko sauc par izlīdzināto analīzi, kā lielu informācijas tehnoloģiju sasniegumu.
Ceļš uz atklājumiem
Spīlmans un Tens pirmo reizi tikās 1990. gada rudenī, kad Spīlmans, tobrīd Jēlas universitātes bakalaura students, apmeklēja Kārnegija Melona universitāti, lai teiktu runu. Tengs, doktora grāda kandidāts, stāsta, ka viņš un citi universitātes darbinieki apbrīnojuši šo garmataino koledžas jaunāko kursu. Viņam jau bija divi doktora kvalitātes darbi. Protams, viņš bija viens no visaugstāk novērtētajiem topošajiem studentiem, ko visas labākās universitātes vēlējās piesaistīt savām doktorantūras programmām. 1992. gadā Spīlmens izvēlējās MIT. Tengs ieradās tajā pašā gadā kā instruktors institūtā. Viņu studentu un skolotāju attiecības drīz vien kļuva par draudzību un pēc tam par sadarbību, kas ilga 11 gadus.
1996. gadā pēc vairākiem gadiem kopā strādājot citā jomā, duets sāka censties uzlabot simplekso metodi. Pētniecības process ir līdzīgs mēģinājumam ar nelielu lukturīti atrast dārgumus uz tumšas salas, saka Tens. Mēs centāmies izpētīt šīs daudzās cerīgās iespējas. Dens vienmēr glabā detalizētus darba žurnālus, kuros sistemātiski tiek atzīmētas izpētes kartes.
Pēc trīs gadu ilga šāda darba Spīlmans tika realizēts tiesas zālē. Abi matemātiķi mainīja savu mērķi un nopietni uzbruka jaunajai pētniecības problēmai.
Tengs, kurš līdz tam bija asociētais profesors Ilinoisas Universitātē Urbana-Champaign, sabata laikā pārcēlās atpakaļ uz Masačūsetsu un īrēja dzīvokli piecu minūšu attālumā no Spīlmana. Pēc tam abi pētnieki savas dzīvojamās istabas pārvērta par darba telpām. Tengs pie savas dzīvojamās istabas sienas uzstādīja lielu tāfeli. Spīlmens vienu glabāja aiz dīvāna.
Kopš tā laika viņu kopīgais darbs notika visu laiku. Tā bija viena no lietām, kur mana sieva sūdzējās, ka dažus gadus es redzēju Šanhua vairāk nekā viņu, stāsta Spīlmens. Tens strādāja pilnu slodzi Akamai Kembridžā, bet gandrīz katru vakaru pēc darba un brīvdienās devās uz Spīlmena dzīvokli. Mēs strādājām daudzas stundas, iespējams, līdz diviem, atzīmē Spīlmens. Tengs piebilst, ka es biju kā adoptēts Dena ģimenes loceklis. Pat viņu kaķene Hloja bija tik ļoti pieradusi pie mūsu klātbūtnes, ka viņa sēdēja pie tāfeles un uzmanīgi vēroja, kad mēs to uzstādām. Pētnieki pateicās Hlojai savā žurnāla rakstā.
Lai izsekotu viņu darbam, Spīlmens turpināja savus darba žurnālus, pierakstot katru tāfelēs esošo domu un vienādojumu pirms to izdzēšanas. Šobrīd viņa 2. būves biroja grāmatplauktā atrodas ducis šādu 200 lappušu garu, piezīmju grāmatiņas izmēra žurnālu. Viņš saka, ka aptuveni 60 procenti informācijas, ko satur žurnāli, ir darbs pie gludas analīzes. Tikmēr Tengs izmantoja digitālo kameru, lai uzņemtu aptuveni 40 tāfeles fotoattēlus, pirms tās tika izdzēstas.
Beidzot Atbildot Kāpēc
Visa šī pētījuma rezultāts bija atbilde uz vienkāršo jautājumu Kāpēc? Spīlmens un Tens beidzot saprata, kāpēc vienkāršā metode visu šo laiku ir tik labi darbojusies. Viņi to izdarīja, izstrādājot jaunu algoritma analīzes veidu.
Līdz to atklāšanai lielākā daļa matemātiķu mērīja algoritmus, izmantojot sliktākā gadījuma analīzi, kurā algoritmam tiek doti vissarežģītākie dati un pēc tam tiek novērtēts, cik labi tas var aprēķināt ar to. Tas būtu tā, it kā kāds jums sniegtu vissliktāko iespējamo garās dalīšanas problēmu, kādu jūs varētu iedomāties, un pēc tam pārbaudītu, vai jūs varat to atrisināt un cik ilgi tas prasīs. Bet tas vienkārši nedarbojās ar simpleksa metodi.
Tāpēc Spīlmens un Tens atrada jaunu pieeju. Viņi ieviesa zināmas atšķirības sliktākā gadījuma analīzē. Tā vietā, lai izmantotu precīzus skaitļus kā ievadi, lai pārbaudītu algoritmu, tie pieļāva neprecizitāti. Piemēram, ja ievade bija 1,31, tika atļauta nejauša ievade no 1,29 līdz 1,33. Viņi atklāja, ka, pieļaujot neprecizitāti, simpleksais algoritms vienmēr efektīvi atrisināja problēmu, un tāpēc tas ir bijis tik veiksmīgs.
Ideja izklausās vienkārša, bet matemātika, kas to atbalsta, ir sarežģīta. Spīlmana un Tenga pirmais žurnāla raksts par šo tēmu, ko tagad pārskata Datortehnikas asociācija ACM žurnāls , satur 80 vienādojumu lapas. Es nezinu, vai tik daudz cilvēku varētu iziet cauri papīram, saka Spīlmens. Faktiski darba rakstīšana dažkārt pat mulsināja Spīlmanu un Tenu. Pāris reizes mēs vienkārši izmetām uzrakstīto un uzrakstījām no jauna, jo, ja mums tas bija sarežģīti, [citiem] cilvēkiem tas būs vēl sarežģītāk, saka Spīlmens.
Spīlmans un Tens ir iepazīstinājuši ar saviem atklājumiem visā pasaulē, lai saņemtu entuziasmu. Viņi publicēja konferences rakstu 2001. gadā, un kopš tā laika abi ir uzstājušies ar uzaicinātām prezentācijām un galvenajām uzrunām visā ASV un Ķīnā, Turcijā, Itālijā, Šveicē un Dānijā.
Šī izlīdzinātā analīze ir svarīga attīstība, saka Michel Goemans, PhD ‘90, MIT lietišķās matemātikas profesors. Un Deivids Džonsons, AT&T Labs-Research Algoritmu un optimizācijas nodaļas vadītājs, saka: [Izlīdzinātā analīze] nodrošina papildu pārliecības līmeni tiem, kas izmanto simplekso metodi.
Spīlmens saka, ka viņš nav izvilcis savu tāfeli kopš pagājušās vasaras, kad žurnāla papīrs beidzot bija pabeigts, taču bez tā mēs nekad nebūtu paspējuši uzrakstīt darbu. Tagad Spīlmans iesaka jaunajiem pētniekiem iegādāties lielas tāfeles, kas ir labs pirmais solis ceļā uz izrāvienu. Tomēr Tengs lielu daļu viņu panākumu saista ar Spīlmena dinamisko prātu un lielisko gaumi pētniecības problēmu izvēlē. Viņam vienmēr ir drosme strādāt pie vissmagākās atklātās problēmas šajā jomā, saka Tengs, un tas varētu būt vēl labāks sākumpunkts pētniekiem un zinātkārajiem cilvēkiem visur.