[SCRÂȘIT] [FOȘTIT] [CLIC] JUSTIN SOLOMON: Ei bine, bine ați venit la sesiunea cu probleme 5 din 6.006. Este o plăcere să văd astăzi toate fețele voastre zâmbitoare aici. Săptămâna aceasta, vom acoperi câteva probleme din teoria graficelor legate de căutarea depth-first și breadth-first search, care au fost aproximativ subiectele pe care cred că le-am abordat în ultimele două prelegeri și ce va fi pe dvs. teme pentru acasă. Și cred că aceasta este în principiu temele de anul trecut, cu câteva revizuiri, bazate pe niște greșeli de scriere pe care le-am prins. Ah, și am prins o greșeală de ortografie despre care voi deranja instructorul nostru mai târziu. BINE. Așa că, fără alte prelungiri, să începem. Bănuiesc că le vom face doar pentru lipsă de creativitate aici. Prima problemă are de-a face cu unele măsurători pe un grafic, care este de fapt una cu adevărat interesantă pentru mine. Deci, se dovedește că într- o mulțime de cercetări în... dintr-un motiv oarecare, în informatică, există cercetarea în teoria graficelor și apoi este cercetarea rețelelor. Și acestea sunt două comunități diferite din motive istorice ciudate pe care nu le înțeleg în totalitate. Dar oamenii din literatura de știință a rețelelor măsoară adesea lucruri precum raza graficului și alte tipuri de măsuri care încearcă să vă spună ceva despre, cum ar fi, un grafic este un lucru lung, întins, cum ar fi un grafic linie sau ceva super compact, ca o stea? Și așa mai departe. Și astfel, această problemă este un fel de săpa în aspectele algoritmice ale modului în care am putea calcula una dintre măsurătorile care cred că este destul de comună în acea comunitate. Deci haideți să trecem prin aceste probleme. Ca de obicei, în 6.006, ne place să luăm probleme de calcul relativ simple și apoi să le îmbrăcăm cu o mulțime de limbaj pentru a face să fie enervant să analizați. Și într-adevăr, această problemă nu face excepție de la asta. Deci, în această problemă, ni se oferă un grafic nedirecționat. Și, ca de obicei, îl vom numi G. Și definim un anumit număr pe care încercăm să-l măsurăm în această problemă, nu? Deci, în special, dacă ni se dă un vârf v, atunci putem defini ceva numit excentricitatea lui v, care este distanța până la lucrul cel mai îndepărtat. Deci, în special, putem defini-- va fi dat de următoarele, care este maximul peste tot posibilul-- Voi încerca să mă asigur că notația mea-- hopa, am deja-- Ei bine, asta este OK-- peste toate celelalte vârfuri ale distanței de la v la w. Așa că stau într- un punct al unui grafic. Și acum îmi place să fac un zgomot puternic. Și ultima persoană care m-a auzit , distanța până la el ar fi excentricitatea acelui vârf. Și deci acesta este un fel de noțiune de rază sau diametru, dar un fel de plantat într-un punct. Și apoi, dacă vrem să învățăm o proprietate nu a unui vârf, ci a întregului graf, un lucru pe care îl putem face este să definim raza. Și care este dat de R din G este min peste toate vârfurile diferite, u, ale excentricității lui u. OK, deci cred că aceasta este una dintre aceste definiții la care este cu adevărat enervant de analizat și de gândit. Așa că ar trebui să desenăm puțin o schemă și să vedem ce se întâmplă aici, pentru că mai ales ca profesor de geometrie, aceasta este cam drăguță, pentru că se traduce direct în ceea ce ați putea face în geometria metrică. Deci, să spunem că am un cerc aici. Și vreau cel mai complicat mod din lume de a-și defini raza. Deci, pentru orice punct dat, există un punct într-un cerc. Acesta este un cerc, în caz că te întrebi. Știi acele concursuri pe internet în care au oameni care pur și simplu merg la tablă, desenează cercuri perfecte și apoi pleacă? Din pacate nu sunt un expert in aceasta problema. Dar oricum, deci, dacă ne gândim la un punct - ca un cerc ca la un analog al graficului nostru, și apoi desenez un punct, care ar putea fi analogul unui vârf, atunci care este excentricitatea? Ei bine, este distanța până la punctul cel mai îndepărtat, nu? Deci, pentru acest tip, ar putea fi lungimea acestei linii, aproximativ, pentru că aceasta este distanța până la lucrul cel mai îndepărtat. Deci, pentru fiecare punct diferit pe care îl desenez, fiecare punct are propriul punct cel mai îndepărtat din cerc. Deci, există un număr pozitiv care este atribuit fiecărui punct din acest domeniu. Și dacă iau minimul acelui număr pozitiv, unde crezi că ajung? PUBLIC: Centrul cercului. JUSTIN SOLOMON: Așa este, Jason. Ajung în centrul cercului, pentru că dacă mă gândesc bine , distanța până la punctul cel mai îndepărtat din acest domeniu, un lucru pe care te poți convinge este că este cât se poate de mică. Deci, aceasta este ceea ce am putea numi o problemă min-max în optimizare, pentru că minimizăm distanța maximă, da? Acest lucru apare și în teoria jocurilor, tot felul de locuri diferite care rezolvă aceste lucruri. Dar, din fericire, în această problemă specială, nu vom avea nevoie de toate acestea. OK, deci corect. Așadar, această problemă a temei are două părți. Primul este de a da un algoritm pentru calcularea razei unui grafic. Și apoi al doilea este de a da un algoritm pentru aproximarea razei graficului foarte rapid, sau mai rapid decât prima parte. De fapt, nu știu dacă există o limită inferioară acolo. Dar revino la asta mai târziu. OK, deci în partea a, ni se dă G. Și, în plus, ni se oferă o informație suplimentară, de care avem de fapt nevoie în această problemă. Cred că este unul dintre acele cuvinte care ne trec cam pe lângă noi când citim o problemă de teoria grafurilor. Dar este important să acordați atenție, desigur. Și adică, ni se dă G. Și este conectat. Presupun că, într-adevăr, ar trebui să i se dea conectat G. Dar asta e în regulă. Acum, ceea ce vrem este să calculăm raza lui G în timp, care arată ca produsul vârfurilor, numărul de vârfuri--oops-- ori numărul de muchii sau numărul de ori numărul de vârfuri. Instructorul tău se luptă să vorbească și să scrie în același timp. Dar este o abilitate la care lucrez. Și sincer, scrisul de mână este mult mai ușor cu această mică cretă. BINE. Așa că, în esență, am avut un profesor de matematică la facultate care folosea această expresie tot timpul , care spunea că e important să nu mă gândesc aici. Problema vă cere să calculați raza unui grafic. Și într-un anumit sens, există un algoritm care se scrie singur pentru a calcula raza, nu? Pentru că raza este min peste toate vârfurile, al excentricității. Excentricitatea este distanța maximă. Deci, care ar fi cel mai simplu lucru de făcut aici? Ei bine, într-un anumit sens, ar fi să faci bucla peste toate nodurile, să le calculezi distanța față de toate celelalte vârfuri și să ia maximul pentru fiecare dintre acestea și apoi minul peste toți tipii din bucla exterioară. Din moment ce tocmai am spus o propoziție despre care îmi dau seama că nu se analizează foarte bine, hai să scriem la ce vreau să spun, adică ne vom gândi că există o exterioară... de aceea nu folosesc această cretă-- o buclă pentru exterior, care calculează acest min. Deci... nu? Ei bine, ce vom face? Putem calcula cea mai scurtă distanță de cale până la toate celelalte w din graficul meu, luăm valoarea maximă a w-- distanței de la v la toate celelalte w. Evident, le putem face pe acestea două în același timp. Și apoi, dacă acest număr este mai mare decât maximul meu actual, păstrează-l. Oh, da. Dacă este mai mică decât estimarea curentă pe care o am a razei, atunci o păstrez. Și dacă nu este, atunci îl arunc, nu? Așa că poate îmi inițializez raza la infinit. Și acum să sunăm la numărul ăsta, nu știu, micuțo r. Dacă r mic este mai mic decât R mare, atunci păstrează-l, nu? Și așa că, dacă ne gândim bine, nu cred că este îngrozitor de greu să dovedim că acest algoritm este corect, pentru că este un fel de a lua doar definiția noastră a razei unui grafic și de a o traduce într- un algoritm fără creier. Deci, cred că, într-adevăr, provocarea aici este să demonstrăm timpul de rulare în acest algoritm special. Deci, cum arată timpul nostru de rulare? Deci avem o buclă peste vârfuri. Așa că am cumva un factor de mod v aici. Și apoi, ei bine, graficul nostru este neponderat. Deci, o strategie pentru calcularea celei mai scurte distanțe de cale ar fi căutarea pe lățime. Cred că asta este în notele mele. Da. Și, în general, căutarea pe lățimea întâi, dacă vă amintiți din prelegere, durează mod v plus mod E timp. Deci întrebarea este, OK, deci dacă înmulțesc aceste lucruri împreună, ce primesc? Obțin O din v ori v plus E, așa, timp. Dar cum ar fi, uh-oh. Nu este momentul în care și-a dorit problema cu temele, nu? Deoarece problema temelor îți cere să rezolvi asta în doar mod v ori E timp. Și cumva am suportat un factor în plus. Și acum trebuie să ne dăm seama de ce este de fapt în regulă, sau trebuie să ne reparăm algoritmul. Dar în acest caz, se dovedește că acest timp de rulare este pur și simplu inexact, OK? Care este intuiția noastră aici? Ei bine, ți-am cam subliniat aici. Graficul nostru este conectat. Și în special, va exista o proprietate frumoasă a graficelor conectate, și anume că numărul de muchii micșorează numărul de vârfuri de aici. Deci, într-adevăr, dacă avem v plus E, într-un anumit sens, acesta va arăta ca un factor constant înmulțit cu E plus un alt E aici. Deci toată chestia asta va fi de v ori E timp, da? Deci haideți să facem acest argument puțin mai formal aici. Deci, în special, știm că G este conectat. Și fiecare vârf -- deci, în special, ceea ce se poate întâmpla aici este -- OK, dacă graficul meu nu constă dintr-un vârf, care este un caz pe care l-ați putea elimina destul de repede, ceea ce nu pot avea este un grafic care să arate așa , ca un vârf și apoi o muchie care plutește acolo. Totul trebuie să fie conectat împreună - conectat împreună. OK, deci, în special, ceea ce înseamnă asta este că fiecare vârf este adiacent cel puțin unei muchii, din nou, cu excepția, cred că, din punct de vedere tehnic, cazul unui vârf. Dar cred că ne putem convinge că pentru orice grafic de mărime constantă, nu ne face grozav de îngrijorare , nu? Doar asimptoticii contează în această problemă. OK, deci dacă fiecare vârf este adiacent unei muchii, bine-- și amintiți-vă că fiecare muchie, un fel prin definiția unei muchii, este adiacentă la două vârfuri. Atunci ceea ce putem concluziona este că numărul de vârfuri este mai mic sau egal cu numărul de muchii împărțit la 2. Aceasta este o estimare conservatoare. Și, în special, ce înseamnă asta? Înseamnă că v este O mare a lui E. Acesta este un caz în care trebuie să fim destul de atenți ca O mare să fie o limită superioară, nu? În acest caz, de obicei, v este mult mai mic decât E - ei bine, depinde de câte muchii, ca dacă aveți un grafic cu adevărat dens sau nu. Dar în acest caz, ce înseamnă asta? Asta înseamnă că mod v plus mod E este într-adevăr doar O mare a modului E, nu? Pentru că acesta este O mare a modului E plus O mare a modului E. Și asta înseamnă că problema noastră rulează într-adevăr în timp de v ori E, ceea ce ne- am dorit în problema noastră. Există întrebări din partea publicului nostru aici? Misto. Publicul: Nu prea înțeleg de ce... unde ați trecut de la prima declarație la a doua declarație acolo. Cel puțin o margine implică că v este mai mic sau egal cu E peste 2. JUSTIN SOLOMON: Oh, da. Deci cred că sunt un fel de două lucruri care contează aici, nu? Fiecare vârf este adiacent cel mult unei muchii. Și fiecare margine... da. Fiecare muchie este adiacentă la două vârfuri. Bănuiesc că, de fapt, este al doilea care contează. Deci nu puteți avea niciodată un vârf care plutește de la sine. Deci, o modalitate prin care îmi pot număra numărul de vârfuri este să mă uit la numărul de muchii și să spun că, ei bine, fiecare muchie poate atinge exact două vârfuri. Fiecare vârf trebuie să atingă exact... ei bine, cel puțin o margine. Deci, dacă le puneți împreună, vă puteți convinge că această limită trebuie să fie 2. Dacă doriți să fiți conservatori în privința asta, puteți scăpa de împărțirea la 2 aici, cred. Chiar nu contează. Alte întrebări din partea publicului nostru? Misto. În regulă, deci acum, să aruncăm o privire la partea b. Deci, în partea b de aici, ei ne cer să facem practic o versiune a aceluiași lucru, nu? Ei vor să aproximăm acum raza. Dar ni se oferă un buget mai mic de timp. Deci, acum, ceea ce vrem la numărul b aici este să calculăm o stea R astfel încât-- Mi s-a strigat în manualul meu că st ar trebui să fie întotdeauna „sub rezerva”. Din cauza asta, am primit o recenzie furioasă a manualului pe care l- am scris, ceea ce a fost nedumerit pentru mine. Dar amazon.com nu este o sursă excelentă de date utile. Dar, în orice caz, vrem stea R, care este cuprinsă între raza lui G și de 2 ori raza lui G, așa. Acum, observați-- cu alte cuvinte, vrem să-- primul lucru de observat este că vrem să limităm raza graficului nostru. Și deja, acest lucru ar trebui să ne sugereze cum am putea rezolva această problemă, pentru că dacă ne uităm înapoi la definiția noastră a razei de aici, observăm că raza este un min, nu? Deci, ce se va întâmpla dacă aș returna epsilonul unui alt vârf? Ei bine, este limitată inferioară de rază, deoarece raza este cel mai mic epsilon posibil peste orice vârf. Asta are sens? Acum, când făceam această problemă, pentru că, știi, eu sunt instructorul prost al celor trei, am spus, bine, bine, dar poate că trebuie să fiu cumva judicios cu privire la vârful pe care îl aleg. Ca, ei bine, într-un anumit sens, ceea ce sugerează acest lucru este că poate aleg un alt vârf și îi calculez raza și returnez asta ca aproximare. Dar, bineînțeles, problema vrea să o pun aici între două valori. Deci, pe lângă limita superioară R, vreau să fie mai mică de 2 ori R. Cu alte cuvinte, aproximarea mea se află într-un factor constant. Am încercat niște chestii ciudate, cum ar fi eșantionarea punctului cel mai îndepărtat și așa mai departe. Apoi mi-am dat seama că de fapt nu trebuie să faci nimic din toate astea. Un lucru pe care îl puteți face este să alegeți literalmente orice vârf, să îi întoarceți excentricitatea. Și asta este de fapt destul de bun. Deci iată algoritmul nostru. Lasă-mă să mă întorc la notele mele aici. De fapt, nu știu de ce îmi urmăresc notele. Aș putea face asta din capul meu. Dar mă fac să mă simt mai bine dacă mă uit la ei în același timp. Deci, în special, ceea ce voi face este să aleg u și v. Permiteți-mi să fiu clar aici - orice u și v. Deci, dacă folosesc o structură de date pentru a stoca toate nodurile mele, o iau doar pe primul , tot ceea ce. Și doi, voi întoarce R steaua este egală cu epsilon de u. Acum, desigur, acesta nu este chiar un algoritm. Dacă faci asta la teme, vei pierde puncte. Și motivul este că nu ți-am spus cum să calculezi această valoare aici. Deci, dacă ar fi să scrieți răspunsul dvs. pentru această problemă, desigur, ar trebui să ne spuneți că, într- adevăr, pentru a calcula epsilon, ce fac? Folosesc căutarea pe lățimea întâi pentru a calcula calea cea mai scurtă de la u la toate celelalte vârfuri. Și apoi cred că iau valoarea maximă aici. OK, deci cred că puteți completa detaliile algoritmului. Provocarea mai mare va fi să dovedești că aceasta este de fapt o legătură bună, nu? Și așa, cu alte cuvinte, ce trebuie să dovedim aici... Nu știu. De exemplu, există o revendicare. Există o propunere. Există o teoremă, undeva pe axa aceea. O să-l numesc drept revendicare. O să-l downgradez. Și asta înseamnă că raza graficului meu este mai mică sau egală cu R steaua, care este mai mică sau egală cu de 2 ori raza graficului meu. OK, deci haideți să dovedim chestia asta. Reușesc să folosesc toate plăcile mele pentru o singură problemă aici. OK, deci, în special, pentru a demonstra această afirmație, trebuie să demonstrez două inegalități. Este ca două probleme de teme într-una. Deci, să le numărăm. Există 1. Există 2. OK, deci să facem inegalitatea 1. Cred că îl putem strânge într-un spațiu relativ mic. Deci, amintiți-vă, care este raza graficului meu? Ei bine, doar prin definiție, știm că este min peste tot posibilul u de epsilon de u. Deci, în special, ceea ce este... proprietatea frumoasă despre minimul a ceva este că este mai mic decât orice altceva sau egal. Deci asta... poate să-l numim u0, doar pentru a face distincția între asta și notația pe care o am în partea stângă. Acesta este mai mic sau egal cu epsilon de u, pentru că, nu știu, pentru că min, da? Deci, de fapt, deja - și, desigur, asta este exact ceea ce am ales să fie steaua noastră R. Deci prima parte a dovezii noastre este făcută aici. Deci aceasta este partea ușoară. Și uneori, cum ar fi, acesta este un fel de ceea ce a inspirat algoritmul nostru. Așa că ne așteptăm ca acest lucru să fie destul de simplu. Bine, dar cealaltă jumătate a problemei este puțin mai complicată. Și de fapt, există o soluție în note. Și apoi m-am hotărât, doar pentru a o face puțin mai inexactă, să-mi scriu pe al meu. Dar, de fapt, am un motiv ascuns, care este că observ că în această clasă nu avem tendința de a folosi o mică parte de notație care îmi place. Așa că, pentru comoditatea mea în viitoarele sesiuni de probleme, m-am gândit să o introduc acum. Deci rezolvăm o problemă de minimizare. Lucrul frumos este că în această clasă, tot ceea ce facem este finit. Dacă îmi urmezi cursul absolvent, nu va fi cazul. De fapt, în cursul 2, vom face ca calculul variațional. Dar în acest curs, ce înseamnă asta? Asta înseamnă că dacă minimizez o funcție, există de fapt un vârf în graficul meu care atinge acel minim, nu? Acest lucru este diferit de cum, de exemplu, dacă eu... atunci voi tace. Dar dacă am vrut să minimizez - iată f de x egal cu 1 peste x și vă cer valoarea minimă. Ei bine, este peste tot x mai mare sau egal cu 0. Ei bine, valoarea minimă este 0 dacă iau x la infinit. Dar nu depășește niciodată 0. Deci ești într-un fel în acest univers ciudat. Dacă vă amintiți prelegerea lui Jason, el a vorbit despre inf-uri și sups, spre deosebire de minuri și maxime. Dar acest lucru nu se poate întâmpla în problema noastră, pentru că atunci când calculăm un min, există de fapt un vârf care îl atinge. Și acel vârf, îl numim arg min. Și astfel, acest argument aici reprezintă argument. Deci un lucru pe care îl pot face este să spun, OK. Deci, amintiți-vă că raza mea este min, min peste tot u de epsilon al u. Apoi voi defini un vârf, u0, să fie arg min peste u al epsilonului lui u. Și aceasta este doar o notație elegantă pentru a spune, dă-mi vârful real care face această valoare cât mai mică posibil, da? Lucrul frumos la această problemă este că încă nu suntem îngrijorați de modul în care facem timpul de rulare. Așa că pot construi astfel de lucruri și să nu-mi fac griji cum l-am găsit de fapt, nu? Bine, deci să spunem că am făcut asta. Deci, acesta este, găsește-mi vârful care îmi dă de fapt raza, nu? Deci, cu alte cuvinte, găsesc acel vârf. Și apoi îi găsesc vârful cel mai îndepărtat și măsoară distanța. Și acea distanță este raza graficului meu, bine? Deci, să facem asta de fapt. Deci, în special, atunci pot defini un al doilea vârf, v0. Ei bine, cum funcționează algoritmul de rază? Îl găsesc pe tipul central și apoi îl găsesc pe cel mai îndepărtat. Așa că îl vom face arg max peste toate v în graficul meu al distanței începând de la u până la orice v. Deci, dacă mă gândesc la cercul meu, acesta este un cerc. Atunci u0 este ca acel centru al cercului meu. Și atunci v0 este ca acel punct îndepărtat. Aceasta este o schema, nu? Cercul meu este într-adevăr un grafic în această problemă. Dar cred că analogia chiar funcționează. BINE. Dar, în realitate, algoritmul meu era fără creier. De fapt nu am calculat u0. Am desenat la întâmplare... Îmi pare rău , nu ar trebui să folosesc acest cuvânt. Am desenat în mod arbitrar un vârf, u, și apoi am calculat distanța cea mai îndepărtată de acel tip. Și, bineînțeles, ceea ce trebuie să verificăm este că acel lucru este într-un factor de 2 din ceea ce mi-am dorit. Deci bine. Dacă te am, atunci voi mai defini un lucru numit v. Și asta... oh, băiete. OK, deci observ că spun un lucru și scriu altul. u0 este centrul graficului meu. Cred că am spus-o. Pur și simplu am uitat să-l scriu. Și apoi acest v este cel mai îndepărtat tip de el. Deci, practic, indicele 0 aici înseamnă -- este idealul platonic a ceea ce mi-am dorit în problema mea. Și niciun indice nu va însemna celălalt. Deci acum calculez lucrul cel mai îndepărtat de u pe care l-am ales de fapt în algoritmul meu. Asta e niște v bar. Deci, din nou, amintiți-vă, algoritmul meu spune doar: OK, voi alege un alt punct, v, și apoi voi întoarce distanța lui v la un punct cel mai îndepărtat... oh, scuze, alege un alt... oh, băiete. Alegeți un punct, u, și întoarceți-i distanța la un punct îndepărtat, v. Cred că am reușit să-i pierd pe toți, înnodând împreună u-urile și v-urile aici. OK, de ce am introdus toate aceste notări? Pentru că asta se întâmplă în această problemă, nu? Pentru a calcula efectiv raza, vreau să găsesc punctul cel mai central , u0, și distanța sa cel mai îndepărtat, v0. În realitate, am ales în mod arbitrar punctul u. Și am returnat distanța ta la un moment dat, v. Și vreau să arăt că acele două lucruri sunt într-un factor de 2 unul față de celălalt. OK, acest rezumat are sens chiar dacă am vorbit în cercuri puțin. OK, deci haideți să facem asta. Așa că nu uitați că lucrul pe care îl voi întoarce de fapt este stea R. Și aceasta este egală cu distanța de la u la v acum, pentru că tocmai am făcut toate aceste definiții. Și acum pot să folosesc inegalitatea mea preferată. De fapt, aceasta este un fel de singura inegalitate pe care o cunoaștem în această clasă până acum, cred, care este inegalitatea triunghiulară, care spune că, desigur, aceasta este mai mică sau egală cu distanța de la u la u0 plus distanța. de la u0 la v. Deci, cu alte cuvinte, aceasta înseamnă că cea mai scurtă cale de la u la v este întotdeauna delimitată de la lungimea celei mai scurte căi de la u la u0 și apoi de la u0 la v, nu? Acesta este desenarea unui triunghi. Aha! Dar aruncă o privire. Care este raza reală a graficului meu? Ei bine, în notația mea, raza graficului meu este exact distanța de la u0 la v0. Și acest lucru este mai mare decât distanța de la u0 la orice altceva, prin definiție, pentru toate v, nu? Deci, dacă răsturn această inegalitate înapoi, ei bine, aruncați o privire. Aceasta este distanța de la u0 la ceva. Aceasta este distanța de la u0 la ceva. Deci am doi factori ai razei. Și obțin limita pe care mi-am dorit-o, da? Și deci aceasta este o mică dovadă puțin mai formală a exact același lucru care este în notele temelor. OK, deci singurul lucru care mai rămâne este să arătăm de fapt că algoritmul nostru rulează într-o perioadă rezonabilă de timp. Deci cred că ne dau un buget de ordinul E timp. Dar observați, acel argument este tocmai argumentul pe care tocmai l-am făcut aici, doar minus factorul v. Și factorul v tocmai a venit din bucla peste toate vârfurile din partea a. Așa că acum cred că am terminat cu problema 1. Ca de obicei, am pierdut prea mult timp cu problema ușoară. Bine, vreo întrebare despre asta? Excelent. Ei bine, acum că am scris prea multe, hai să facem restul. Am petrecut timp cu această problemă pentru că îmi place. Pare o problemă de geometrie. BINE. Deci acum, să vedem. În problema 2, am observat că această temă este oarecum plină de probleme prototipice de teorie a grafurilor oblice 6.006 în general. De exemplu, ei merg pe lista lucrurilor pe care oamenii le fac de obicei în teoria graficelor și care sunt trucuri utile de știut. Așa că le-aș sugera studenților din această clasă, chiar dacă este promovat-refuzat, să se uite foarte atent la această temă înainte de a o face pe cea curentă. Cred că ordinea reiese că ei pot face asta, pentru că cred că veți obține câteva indicii bune despre cum să rezolvați toate temele curente. Așa că ați auzit primul aici, băieți. BINE. Deci, în problema 2, vorbim despre investigația pe internet. Deci, în special, la MIT există o mulțime de routere diferite care sunt conectate prin cabluri între ele. Și, în esență, ce ni se oferă? Ni se oferă o grămadă de routere diferite. Și ni se dă lungimea cablului dintre ele. Iar latența, deloc surprinzător, este proporțională cu lungimea cablului. Asta, în înțelegerea mea abstractă a modului în care funcționează computerele, are sens pentru mine. Nu sunt sigur că este adevărat. Dar asta e cam lipsit de importanță pentru 6.006. Presupun că departamentul nostru are o clasă de rețele dacă ești interesat de așa ceva. Și, în esență, ceea ce încercăm să facem este să rezumam latența tuturor routerelor. Așa că haideți să descompunem un pic de notație aici, în timp ce eu continu să dansez în toată camera aici. Îmi pierd în continuare creta. Am nevoie ca un toc. Simt că asta ar fi util pentru găleata de cretă. BINE. Deci acum vom face problema 2 aici. Deci ni se oferă r routere. Și unele dintre ele sunt marcate ca puncte de intrare. Și acum avem o grămadă de fire bidirecționale, wi, fiecare dintre ele având lungimea li. Și aceasta este o valoare întreagă pozitivă aici. Și, de fapt, din cauza asta, din punct de vedere tehnic, cred că mulți studenți din această clasă au mai întâlnit grafice ponderate înainte. Dar dacă te gândești la narațiunea acestui curs, cred că, pentru versiunea acestei teme, nu am întâlnit încă grafice ponderate. Dar o modalitate mai bună de a spune , mai degrabă decât diagnosticarea psihologică a instructorilor, este că ceea ce vom găsi este că există adesea probleme care par a fi probleme de grafic ponderat, dar chiar nu sunt. Și acesta este un exemplu frumos în care acesta este cazul. OK, deci definim latența după cum urmează, că este cel puțin proporțională cu cea mai scurtă cale către un punct de intrare. Și acum avem două presupuneri suplimentare de care avem nevoie, nu? Una este că latența totală, sau cel puțin latența fiecărui vârf, care este același lucru-- latența-- este mai mică decât infinitul. Ce spune asta cu adevărat , apropo? Cum ar fi, când ar fi latența infinită? Ar fi doar infinit dacă mi-ar plăcea să iau o foarfecă și să tai un fir și să mă conectez pentru restul rețelei. Da? PUBLIC: Fiecare router este conectat la un punct de intrare. JUSTIN SOLOMON: Da, exact. De exemplu, există o cale de la fiecare router la un punct de intrare. Nu înseamnă neapărat că întregul grafic este conectat, cred. Dar cel puțin poți ajunge oricând la un punct de intrare. Și apoi, în plus, și acesta este adevăratul kicker aici, că există cel mult 100r picioare de sârmă. De altfel, r înseamnă routere. Aveam problema anterioară în cap și mă gândeam la rază de mult. Deci nu fi ca instructorul tău. Și, de fapt, citește întreaga problemă înainte de a te opri. Dar, în orice caz, lucrul pe care încercați să îl faceți este să calculați suma peste toate routerele-- nu știu, r, orice-- a latenței acelui router. OK, deci asta e problema noastră aici. De altfel, acest mic exercițiu prost pe care tocmai l-am făcut de a lua această problemă a paragrafului și de a o scrie cu marcatori, consider că mă ajută foarte mult atunci când încerc să rezolv aceste probleme de algoritmi, pentru că cred că este foarte ușor să ajung ca aruncat de un zid de text aici. OK, deci această problemă strigă teoria graficelor. Practic folosim termenii aici. Folosim termenii, nu? De exemplu, avem noduri care sunt cam ca routerele. Și poate că marginile sunt un fel ca firele. Dar există un pic de cap, și anume că timpul tău de rulare... la sfârșitul zilei, cred că vrei să comanzi timp de rulare. Acolo lucrurile devin puțin ciudate inițial. Și așa că trebuie să ne gândim puțin cu atenție cum să o facem. Și aici va fi trucul. Deci aceasta începe să arate ca o problemă cu calea cea mai scurtă. Dar ce poate nu ai vrea să faci? Ar fi să repeți peste fiecare router, sau fiecare vârf și fiecare router și să calculez calea cea mai scurtă între fiecare pereche, pentru că dacă ai face asta... oh, băiete, îmi confund terminologia. Există puncte de intrare, care este lucrul la care trebuie să calculez distanța. Și trebuie să iterez peste fiecare router și să-i calculez distanța, poate, până la toate punctele de intrare, apoi să iau min, sau ceva de genul ăsta. Dar dacă aș avea o buclă for dublă, atunci probabil că nu voi primi ordinul de comandă, nu? Pentru că cumva, te aștepți să arate ca ceva pătrat sau ca produsul a doi termeni. Așa că trebuie să fim puțin mai smecheri decât atât. Și vom folosi un fel de truc canonic în teoria grafurilor. OK, deci haideți să urmăm abordarea Toucan Sam aici. O să ne urmăm nasul și să spunem că, OK, practic există un grafic care ne privește în față în această problemă. Dar apoi va trebui să facem o mică modificare, pentru că ne-am dori să folosim genul de căutare liniară pe timp pe care ni-l oferă BFS. Dar se pare că avem greutăți de margine în graficul nostru, deoarece firele sunt asociate cu lungimi, nu? Diferite fire au dimensiuni diferite. Dar avem acest fapt distractiv și frumos, și anume că cantitatea totală de sârmă din întregul nostru univers este mai mică de 100r. Bănuiesc că unitățile din acest 100 sunt cam ciudate, nu? Este ca niște picioare pe router sau ceva, dar orice. OK, deci în special, voi face un grafic cu nodul per router. Deci, poate aici este un router. Există un alt router. Există routerul 1 și routerul 2. Dar, din moment ce vreau să folosesc genul de avantaje liniare în timp ale căutării pe lățimea întâi atunci când calculez distanțe, pot fi puțin cam furiș în privința asta, adică, în loc să am ca 10 picioare de fire, voi avea 10 fire de 1 picior, da? Doar că acum voi avea și lanțuri mici. Deci, aici, poate că lungimea l 1, 2 este egală cu 3, nu? Așa că voi pune trei margini între ele. Deci, cu alte cuvinte, și le voi conecta cu lanțuri de margini pentru fiecare fir. Are sens? Deci, în esență, o să iau problema mea cu graficul ponderat și o să o fac neponderată la fel ca și când am repetat o grămadă - ei bine, nu chiar repetarea, ci înlănțuind împreună o grămadă de muchii, astfel încât lungimea totală a acestui lucru să fie egală cu distanța de la un router la altul. BINE. Un lucru pe care l-am putea face la fel de bine este să legăm numărul de vârfuri și muchii din graficul nostru atunci când facem asta. Deci, în primul rând, să ne gândim la numărul de vârfuri. Și putem fi complet leneși și limitați de sus chestiile astea. Nu contează. Ei bine, pentru un singur lucru, am un nod pe router. Deci avem un factor de r acolo. Și acum, observă că așezăm cablul o bucată pe rând aici, în lanțurile noastre. Și acum tind să am întotdeauna o durere de cap în stil stâlp de gard despre exact care este factorul constant aici. Dar dacă suntem conservatori în privința asta, suportăm cel mult un factor de 100r feluri suplimentare, deoarece acestea sunt toate piesele diferite pe care le-am putea așeza împreună. Cred că este de fapt mai puțin decât atât din cauza punctelor finale, dar orice, pentru că r plus 100 r este O mare din r. Deci numărul de vârfuri din graficul meu aici este O mare din r. În mod similar, care este numărul de muchii? Ei bine, aceasta este exact cantitatea de cablu care se află în interiorul rețelei mele, cred. Da. Deci asta este exact 100r. Ei bine, cred că modul în care este scrisă problema, este delimitată de 100r, dar orice. Deci, acesta, din nou, este O mare din r. Acest lucru este un fel de convenabil. Deci acum avem un număr care le guvernează pe toate, care este r, care vă spune atât numărul de vârfuri, cât și numărul de muchii, până la un factor constant, nu? Deci, un lucru pe care mă pot convinge este că dacă fac BFS pe graficul meu, este oarecum OK. Amintiți-vă, acesta este timpul vârfurilor plus muchiile. Dar în acest caz, acestea sunt aceleași. OK, deci corect. Deci, amintiți-vă, la sfârșitul zilei, încerc să calculez latența. Aceasta este ca lungimea celei mai scurte căi către nodurile punctului de intrare. Așa că aici ar fi un algoritm fără creier, adică pentru toate routerele, pentru toate punctele de intrare, calculați... Nu știu. Să numim routerul de pe i, punctul de intrare j. Eu calculez distanța ca să folosesc căutarea pe lățimea întâi sau așa ceva. Și apoi iau minul acestor valori și le adun pe toate , nu? Deci calculez -- pentru fiecare router, mă uit la fiecare punct de intrare posibil . Îi calculez distanța până la punctul de intrare. Iau minul peste toate aceste lucruri. Și acum adaug asta la suma mea curentă. Există o problemă aici, și anume, nu v-am spus numărul relativ de puncte de intrare față de numărul total de routere. Deci, cel puțin așa cum am scris acest algoritm aici, cât timp ar dura asta? Ei bine, există două bucle pentru diferite. Și în cel mai rău caz posibil, cel puțin în algoritmul meu mort de creier , nu observ că, dacă sunt un punct de intrare, atunci nu am nevoie să calculez distanțe. Ei bine, asta ar avea ordine r pătrat... uh, r pătrat timp, nu? Cel puțin, nu? De fapt, nici măcar nu ar trebui să scriu O mare. Ar trebui să scriu... ce este limita inferioară? Doamne, sunt un profesor teribil de algoritmi. Omega de timp r pătrat, pentru că nici măcar nu am luat în calcul timpul necesar pentru a calcula distanța, nu? Și aceasta este o problemă, pentru că ți-am oferit doar un buget de timp liniar pentru algoritmul tău, nu? Deci aceasta este o față încruntă. Am încercat să desenez emoji-ul turd pe notițele mele. Și într-adevăr... nu a funcționat. OK, deci avem nevoie de un truc mai bun. Și acesta este de fapt unul dintre aceste trucuri prototip, care este să faci următoarele. Deci, să construim un grafic. O să-mi desenez graficul într-un mod anume. Dar observați că nu există nimic la algoritmul meu căruia îi pasă de modul în care l-am desenat. Asta doar pentru a- mi face viața mai ușoară, adică voi pune toate punctele de intrare în stânga și toate routerele rămase non-puncte de intrare în dreapta, pentru că pot. Și așa arată graficul meu. Deci acestea sunt ca punctele mele de intrare. Iată celelalte routere ale mele. Graficul meu nu trebuie să fie bipartit. De exemplu, s-ar putea ca routerele mele să fie conectate între ele, indiferent. Și apoi există câteva margini care merg de la punctele mele de intrare la routerele din grafic. Încerc să mă asigur că graficul meu este conectat. BINE. Și, în esență, ceea ce îți cere această problemă este să spui, OK, pentru fiecare nod din graficul meu, trebuie să calculez distanța până la cel mai apropiat punct de intrare și apoi să însumez toate acele lucruri, nu? Aceasta este schema pe care am putea-o avea în vedere. Deci, într-un anumit sens, ceea ce vrem să facem este să ne gândim la setul de puncte de intrare ca la un nod uriaș, pentru că nu contează pe care dintre acești tipi îl aleg pentru calea mea cea mai scurtă către un punct de intrare. Trebuie doar să găsesc unul, da? Și iată trucul de bază. Și acesta este unul care apare în toată teoria grafurilor, adică voi introduce un nod suplimentar în graficul meu. Și o să-l pun pe partea stângă. El este foarte mare, pentru că este un supernod, care este un termen de artă. Acest termen apare mult. Și îl voi conecta la fiecare punct de intrare din rețeaua mea de routere. Are sens, clasă? BINE. Deci iată genul de chestie tare. Deci, în primul rând, pentru fiecare punct de intrare, care este calea cea mai scurtă de la punctul de intrare la supernod? Ei bine, evident, are lungimea 1, nu? Ți-am desenat aici. Acum, iată chestia. Să luăm cea mai scurtă cale de la supernod la oricare dintre routerele din partea dreaptă. Ce stiu eu? Ei bine, clar... de parcă poate l-am ales pe tipul ăsta de aici. Ei bine, care este calea mea cea mai scurtă? Merge aici și apoi acolo. Există o proprietate care contează aici, și anume că trebuie să treacă prin unul dintre aceste noduri de intrare. Prin care trebuie să treacă? Ridicare din umeri. Pentru rușine. Ei bine, amintiți-vă, inegalitatea preferată a lui Justin este inegalitatea triunghiulară. Și ce spune? Se spune că dacă calculez cea mai scurtă cale de la supernod la orice nod din graficul meu, atunci fiecare fel de sub-piesă a acelei cele mai scurte căi este, de asemenea, cea mai scurtă cale. Acea propoziție a fost greu de analizat. Să încercăm din nou. Deci, în special, dacă am un grafic de la supernod la un router de aici, ei bine, ne-am convins că trebuie să treacă prin unul dintre nodurile de intrare. Prin care trebuie să treacă? Este vreodată ceva care este mai departe decât cel mai apropiat nod de intrare? Ei bine, nu, pentru că aș putea calcula o cale mai scurtă în acest caz, alegând cel mai apropiat nod de intrare și apoi mergând la supernod. Deci, acesta este un mod complicat de a spune că, în esență, ceea ce ne dorim cu adevărat este pentru fiecare router, distanța de la acel router, să-i spunem i, până la supernod, s. Este corect? Asta este distanța până la cel mai apropiat punct de intrare? PUBLIC: Ai mers încă un centimetru prea departe. JUSTIN SOLOMON: Am mers un centimetru prea departe, nu? Pentru că am mers la cel mai apropiat punct de intrare. Și apoi am luat un avantaj suplimentar. Deci vrem să facem minus 1. OK. Deci, ce înseamnă asta? Ei bine, asta înseamnă că de fapt nu trebuie să am această buclă interioară peste toate punctele de intrare posibile . Trebuie doar să construiesc acest nou grafic special cu un nod suplimentar -- observă că nu îmi va afecta timpul de rulare -- și să calculez cea mai scurtă distanță de la supernod la orice alt nod din graficul meu și apoi să o folosesc ca rezultat, da ? Deci, cu alte cuvinte, cum va arăta algoritmul meu? Ei bine, mai întâi, îmi voi construi graficul, nu? Deci, ce trebuie să fac? Dacă ar fi să scriu asta în temele mele, ar trebui să vorbesc despre cum am obținut aceste lanțuri de margini între diferite perechi de routere. În plus, voi face un supernod suplimentar și voi introduce o margine din acesta în fiecare punct de intrare. Observați că adăugarea punctului de intrare aici adaugă doar un 1 la numărul de vârfuri și cel mult, cred, un r la numărul de muchii, ceea ce nu afectează asimptotic dimensiunea niciunuia dintre aceste două seturi. Deci e un lucru bun. Acum voi face-- Voi folosi BFS pentru a face o singură sursă cea mai scurtă cale de la supernodul meu la toate celelalte vârfuri. Și cât timp durează asta? Ei bine, amintiți-vă că, în general, BFS durează timp v plus E. În acest caz, v plus E sunt ambele - arată ca r. Deci, acesta este momentul comenzii. BINE. Și apoi, în cele din urmă, o să însumez peste routere i valoarea distanței de la supernod la router i, minus 1 pentru a ține cont de acea margine suplimentară pe care am adăugat-o. OK, și asta este soluția la problema noastră. OK, aveți întrebări despre numărul 2 aici? Excelent. Hai echipa. BINE. Deci acum să trecem la problema 3. Sunt... da, suntem cam la jumătatea drumului. OK, deci în problema 3-- corect. Deci facem Potry Harter și trei prieteni vrăjitori. Numărul trei de aici, cred, este de fapt irelevant, deși, ca de fiecare dată când vedeți un anumit număr într-o problemă, ar trebui să îl păstrați în cache în geanta cu lucruri de reținut. Și în acest caz, a fost un hering roșu. Potry Harter și cei trei prieteni ai săi vrăjitori au sarcina de a căuta în jurul unui labirint, da? Și în special, sunt câteva lucruri drăguțe de știut despre labirint și lumea Potry Harter-- asta chiar îmi scapă dislexia aici-- care este următorul. Corect, deci ce știm? Știm că în labirintul meu sunt n camere și că fiecare dintre camerele mele are cel mult patru uși. Deci, cu alte cuvinte, dacă mă gândesc să construiesc un grafic din camerele mele, ceea ce este ca, nu cred că spun prea multe despre această problemă, trecând puțin la soluție, ce știm despre gradul oricărui vârf, presupunând că vârfurile mele sunt camere din labirint? Sunt cel mult patru. Deci e cam frumos. OK, corect. Și toate ușile încep să se închidă. Așa că pare o informație utilă de reținut. Dar avem genul acesta de lucruri ciudate, și anume că unele uși sunt fermecate. Și aparent, Potry Harter poate deschide anumite uși gratuit, care nu sunt ușile prevăzute. Și apoi alții, ei trebuie să facă binecuvântarea și apa sfințită, și orice ar fi ceea ce se întâmplă în acest univers, și apoi deschide acea ușă. Dar asta îi costă materiale și dureri de inimă, nu? Și așa vrem să minimizăm asta. Și, deci, ceea ce li se oferă este, practic, o hartă. Și aceasta include toate camerele diferite, modul în care sunt conectate între ele și care dintre uși sunt fermecate. Și ceea ce vreau este numărul minim de uși pe care trebuie să le dezamăgească. Acum, această problemă este ca un fel de ascuns. Și motivul este că există o rețea care este evident de construit. Și acesta se dovedește a nu fi chiar cel potrivit. Și apoi puteți începe să vă gândiți să adăugați greutăți pe grafic și să înnebuniți cu asta. Dar se dovedește că nu este direcția corectă. Și, de fapt, în lumea Potry Harter, aparent, nu suntem îngrijorați de starea lor fizică. Cu alte cuvinte, cele mai scurte căi sunt de fapt irelevante în această problemă. Vezi asta? Pentru că să zicem că am o problemă foarte complicată, enervantă . Deci, poate că am... iată labirintul meu. Și nici măcar nu vorbim despre punctul de intrare, cum ar fi locul în care intră de fapt. Dar doar în scopuri de ficțiune, să spunem că intră în labirintul meu aici și că, doar pentru a fi enervant, cele două uși care sunt fermecate... , am putea face un grafic în care toate vârfurile sunt camere, iar marginile sunt uși-- sunt ca la aceste două capete ale T. Deci am un T uriaș. Și intru chiar în mijloc. Acum, ce are de făcut Potry Harter aici? Ei bine, evident, există... deoarece acest grafic este un copac, sunt doar atâtea ce pot face, nu? Poate intră aici. Ei merg pe tot drumul până la capăt pentru a dezamăgi ușa de aici. Și apoi se întorc și merg spre celălalt capăt. Îl dezamăgesc pe tipul ăla, da? Și acum pot ajunge în alte camere. Da, pentru că acesta este scopul lor, este să viziteze fiecare cameră. Îmi pare rău, cred că am omis acel pas. Acum, sunt câteva lucruri de observat în legătură cu acest exemplu, care îl fac puțin diferit de teoria tipică a grafurilor , și anume, odată ce au dezamăgit această ușă, de parcă ar merge pe aici, și o deschid, ei bine, acum ei mergi în această altă cameră, doar pentru... știi acele exerciții de gimnastică în care alergi în cealaltă parte a camerei, atingi podeaua și apoi alergi înapoi? Cam asta au făcut aici, nu? Au fugit în această cameră. Au lovit acel vârf. Și acum vor să se întoarcă și să meargă pe partea cealaltă. Nu mai plătesc bani la ieșire, nu? Deci, odată ce deschid acea ușă, rămâne deschisă. Și asta este de fapt destul de important, pentru că ceea ce face este că face ca această problemă să nu arate ca o problemă de vânzător ambulant , ceea ce nu ar fi atât de grozav. OK, deci corect. Și, mai mult, este faptul că sunt... poate că subdivizez aceste margini. Am o grămadă de margini aici care nu sunt toate fermecate. Contează asta, ca și cum aș avea vreo cinci miliarde de margini aici? Fara drept? Pentru că ei cer în această problemă doar numărul minim de uși pe care trebuie să le dezamăgești, da? Deci ar putea fi că Harry Harter merge foarte departe de-a lungul graficului meu. Dar atâta timp cât nu trec printr-o ușă fermecată, nu-i costă nimic. Deci ce înseamnă asta? Ei bine, asta înseamnă că, într-un anumit sens, în momentul în care intru într- o cameră, aș putea la fel de bine să merg în orice altă cameră cu care este conectată prin uși nevrăjite. Și asta nu mă costă nimic. Deci, ca o politică, ar trebui să fac asta, nu? intru intr-o camera. Și apoi caut doar în jur și intru în toate ușile posibile care nu mă costă o descântec, pentru că sunt gratuite. Și scopul meu este să vizitez fiecare cameră, da? OK, deci aici va fi trucul ascuns. Așa cum începe să miroasă? Deschid o ușă, iar acum vreau să explorez toate celelalte camere care sunt conectate la aceea. PUBLIC: Poate o componentă conectată. JUSTIN SOLOMON: Da, poate o componentă conectată. Există o problemă. Este componenta conectată în acest grafic? Ei bine, nu. De exemplu, tot acest grafic este o componentă gigantică conectată. Așa că trucul ascuns este că de fapt vom scoate ușile fermecate. Trebuia să se ștergă și nu s-a întâmplat. Dar ideea este că, dacă scoatem ușile conectate, acestea sunt ca bucățile hărții mele pe care le pot vizita fără a suporta niciun cost. Deci, dacă mă gândesc la graficul meu, poate că există o grămadă de vârfuri aici. Și apoi este o ușă fermecată. Și mai sunt o grămadă de vârfuri aici și apoi alte două uși fermecate de genul ăsta. Și, cum ar fi, ceea ce se întâmplă aici, ca dacă acesta este ca un triunghi uriaș sau ceva, este de fapt irelevant, pentru că odată ce ating oricare dintre acestea, acum le pot atinge pe toate celelalte. Deci haideți să sugerăm un algoritm. Deci, primul nostru pas este să construim un grafic, G, unde nodurile sunt camerele - sunt camerele. Și care ar trebui să fie marginile? Ei bine, dacă doar încerc să găsesc aceste mici pâlcuri de camere pe care le pot vizita gratuit dacă ajung la oricare dintre ele, atunci marginile sunt ușile nefermecate. BINE? Și acum, la pasul doi, voi calcula componentele mele conectate , pe care le-am acoperit în prelegere -- componentele conectate ale graficului meu, G. Cât timp durează? Ei bine, amintiți-vă că există doi algoritmi diferiți pe care i-am menționat, care pot face acest lucru. Acesta este BFS sau DFS complet. Și amândoi vor lua același timp. Care este ora aceea? PUBLIC: Linear în dimensiunea graficului. JUSTIN SOLOMON: Linear în dimensiunea graficului. Deci inițial, asta ar putea fi problematic, pentru că vreau comanda n. Ține minte, aici sunt n camere. Dar datorită gradului nostru legat, datorită știrii că fiecare cameră are cel mult patru uși, te poți convinge că atât numărul de vârfuri, cât și numărul de muchii sunt de ordinul n, prin care probabil ar trebui să mă grăbesc , pentru că, ca de obicei, am merg incet. BINE. Deci acum, ce am? Am o listă cu toate componentele conectate în graficul meu. Și fiecare este potențial conectat cu altele prin uși fermecate. Deci, într-un anumit sens, m-aș putea gândi la... nu înseamnă că aceasta este soluția problemei. Dar m-aș putea gândi la modelarea problemei mele ca la realizarea unui grafic nou, în care am pus un vârf uriaș în fiecare componentă conectată. Și poate le conectez prin uși fermecate. Și vreau o cale care să atingă fiecare dintre aceste camere. Dar asta nu este chiar drumul corect de urmat. Și asta te prinde prin surprindere, pentru că asta începe ceva înfricoșător, nu? Dacă ați auzit de problema vânzătorului ambulant, cam așa miroase. Dar acest lucru nu este de fapt corect aici din două motive. Una este că, odată ce deschid o ușă fermecată, pot trece înapoi prin ea. De exemplu, îmi poate plăcea hopscotch înainte și înapoi prin ușa aceea de câte ori vreau și nu mă costă nimic. Mă costă ceva doar prima dată când îl deschid, da? Și mai mult, nu ți-am cerut să- mi calculezi de fapt acea cale. Dacă citiți cu atenție problema, vă cere doar numărul minim de uși pe care trebuie să le deschideți. Deci, aceasta este o problemă cu adevărat furioasă, deoarece se dovedește că există o linie suplimentară de cod care rezolvă această problemă. Acesta este pasul trei, pe care îl voi scrie înainte de pașii unu și doi, doar pentru a vă ține confuz. Și asta înseamnă a returna acest număr de componente conectate minus 1. Asta pare furiș. De ce este asta? Ei bine, ceea ce se întâmplă aici este următorul, adică să spunem că merg de-a lungul-- amintiți-vă că graficul meu este conectat. Deci, ceea ce știu este că pot oricând să ajung de la orice componentă conectată la oricare alta. Și deci să luăm orice ordine -- observați că problema nu m-a întrebat de fapt cum să returnez o cale eficientă. Mi-a cerut doar numărul minim de uși pe care trebuie să le deschid. Deci tot ce trebuie să fac este să mă conving că există o cale cu atâtea uși pe care trebuie să le deschid. De fapt, nu trebuie să-l returnez. Dacă aș face-o, ar fi ușor mai enervant să mă gândesc. BINE. Deci graficul meu este conectat. Așa că un lucru pe care l-aș putea face este să fac lumea... ei bine, cum vreau să fac asta? Ei bine, să vedem aici. Bănuiesc că aș putea veni cu o ordonare care să arate ca o căutare în profunzime a graficului meu. Asta ar trebui să o facă. BINE. Așa că poate încep de la tipul ăsta. Încep doar de la un vârf arbitrar. Și apoi voi face căutarea în profunzime, dar mai degrabă decât pe graficul complet, pe acest tip de metagraf, în care am adunat camere în care pot ajunge fără costuri. Deci ce am de gând să fac? O să încep să merg spre tipul ăsta și apoi o căutare în profunzime, să dau înapoi și apoi să cobor înapoi. Și dacă vă gândiți bine, amintiți-vă că, în primul rând, căutând în profunzime, am această proprietate, nu trebuie niciodată să reexaminez un pâlc pe care l-am ajuns o dată. Ei bine, numărul total de uși pe care o să le deschid este exact numărul de componente conectate minus 1, pentru că de îndată ce am făcut asta, căutarea mea în profunzime se face aici, da? Cu alte cuvinte, acesta este numărul de noduri din graficul meu. Așa că dacă aș lua-- care ar fi o modalitate mai bună de-- observ că în mintea mea, acest lucru era mai ușor de articulat decât în ​​cuvinte. Aici ar fi o modalitate de a face asta, ar fi... PUBLIC: Poate adăugați niște uși fermecate la grafic? JUSTIN SOLOMON: Poate mai adaugă niște uși fermecate. Ah, e adevărat. De fapt, problema mea este puțin prea ușoară. Așadar, atâta timp cât căutarea mea în profunzime se întoarce pe cărările pe care le-a găsit deja, atunci îmi întind mâna în acest tentacul, apoi mă întorc înapoi și apoi ajung într-un loc nou. Nu voi traversa niciodată o ușă fermecată de care nu am nevoie, pentru că am văzut deja locația. PUBLIC: Deci traversezi un copac, practic? JUSTIN SOLOMON: Da. Deci am un arbore cu calea cea mai scurtă care se întâmplă aici. De fapt, cred că o căutare pe lățimea întâi ar fi un exemplu mai bun. De fapt, iată... OK, hai să fim concreti. Îmi pare rău. Ar fi trebuit să mă gândesc la asta mai atent decât m-am gândit ieri acasă. Un lucru pe care l-aș putea face ar fi să calculez un arbore cu calea cea mai scurtă de la un vârf din acest grafic la toate celelalte. În special, asta îmi oferă calea cea mai scurtă. Și aș putea traversa acel copac până la un nod, apoi să- l străbat până la capăt, apoi să-l inversez la un nou nod, apoi să-l traversez până la capăt și așa mai departe. Aceasta nu este o cale eficientă din perspectiva mersului pe jos. Dar din perspectiva deschiderii ușii, este extrem de eficient, pentru că este un copac, nu? Și amintiți-vă că numărul de muchii dintr-un arbore de întindere al graficului meu este exact numărul de vârfuri din graficul meu minus 1, care este exact proprietatea pe care o avem aici. Uau, transpir o secundă acolo. BINE. Așa că acum, în cele 30 de minute rămase aici, mai avem două probleme, ceea ce este timp mai mult decât suficient, mai ales că ultima problemă este în mare parte combinatorie și mai puțin algoritmică. Așa că cred că este în regulă să te concentrezi, poate să vorbești despre asta la un nivel înalt și să arăți un complot distractiv. OK, deci pentru problema 4, avem o companie aeriană, Purity Atlantic. E drăguț, Jason, într-adevăr. Și este deținut de Brichard Ranson. Am înțeles bine? Și Purity Atlantic are o vânzare drăguță - asta nu este ca un unghi drăguț, presupun - care este în esență următorul, și anume că poți rezerva un itinerariu în care ai orașul natal. Și apoi alegi, cred, alte trei orașe pe care vrei să le vizitezi. Și apoi Purity Atlantic... poate că ești în luna de miere și nu ești preocupat de preț, ci mai degrabă de eficiență, pentru că nu vrei să-ți petreci tot timpul într-un avion. Acest lucru este valabil mai ales în această lună. Atunci ce vrei să faci? Doriți să minimizați numărul total de conexiuni, nu? Pentru că, după cum știm cu toții, în primăvara lui 2020, nu vrem să petrecem prea mult timp în aeroporturi, da? Deci, corect. Deci cum facem asta? Ei bine, facem un site web, unde îi spui lui Purity Atlantic orașele pe care vrei să le vizitezi și orașul tău natal. Și vă oferă înapoi un itinerar eficient care minimizează numărul de conexiuni. BINE. Și întrebarea este, cum faci asta de fapt, nu? Cum calculezi cel mai bun itinerariu care minimizează numărul de zboruri pe care trebuie să le faci? Deci care sunt variabilele noastre? Și uneori pare că variabilele sunt toate permutările diferite ale orașelor pe care le-ai putea vizita, nu? Aș putea merge la, nu știu, Cambridge, Boston și apoi Cambridge în Marea Britanie. Poate te descurci ca la Universitatea și apoi, nu știu, Budapesta și în alt loc. Sau le pot face în orice altă ordine. Și asta pare că ar trebui să fie factorial, ceea ce ar fi o veste proastă. Dar aceasta este una dintre aceste probleme pe care presupun că un teoretician al informaticii l-ar putea numi tratabilă cu parametrii fixi. Dar acesta este un fel de termen exagerat aici. Dar, în esență, atâta timp cât ignori toți factorii care îngreunează această problemă, atunci este ușor. Un alt mod de a spune este că, OK, dacă vizitez doar trei orașe, care este numărul total de comenzi posibile ale celor trei orașe ale mele? Clasă? Deci am orașul A, B, C. Aș putea face B, C, A. Aș putea face B, A, C. PUBLIC: Enumerați-le. JUSTIN SOLOMON: Da, bine, Jason. Voi face asta. Deci asta este ceea ce numim matematic demonstrație directă, care sunt alte modalități posibile de a vizita trei orașe. Și acum, prin dovada mea directă, susțin că nu există alte modalități de a vizita trei orașe. Și în special, există 1, 2, 3, 4, 5, 6 ordine diferite ale orașelor pe care le pot vizita. Observați că aceasta este o constantă în problema mea. Nu vă cer să faceți un site web care să ia ca și setul total de orașe pe care doriți să le vizitați în cuplu și să le comandați. Mai exact sunt trei. De asemenea, s-ar putea să observați că 6 este 3 factorial, care este poate o modalitate mai eficientă de a ajunge la aceeași limită. BINE. Deci, corect. Deci, există șase ordonări diferite ale orașelor. Și în fiecare caz, ce va trebui să fac? Va trebui să calculez suma trecerii de la orașul meu sursă la primul, de la primul la al doilea, de la al doilea la al treilea, de la al treilea înapoi la primul, OK ? Deci de ce am nevoie? Ei bine, am nevoie de... într- un fel, vreau să fiu conservator în privința asta, doar costul zborului din fiecare oraș în orice alt oraș. Dar asta nu este tocmai corect. Am nevoie doar de costul zborului din fiecare oraș pe care l-ați specificat ca oraș de care sunteți interesat către orice alt oraș de care ați specificat că vă interesează, da? BINE. Deci, în special, merg la noua mea. Deci, în această problemă, avem c orașe și f zboruri. BINE. Și inițial, s- ar putea părea că trebuie să calculăm o mulțime de cele mai scurte căi. Dar cum ar fi, dacă vreau să merg din Boston, la Budapesta, la Londra, la... Rămân fără orașe... Paris și înapoi la Boston, sau orice comandă prefer, trebuie să-mi fac griji pentru cel mai scurt calea de la Nebraska la California? Potenţial nu. Ca, asta ar putea fi irelevant. Singurele care îmi pasă sunt acele patru orașe pe care le-am identificat, bine? Deci există 3 permutări factoriale posibile. Și la sfârșitul zilei, ei bine, sunt de 2 ori 4 alegeți 2. Dacă vă întrebați, acesta este 12, sau O mare din 1 pereche de orașe, ceea ce înseamnă că, cum ar fi-- în scopuri de itinerar-- itinerar-- adică dacă intru întotdeauna într- un aeroport dintr-unul dintre orașele A, B, C sau orașul meu natal și ies mereu prin altul, atunci sunt patru orașe posibile. Le aleg câte două. Observați că este posibil ca zborurile să nu fie comandate. De exemplu, aș putea să ajung dintr-un oraș în altul. Dar atunci poate că avionul are o conexiune sau ceva. Deci întoarcerea este un cost diferit. Dar, în total, sunt de 2 ori 4 să aleg 2 perechi diferite de orașe din care aș putea intra sau ieși. BINE. Deci acum, ce am de gând să fac? Ei bine, astfel încât să pot calcula cele 12 căi diferite cele mai scurte care contează în graficul meu. Deci, când spun calea cea mai scurtă , la ce mă refer? Ei bine, voi construi un grafic, G, cu un vârf pe oraș și o muchie pe zbor. Și observați numărul de conexiuni pe care trebuie să le fac, numărul minim între orice oraș decât orice alt oraș, este egal cu cea mai scurtă cale - lungimea celei mai scurte căi minus 1, nu? Deci, poate că am... gen, iată Boston. Aici e Londra. Iată Paris, B, L, P pe scurt. Atunci lungimea drumului meu cel mai scurt este 2. Și numărul de conexiuni pe care trebuie să le fac este 1, pentru că mă opresc prin Londra, da? Deci ce am de gând să fac? Ei bine, pentru fiecare pereche de orașe din asta-- hopa-- nu, este în regulă-- în setul orașului sursă și a celor trei orașe pe care doriți să le vizitați, voi calcula cel mai scurt-- lungimea calea cea mai scurtă. Deci acesta este numărul minim de conexiuni pe care trebuie să le obțin de la oricare dintre acestea la oricare alta din graficul meu, G. Ei bine, cât timp durează? Ei bine, există 12 astfel de perechi. Am argumentat deja asta. Și cât timp este nevoie pentru a face de fapt calea cea mai scurtă, deci folosind căutarea pe lățimea întâi? PUBLIC: Timpul liniar de dimensiunea graficului. JUSTIN SOLOMON: Timpul liniar de dimensiunea graficului. Cred că Jason are de fapt un tricou care spune asta. Ei bine, în acest caz, amintiți-vă, acesta este O mare din numărul de muchii plus numărul de vârfuri. Dar doar pentru a-ți face viața puțin mai enervantă, numărul de vârfuri este numărul de orașe. Și numărul de margini este numărul de zboruri, nu? Deci, aceasta durează de 12 ori O din c plus f timp, care, desigur, este doar O din c plus f timp. Observați, acesta este unul dintre aceste lucruri în care suntem ascunși. V-am spus că vizitați în mod special trei locuri. Și de aici a venit acest număr 12. Dacă am fi spus că vrei să vizitezi m orașe, atunci aceasta ar fi o problemă cu temele foarte diferită. Acesta este unul dintre acele lucruri pe care trebuie să le amintiți, unde v-am oferit câteva constante și ar trebui să le folosiți. BINE. Deci acum, ce pot face? Pot repeta peste fiecare permutare a lui A, B, C, nu? Deci este ca și cum ai spune că merg de la sursa mea la orașul 1, la orașul 2, la orașul 3, înapoi la sursa mea. Adun și calculez costul, costul acelei călătorii. Și rețineți, costul în acest caz este egal cu numărul minim de conexiuni. Și apoi returnez minimizatorul. Așa că spun, cum ar fi, este mai ieftin pentru mine să merg la Boston, Budapesta, Paris, Boston, Paris, Budapesta și așa mai departe. Așadar, o buclă for peste permutări, care în general este respinsă. Dar în acest caz, pentru că v-am spus că vizitați exact trei locuri, câți pași vor avea loc în acea buclă pentru? Ei bine, le-am scris pe toate aici, pe tabla noastră. Sunt exact 3 factoriali, sau 6 pași, nu? De 3 ori de 2 ori 1, care este 6. OK. Deci, corect. Deci, la sfârșitul zilei, această buclă for va dura, ei bine, ordinul 6 , care, desigur, este doar ordinul 1. Deci nu contribuie deloc la timpul nostru de execuție. Și întregul nostru algoritm rulează în timp c plus f. OK, deci corect. Deci, aceasta este una dintre aceste probleme în care profitați cu adevărat de constantele pe care vi le-am oferit. Am spus că vizitați trei orașe. Așa că folosește-l. De altfel, ca teoretician în informatică, dacă aș spune că vizitați exact 17 orașe, ei bine, care ar fi cifrele noastre acum? Adică, ar fi 17 factorial și apoi ca 17 alegeți 2. Acestea sunt numere mari. Dar sunt încă constante. Deci, pentru scopurile acestei clase, ar fi OK. Dar în secunda în care îi dau un nume, ca m, apoi am ajuns să mă gândesc puțin mai atent la acele lucruri factoriale . În regulă. Deci asta e problema. Deci, trucul de bază aici a fost că , da, se pare că toate perechile sunt pe calea cea mai scurtă. Dar nu este deloc. Sunt toate perechile de lucruri pe care le vei călători de fapt între calea cea mai scurtă. Și din moment ce acel număr de perechi este finit -- este doar 12 -- este un lucru OK de făcut. BINE. Cum facem? Ah, 15 minute. Perfect. Nu am vrut să fac ultima problemă. Și cred că am reușit să mă pun exact în această poziție. BINE. Deci ultima problemă la această temă, care, din nou, această temă urmează cu adevărat temele prototipice de căutare 6.006 în lățimea întâi, temele de căutare în profunzime. Simt că toate cad într-un tipar similar. Din nou, toate aceste resurse sunt disponibile pentru voi, băieți. Ar trebui să te uiți la ele. Nu încercăm să ascundem nimic. Această problemă implică rezolvarea unui cub de buzunar, care este ca un mic mini cub Rubik, care este 2 pe 2. Și arată așa. Ah, există cretă. De fapt, iată-ne. Deci iată cubul meu Rubik. Arată ca un cub, pe care am probleme să-l desenez. Și în special, este 2 pe 2, ceea ce îl face puțin mai ușor decât cubul Rubik obișnuit. Și în special, vom marca câteva fețe. Pe furiș, au folosit un mic termen de geometrie aici, care este drăguț. Deci, iată fața f0. Îmi pare rău că nu prea vezi asta. Dar fața de sus este f0, în caz că vă întrebați. Fața stângă este f1. Și fața din față aici, f2. Observați că le-am identificat prin vectori asemănători care arată la 90 de grade față de față. Aceștia se numesc vectori normali. Dacă vrei să le definești în mod riguros, poți să-mi iei cursul de absolvent. Dar pentru un cub Rubik, nu este îngrozitor de dificil. Dar, în orice caz, pot vorbi despre răsturnarea acestui cub Rubik într-un mod destul de ușor , și anume că îmi place, voi repara un colț al cubului meu. Deci acesta este ca colțul de care mă țin cu mâna. Și acum pot să apuc, ce? Partea de sus, partea laterală sau partea din față a cubului meu. Și îl pot roti în sensul acelor de ceasornic sau în sens invers acelor de ceasornic. Și vă puteți convinge că acestea sunt toate modalitățile posibile prin care aș putea să mă încurc cu starea cubului meu după ce am reparat un colț. OK, corect. Și astfel, această problemă implică, practic, un fel de truc foarte tipic. De fapt, o mare parte din istoria acestor algoritmi de căutare diferiți-- căutare pe lățime-întâi , căutare în profunzime-întâi, A*, despre care cred că nu o vom acoperi aici-- datează de la, ce, 20 sau 30 de ani în urmă, am fi numit inteligență artificială. În zilele noastre, asta are un sens foarte diferit. Dar pe vremuri, AI se referea la rezolvarea jocurilor de societate, a cuburilor Rubik și a tuturor acestor lucruri, folosind algoritmi. Și modul în care ar face asta este căutând diferitele spații ale configurațiilor. Și acum, dacă ne gândim la fiecare față a acestui cub ca fiind pictată cu o culoare, există diferite configurații ale graficului meu pe care le obțin răsturnând cele trei laturi. Deci, dacă ne gândim că există un vârf pentru fiecare stare a cubului meu, unde starea aici înseamnă colorarea fiecărei fețe de pe cubul meu Rubik, atunci există o margine pentru fiecare mișcare. Și în această problemă, am codificat o mișcare ca o pereche, j virgulă s, unde spune că voi roti fața fj, unde j este între, cred, 0, 1, 2, în direcția s. Și putem doar indexa asta ca plus sau minus 1, ca să spunem în sens invers acelor de ceasornic sau în sensul acelor de ceasornic. Deci, acesta este un lucru drăguț, în care graficul tău are o grămadă de vârfuri, care sunt toate cuburi Rubik. Acesta este un cub. Și apoi există margini dacă pot trece de la una la alta făcând una dintre aceste mișcări. Și aceasta este o abstractizare frumoasă, pentru că dacă vreau să rezolv un cub Rubik în cel mai eficient mod posibil, o modalitate de a face asta este să calculez calea cea mai scurtă de la configurația mea actuală la cubul lui Rubik platonic, unde toate culorile sunt constante. pe diferitele fețe ale cubului meu. Și deci este ca un fel de identificare de bază care se întâmplă peste tot în strategiile de căutare, unde mă voi gândi la fiecare vârf al graficului meu ca fiind starea unui sistem și fiecare muchie ca fiind o tranziție de la unul la altul. . Și apoi căile în chestia asta sunt un fel de moduri diferite de a-mi rezolva puzzle-ul, nu? Deci, așa cum ar fi unul diferit, nu știu, fiecare vârf este o tablă de șah cu piesele de șah împrăștiate pe tabla de șah. Și fiecare margine este o mișcare de șah a unui jucător sau altul. În acest caz, ar trebui să fii puțin atent, pentru că vrei ca jucătorul 1 sau jucătorul 2 să meargă înainte și înapoi unul de celălalt. Dar vă las să vă gândiți la reducerea de acolo. OK, deci corect. Această problemă, cred în mare măsură, este în mare parte doar combinatorie distractivă, mai degrabă decât algoritmi. Dar se ascund un pic de algoritmi aici. Așa că vor să argumentați că numărul de configurații distincte ale acestui cub Rubik, acest tip 2 pe 2, este mai mic de 12 milioane. Acest lucru este frumos, pentru că 12 milioane este un număr căruia computerele pot face față de fapt. Și deci există un argument destul de simplu acolo. Dreapta. Deci, în special, iată un cub. Câte sferturi sunt într-un cub? PUBLIC: Opt. JUSTIN SOLOMON: Opt, mulțumesc. Am ascuns unul aici, în caz că te întrebi. Deci, să presupunem că repar un colț al cubului, așa cum am făcut-o. Apoi, de fiecare dată când rotesc una dintre fețele cubului meu în sensul acelor de ceasornic sau în sens invers acelor de ceasornic, sunt, în esență, ca și cum aș lua un colț al cubului meu și îmi place să-l lipesc în alt loc, nu? Deci, în total, șapte colțuri ale cubului meu se pot mișca. Și dacă nu sunt îngrijorat, cum ar fi... s-ar putea ca unele dintre aceste permutări să nu fie de fapt realizabile printr-un set de pași. Ca, poate ar trebui să- mi sparg cubul Rubik și să-l lipesc la loc. Dar dacă sunt conservator în privința asta, există, desigur, mai puțin sau egal cu 7 configurații factoriale diferite ale colțurilor. Deci, cu alte cuvinte, de fiecare dată când îmi rotesc fața, unul dintre colțuri ajunge într-un alt loc. Deci există 7 moduri factoriale diferite care s-ar fi putut întâmpla. OK, deci asta face parte din limita mea. Amintiți-vă că încerc să limitez numărul total de configurații aici. Și, în esență, ceea ce am făcut până acum este că am spus: OK, ei bine, există o grămadă de cuburi în cubul meu Rubik de 2 pe 2. Așa că îmi va plăcea să dezlipesc întreg acest cub, să iau doar acest colț și să-l lipesc aici. Și există aproximativ 7 moduri factoriale diferite în care aș putea face asta. Dar tot trebuie să socotesc faptul că scot această piesă. Îl lipesc în partea de sus. Dar trebuie să-i dau seama de orientarea. Încă îl pot roti în jurul acestui colț. Și, de fapt, există trei moduri diferite în care l-aș putea roti, nu? Poți să vezi, nu? 1, 2, 3, da? Deci, în total, astfel încât fiecare colț se poate roti în trei moduri. Deci asta înseamnă că am de 3 ori 7 configurații factoriale diferite ca limită superioară. Și acest număr este, așteptați-l, 11.022.480. Problema vă cere să argumentați că limita superioară este limita superioară de 12 milioane. Și într-adevăr, este mai mică sau egală cu 12 milioane. PUBLIC: Este de 3 ori 7 factori sau... JUSTIN SOLOMON: Oh, îmi pare rău. Corect, pentru că există șapte colțuri, fiecare dintre ele se poate roti în trei moduri diferite. De fapt, este de la 3 la a 7-a putere înmulțită cu 7 factorial. Mulțumesc, studente. OK, corect. Deci haideți să vedem aici. Mișcându-mă foarte repede aici, următoarea problemă spune, arătați gradul maxim și minim al oricărui vârf din graficul meu. În primul rând, mă aștept ca vârfurile să aibă grade diferite? Aceasta este un fel de problemă prostească. Cum ar fi, ce ar însemna să ai un vârf care are cumva un grad mai mic decât un alt vârf? Ar însemna că există o anumită configurație a acestui cub pentru care există mai puține mișcări pe care le-aș putea face pentru ao schimba decât o altă configurație a acestui cub. Și evident că nu este cazul, nu? Pentru că atunci când răsturn una dintre fețele cubului meu, tot ceea ce fac este să mut culorile. Nu am schimbat cumva fizica modului în care funcționează un cub Rubik, nu? Și cred că acest lucru a fost intenționat să fie enervant de către instructorii tăi. Gradul min este egal cu gradul maxim. Și, de fapt, gradul fiecărui nod din graficul meu este constant aici. Singurul lucru care merită remarcat aici -- ceea ce nu am argumentat -- se dovedește, cred, a fi adevărat. Dar ceea ce am argumentat este că nu aș putea roti o față și de fapt să ajung în aceeași configurație. Ca, poate, dintr-un motiv oarecare, aveam roșu pe tot exteriorul. Și așa că, când l-am rotit , nu s-a schimbat nimic. Asta evident că nu este adevărat. Dar nu am argumentat cu atenție. Dar atâta timp cât nu îmi fac griji că graficul meu este simplu, ca și cum sunt de acord cu buclele de sine, atunci gradul este cu siguranță constant, da? BINE. Și, de fapt, nu cred că asta se poate întâmpla într-un cub Rubik tipic . PUBLIC: Ei bine, cred că ideea este să spun care a fost gradul. JUSTIN SOLOMON: Oh, da, într-adevăr. Deci nu am calculat gradul. Dar am susținut că sunt egali unul cu celălalt. OK, deci acum trebuie să calculăm care este gradul respectiv. Și iată cum să o faci. Deci, desigur , asta, cred, este chiar mai ușor decât prima parte. În esență, amintiți-vă, avem trei opțiuni diferite pentru fețele pe care le pot roti. Pot roti partea superioară, frontală sau laterală aici. Deci sunt trei fețe pe care le-am putea roti. OK, și în câte moduri diferite le pot roti? Le pot roti în sens invers acelor de ceasornic sau în sensul acelor de ceasornic. Deci sunt două direcții. Deci, în total, există gradul 6 pentru fiecare vârf, nu? Există diferite moduri de intrare sau ieșire dintr-un vârf aici. OK, deci următoarea parte a problemei vă oferă o bucată de cod și apoi face o căutare pe lățime pe acest grafic. Și e super, super lent să-mi dai distanța față de toate celelalte configurații. Și Jason a rulat-o convenabil pe laptopul său aici. Nu... sunt nervos să-ți ating laptopul. Nu-mi pasă atât de mult, dar nu... știi, nu vreau să-ți infectez... da. Dreapta. Deci avem o bucată de cod care explorează graficul tuturor configurațiilor cubului nostru prin căutare la lățime mai întâi și apoi îmi oferă oarecum calea cea mai scurtă, cred că de la cubul de bază, unde toate fețele sunt constante față de toate celelalte configurații care sunt accesibile și generează o diagramă. Dreapta. Și, așadar, ceea ce ei cer este să descopere numărul total de configurații pe care le explorează. Un lucru pe care îl vei afla -- centru în jos -- este că explorează aproape o treime -- de fapt, exact o treime din toate configurațiile posibile ale cubului meu. Cred că putem vedea asta aici. Așa că bănuiesc că rulează toată chestia asta. I-ai văzut pe toți împreună. Dreapta. Hopa! Asta e ok. Și, de fapt, genul de fapt distractiv pe care îl puteți afla despre cubul Rubik de 2 pe 2 pe 2 este că există de fapt trei componente conectate în acest grafic. Deci, cu alte cuvinte, există un fel de trei cuburi Rubik diferite pe care le puteți face, modulo toate diferitele flip-uri pe care le puteți face fețelor. Și acestea corespund rotațiilor de colț ale unuia dintre colțurile obiectului. OK, deci corect. Deci, următoarea parte a problemei vă cere să precizați numărul maxim de mișcări necesare pentru a rezolva orice cub Rubik. Și o puteți vedea în acest complot. Deci, ceea ce vă arată acest grafic este dimensiunea setului de nivel al acestei funcții de distanță pentru fiecare distanță. Deci, cred că din punct de vedere tehnic, arată ca 0. Dar există, de fapt, acesta este la un 1 aici, adică există un vârf la distanța 0, care este sursa. Și pe măsură ce ne îndreptăm din ce în ce mai departe , copacul nostru se extinde. Și vedem din ce în ce mai multe vârfuri. Și aparent, cele mai multe vârfuri sunt aproximativ distanță - este 11 sau 12? 11 depărtare de original. Apoi, în cele din urmă, explorez întregul grafic și am terminat. Și puteți vedea că vârful cel mai îndepărtat este la 14 , ceea ce înseamnă că cel mai enervant cub Rubik de rezolvat poate fi rezolvat în 14 pași pentru cubul de buzunar 2-de-2-de-2. Sunt sigur că Jason știe probabil echivalentul acestui număr pentru 3-by-3-by-3. Dar habar n-am ce este. Sunt impresionat dacă poate să calculeze în capul lui, de parcă părea să încerce. Dar mă abat. Dreapta. Deci, cu alte cuvinte, acesta este de fapt un termen luxos pentru... am vorbit despre raza graficului dvs. în prima problemă. Acum avem diametrul, care este, ei bine, nu neapărat de 2 ori mai mare decât raza, așa cum am definit-o aici, dar de fapt, aproape... cred că într-o anumită constantă. OK, deci corect. Așa că observați că axa verticală aici este foarte mare. Și asta explică de ce acest cod BFS este atât de lent, nu? Pentru că acestea sunt toate configurațiile diferite pe care trebuie să le lovească. Sau mai precis, dacă iau poziția y a fiecăruia dintre aceste vârfuri și îi însumez înălțimea, acestea sunt toate configurațiile care sunt accesibile. Și aceștia sunt toți pașii de care BFS are nevoie înainte de a se termina. Și deci acest număr este în... este cu siguranță în milioane, da. OK, deci, ultima parte a acestei probleme, pe care se pare că nu am timp s-o rezolv, dar oricum vă voi trimite la soluție, este întrebarea cum am putea face asta mai repede. Și, în special, ceea ce scrie este, să spunem că am un total de n configurații pentru cubul meu Rubik . În acest caz, se pare că sunt aproximativ trei milioane, cred. BINE. Și acum vreau un algoritm care să-mi ofere cea mai scurtă secvență de mișcări pentru a rezolva orice cub de buzunar. Omule, chiar distrug creta azi. Și vreau să rezolv orice cub într-un număr de pași care arată ca 2N până la plafonul lui w peste 2, unde-- să vedem aici. Codul furnizat... Îmi pare rău, această problemă s- a schimbat în această după-amiază. [RÂDE] Corect. Deci, unde N sub i este egal cu numărul de configurații accesibile în i se mișcă. Oh bine. Văd ce am făcut aici. Deci, dacă acesta este cubul meu de bază, atunci avem, probabil, șase diferite-- 1, 2, 3, 4, 5, 6 cuburi diferite la care pot ajunge din acestea. Și apoi sunt 6 cuburi la care pot ajunge din toate acestea. Dar, desigur, unii dintre aceștia ar putea fi îndreptați înapoi sau unul către celălalt. Dar acesta este numărul de lucruri care sunt accesibile în i mișcări. Și cer un algoritm care găsește calea cea mai scurtă în această perioadă de timp. Apropo, N mare de obicei exponențiază în acel indice acolo. Asta pare nevinovat, dar nu este. Trucul de bază aici este să faci... Nu mă voi deranja să-l notez. Vom vorbi despre asta pentru o secundă și vom chema pentru ziua respectivă. Ei bine, voi face o imagine. Așadar, algoritmul de căutare pe lățimea întâi la care ne-am gândit până acum alege un vârf și apoi calculează setările de nivel în exterior de la acel vârf până când poate ajunge la destinația pe care doriți să o atingeți. Asta nu prea merge aici. Și... ei bine, vreau să spun, funcționează. Dar va fi destul de lent, pentru că, să zicem că am avut ghinion, iar acum suntem în acel vârf de 14, nu? Apoi, undeva acolo, voi atinge această înălțime mare, care se află peste 11, înainte de a putea ajunge la vârful 14. Așadar, trucul aici este că se dovedește că o pot face doar ajungând la 7. Și modul în care voi face asta este, în schimb, voi rula BFS în paralel pentru două vârfuri diferite, nu? Sursa și ținta. Deci, în acest caz, cubul meu actual și cubul pe care mi- aș dori să fie, ca soluția problemei. Mai întâi voi calcula setul de nivel 1 al acelui cub, apoi setul de nivel 1 al următorului cub, apoi setul de nivel 2, setul de nivel 2, 3, 4. Și observ că în cele din urmă, se vor intersecta, drăguț mult chiar la mijloc. Și deci dimensiunea setului de niveluri... nu trebuie să calculez niciodată un set de niveluri care să fie mai mare de jumătate din lungimea celei mai scurte căi. Trebuie să mă rotunjesc pentru a fi conservator în privința asta. Și de aici iau acest factor aici. Deci, acesta este doar un mic truc frumos pentru a reduce dimensiunea căutării. Acesta este un alt tip de truc standard dacă te uiți la unele dintre codurile pe care oamenii le folosesc pentru rezolvarea algoritmică a jocurilor de societate și așa mai departe. Cred că de obicei caută de la început și sfârșit starea spre exterior și încearcă să se întâlnească la mijloc tocmai din acest motiv, și anume că creșterea exponențială, după cum știm cu toții, poate fi destul de problematică. Bine, oameni buni. Așa că cred că nu mai avem timp. Și cu siguranță m-am epuizat. Deci, cu asta, sperăm să ne vedem săptămâna viitoare. Și da, sper că toată lumea se descurcă bine.