[SCRÂȘIT] [FOSȘIT] [CLIC] JUSTIN SOLOMON: OK. Ei bine, bine ai revenit la o altă sesiune cu probleme. Este grozav să văd din nou fețele zâmbitoare ale tuturor. Corect, așa că astăzi, vom continua discuția despre problemele de teoria grafurilor, de data aceasta concentrându-ne pe, ei bine, puțin din asta, puțin din asta, câteva probleme din trecutul cel mai scurt, calea cea mai scurtă a tuturor perechilor și apoi modificarea a algoritmului lui Dijkstra pentru a ne termina ziua. Așa că, ca întotdeauna, vom parcurge problemele sesiunii cu probleme în ordine, fără niciun alt motiv decât așa mi-au fost prezentate și cred că oricum sunt aproximativ izomorfe cu modul în care merg majoritatea temelor din această clasă. Dar, în orice caz, să începem aici. Deci, în problema sesiunii cu probleme 7-1 aici, ca întotdeauna, prima noastră problemă este un fel de încălzire pentru a ne asigura că înțelegem toate aceste definiții, tehnici pe care le folosim în 6.006. Astăzi, vom trece peste algoritmul lui Dijkstra. Deci, dacă vă amintiți, algoritmul lui Dijkstra este o tehnică pentru calcularea celei mai scurte căi de la o singură sursă la restul graficului. Există aproximativ un milion de moduri diferite de a explica, de a înțelege algoritmul lui Dijkstra. Așa că, fără îndoială, voi reveni asupra celui pe care mi-l amintesc, care probabil nu este cel pe care Jason tocmai l-a vorbit în prelegere. Dar o vom face să funcționeze. Și, desigur, dacă există întrebări, le vom aborda pe parcurs. Am de gând să trec la o bucată de cretă care nu este de opt de un inch și voi începe. Corect, așa că în problema 1A temele noastre aici, ni s-a cerut să rulăm algoritmul lui Dijkstra din nodurile de aici. Apropo, doar un fel de terminologie standard în teoria graficelor pe care cred că o vom vedea multe în temei este că folosim de obicei s pentru felul de punct de plecare al unei căi sau, uneori, sursa dacă vorbim despre fluxurile de rețea. Dar nu cred că le facem în această clasă. Și apoi t este de obicei destinația. De ce, ai putea întreba? Pentru că este litera după s. Corect, deci prima noastră sarcină aici este să calculăm calea cea mai scurtă dintr-o singură sursă de la s la orice altceva din graficul nostru. Inițial, acest lucru pare dureros. Dar nu este. Deci o să mă ierți. Am de gând să scriu un fel de versiune scurtă a algoritmului lui Dijkstra, pentru că vă vorbesc în timp ce rezolv această problemă, ceea ce, desigur, ar fi mult mai enervant pentru voi băieți să o faceți pe hârtie. Dar asta e viața în oraș. Deci acolo. Asta e... în cuvintele lui Britney Spears, este prerogativa mea ca instructor. OK, deci în algoritmul lui Dijkstra , ce facem? Inițial etichetăm toate nodurile noastre ca având distanța infinită până la sursă sau-- și le inserăm în coada noastră de prioritate, cu excepția unui vârf, care desigur este vârful sursă. Și el sau ea are distanța 0 dintr-un motiv evident, și anume că, dacă calea mea începe de la sursă, are distanța 0 până la sursă. Deci, ca stenografia noastră... ce a fost asta? Vreau să folosesc roșu? Da, bineînțeles că da. Dar vezi, e creta asta grasă, omule. BINE. 0. Pot face asta să funcționeze. BINE. Deci convenția noastră de astăzi va fi dacă un vârf nu are o etichetă pe el, este distanța infinită. Deci, ce face algoritmul lui Dijkstra? Algoritmul lui Dijkstra preia cel mai apropiat vârf pe care nu l-am procesat încă și cel mai apropiat în ceea ce privește valoarea distanței pe care am stocat-o la acel vârf și apoi actualizează toți vecinii săi folosind un fel de construcție a stilului inegalității triunghiulare. Deci haideți să vedem cum arată. Până acum, totul se află la o distanță infinită, cu excepția unui vârf, care este vârful s, care este distanța 0. Deci, evident, aceasta ar trebui să fie prima noastră iterație a algoritmului lui Dijkstra. Și acum ceea ce va face vârful S este să se uite la toți vecinii lui s și să le actualizeze folosind inegalitatea triunghiului. Și dacă sunt mai aproape având o cale prin s până la vecin, atunci actualizez distanța. Și dacă nu este, atunci nu o fac. În acest caz, totul este infinit. Deci este destul de clar că ar trebui să-mi îndrept calea prin s, deoarece orice distanță mai mică decât infinitul este mai mică decât infinitul. Deci, în special, observați că există o margine de lungime 8 de la s la a. Așa că acum, în loc să fiu la o distanță infinită, pot vedea că vârful a este cu adevărat distanța 8. Oh, această cretă îmi dă fiori. În mod similar aici, există o margine de lungime 7. Și cred că acestea sunt toate marginile din s. Deci suntem buni. Și acum genul de lucru drăguț cu modul în care funcționează algoritmul lui Dijkstra , care cred că era puțin implicit în construcția pe care am văzut-o ieri, dar e în regulă, este că odată ce vizitez un vârf, nu îl mai ating niciodată. Se îngheață în timp... la distanță, presupun. Dar, în orice caz, asta înseamnă că o să pun o cutie mică în jurul ei, adică am terminat cu tipul ăsta. Nu mai este în coada mea. BINE. Sperăm că sistemul nostru pictural are sens aici. Din nou, cu privire la problema temelor, trebuie să scrieți aceste lucruri. Și îmi pare rău. Asta e nasol. Dar nu trebuie, pentru că azi vorbesc cu voi toți. OK, deci amintiți-vă de algoritmul lui Dijkstra. Ne vom uita la lista noastră de vârfuri pe care nu le-am văzut încă. Deci este totul, cu excepția lui S. Găsește-l pe cel mai apropiat. Și procesează-l pe acesta în continuare. Deci, în acest caz, acesta este 7 aici. OK, deci hai să aruncăm o privire. Care sunt vecinii lui 7? Ei bine, am s. Și asta e... oh, și d aici. BINE. Deci, în primul rând, să aruncăm o privire la s. Evident, dacă am o cale care trece prin c, înapoi prin această margine verticală la s, acea cale are lungimea 8, nu? 7 plus 1. 8 este mai mare decât 0. Deci nu actualizez s. Dar de fapt știam deja asta, pentru că s a fost înghețat aici. Deci nici nu a trebuit să mă uit la marginea aceea. Aș fi putut să-l scot dacă aș fi vrut. BINE. Dar există o altă margine care iese din c, care este îndreptată spre d, care are lungimea 4. 7 plus 4 este, așteptați, 11. Și asta este mai puțin decât infinit. Așa că actualizez distanța lui d la 11. Și nu cred că am reușit încă să greșesc. OK, deci acum, ne-am uitat la toate marginile din c. Și c este înghețat. Și mergem mai departe. OK, în continuare, să vedem. Pe celelalte vârfuri, avem infinit, 8 și 11. Deci, cel mai mic dintre aceste trei numere este 8. Și vom actualiza toți vecinii celor 8, care, din fericire, deși acest grafic pare mare, au avut un pic de milă pentru instructorul tău de secție astăzi. Și într-adevăr, nu există atât de multe margini. Deci nu este prea greu de procesat. Dar aici este chestia. Există o margine de lungime 0 de la a la d aici. Pot ajunge la a în 8 unități. Așa că pot ajunge și la d în 8 unități parcurgând acea margine. 8 este mai puțin de 11. Sunt o veste bună. Vreau să- l șterg sau să-l zgâriesc? Ce va fi mai bine? Îl voi zgâria, doar ca să fiu dezordonat. BINE. Deci acum, d are o distanță de 8 de vârful s. Și cred că asta sunt toate marginile unui. Deci a este setat. BINE. Distracția asta sau ce? Așa că acum ne uităm la toate marginile din... oh, îmi pare rău. Ne dăm înapoi și ne uităm la toate vârfurile noastre. Îl găsim pe cel mai apropiat. Asta este d. Și acum trebuie să-i actualizăm pe toți vecinii lui d. Deci, din fericire, toate vârfurile rămase au distanță infinită. Deci ce știm? Există o margine de lungime 1 aici. Așa că obținem un 9. Există o margine de lungime 2. Așa că primesc un 10. Și cred că acestea sunt toate marginile de ieșire de la d. Și acum d e gata. O să încep să mă mișc mai repede, pentru că asta e plictisitor. BINE. Acum următoarea margine cea mai apropiată este 9. Observați că numai 9-- sau mai degrabă, b, presupun, este vârful, care este în prezent la distanța 9. Are doar un vecin care nu a fost încă procesat, care este e. Deci știm că este la 9, 10, 11, 12 distanță. O să-mi verific restul de hârtie și să mă asigur că nu am făcut încă nicio greșeală. 7, 8. Cool. BINE. Așa că acum următorul cel mai apropiat vârf al nostru este vârful h, care este distanța 10. Și aha! Dacă parcurg marginea în sus de la h la e, pot obține o cale de lungime 11. Și 11, conform celor mai mulți matematicieni, este mai mic de 12. Și, prin urmare, ar trebui să actualizăm valoarea aici. În plus, există o margine de lungime 2 din h, îndreptată spre g. 10 plus 2 este 12. Și cred că asta este. Ajungem acolo. OK, deci următorul cel mai apropiat vârf este e. e nu are margini de ieșire. Deci e totul gata. După aceea, avem g. g are o margine de ieșire de lungime 1 în d. 12 plus 1 este 13, care este mai mare decât 8. Deci nu actualizăm. Și, în mod similar, 12 plus 0 este mai mare decât 7. Deci nu actualizăm. Dar din nou, marginile care indică vârfurile pe care le-am procesat deja, chiar nu trebuie să luăm în considerare, doar prin modul în care funcționează algoritmul lui Dijkstra. Observați că, dacă ar exista o margine de greutate negativă, vom reveni la, atunci această presupunere ar fi problematică. Deci, concluzia de aici este că tipul ăsta este înghețat în piatră. Și acum, observați că coada noastră este de fapt goală, da? Deci, în funcție de cum ne-am configurat... ei bine, nu este gol. Dar conține un singur vârf. Și este la infinit infinit. Infinitul plus 0 este tot infinit. Deci, asta e distanța acestui tip aici. Și acum coada noastră este goală. Îmi pare rău. OK, deci cred că am reușit să fac asta corect. Excelent. Deci problema a cerut două lucruri. A cerut cea mai scurtă distanță de cale pentru o singură sursă. De asemenea, a cerut ordinea de traversare, pe care am uitat să o fac în timp ce făceam această problemă. Dar ai putea să- l retragi destul de ușor. OK, deci asta este partea A. Apoi, în partea B, se spune, schimbați greutatea muchiei de la g la c la minus 6. Deci avem g la c. Și acum, în loc de 0, vom face minus 6. Și întrebarea este, dacă aș rula algoritmul lui Dijkstra, în esență, ce s-ar rupe? Și cred că este destul de ușor de observat. Amintiți-vă că g a fost în esență vârful mai puțin interesant pe care l-am atins în algoritmul nostru aici. Singurul la care ne-am uitat a fost f. Și astfel, această margine de ieșire de la g, de fapt, nici măcar nu ar fi văzută de algoritmul lui Dijkstra, din fericire, până când nu vom atinge toate aceste alte vârfuri într-un mod identic cu traversarea noastră anterioară. Și apoi ajungem în sfârșit la g. Și acum ce se va întâmpla? Ei bine, dacă aș avea această margine de lungime negativă 6, cât este 12 minus 6? Acesta este 6. Și observați că acesta este mai mic decât 7, care este eticheta vârfului c. Dar asta încalcă presupunerea noastră, și anume că de îndată ce vizitez un vârf, nu trebuie să- l mai ating niciodată, nu? Pentru că acum am identificat o cale prin g, înapoi la c, care are o distanță similară cu calea pe care o avea c când a fost vizitat în coadă. Deci, cumva, spiritual, ar trebui să adaug c înapoi la coadă. Dar asta contravine regulilor din algoritmul lui Dijkstra. Deci, de exemplu, dacă aș face asta, ar trebui să mă conving că timpul de rulare nu explodează și că acest algoritm se termină, ceea ce ar putea fi o problemă dacă aveți un ciclu de greutate negativ. Din fericire, avem algoritmi pentru detectarea ciclurilor negative de greutate . Dar asta este o altă chestiune. OK, deci cred că acest lucru este destul de simplu. În esență, îți cere doar să treci prin algoritmul lui Dijkstra și să te asiguri că înțelegi ce se întâmplă. Aveți întrebări despre asta? Misto. Cred că aceasta este una dintre sesiunile cu probleme mai ușoare. Așa că poate vom termina mai devreme, doar că spun mereu asta și apoi vorbesc prea mult. Îmi pare rău. Nu regret. BINE. Deci, corect. Deci, în problema 7-2, aceasta este o extensie a unei probleme pe care am considerat-o, cred, acum două sesiuni de probleme. Și arată cam așa. Mă voi întoarce în notele mele. Deci, amintiți-vă, în două sesiuni de probleme în urmă, am definit raza graficului pentru un grafic neponderat. Am venit cu un algoritm pentru a-l calcula și pentru a-l aproxima , toate acele lucruri bune. Acum, în această problemă, vom face practic același lucru. Dar acum suntem pe un grafic ponderat, da? Deci, în special, vom defini o cantitate - aceasta este problema 2 - numită excentricitate ponderată, care este asociată unui vârf într-un grafic ponderat. Și arată așa. Deci, excentricitatea ponderată asociată vârfului u este egală cu maximul pe toate vârfurile din graficul meu a distanței celei mai scurte căi de la u la acel vârf. Din nou, sperăm că publicul nostru va prinde dacă schimb accidental argumentul pe calea cea mai scurtă. Sunt obișnuit să cred că asta este simetric, dar nu este, pentru că graficul nostru este direcționat. De fapt, în această problemă, nu cred că graficul este direcționat, așa că... am uitat. Este regizat. OK bine. Da, atunci bine. Voi încerca să fiu precis. [RÂDE] Bine, și la fel ca problema pe care am avut-o acum două sesiuni de probleme , deci excentricitatea asociată cu un vârf este un fel ca distanța până la cel mai îndepărtat lucru din graficul meu. Și acum raza graficului meu încearcă să găsească vârful cel mai central, care este minimizatorul excentricității ponderate. Și numim asta raza ponderată. Așa că cel evaluat... agh. Oof, asta e una grea. Raza ponderată este o măsurătoare, care nu este asociată cu un vârf, ci mai degrabă cu graficul. Și este egal cu min peste toate vârfurile posibile, u, al excentricității ponderate a lui u. OK, și deci problema aici este că ni se oferă un grafic direcționat ponderat fără ciclu de pondere negativă. Deci poate avea ponderi negative. Dar nu pot avea un ciclu negativ. Și întrebarea... oh, mi-am atins fața. Întrebarea este, care este -- pot găsi raza graficului meu în timp care arată ca ordinea mod v cub? Acum, dacă vă amintiți din sesiunea noastră anterioară de probleme, când ne-am gândit să calculăm raza unui grafic, ce am făcut? Ei bine, am încercat să venim cu un algoritm inteligent. Și apoi ne-am dat seama că asta era de fapt inutil. S-a dovedit că genul de lucru cu moartea creierului, în care te uiți doar la definiții și doar îl faci să funcționeze, a fost de fapt suficient de bun. Și asta se dovedește a fi cazul aici, nu? Acesta este un bun reamintire pentru noi toți că înainte de a înnebuni... 6.006 este o clasă distractivă de algoritmi. Ajungem să aflăm despre referințe drăguțe la emisiuni TV și toate astea. Înainte de a înnebuni cu asta, desigur, dacă există un algoritm evident care ne urmărește în faza de a rezolva o anumită problemă a algoritmilor, ar trebui să încercăm asta înainte de a încerca ceva mai inteligent. Și într-adevăr, în acest caz, funcționează. Deci, care sunt tipurile de ingrediente de care avem nevoie pentru a calcula raza? Ei bine, raza este excentricitatea minimă. Deci, ceea ce ar fi cel mai inteligent-- sau cel mai simplu lucru de făcut, mai degrabă, ar fi să calculăm excentricitatea pentru fiecare vârf și să ia cea mai mică. Cum calculez excentricitatea pentru fiecare vârf? Ei bine, trebuie să am distanța maximă de la acel vârf. Deci, ceea ce ar fi un lucru simplu de făcut ar fi să calculăm distanțele dintre toate vârfurile posibile. Și în mod convenabil, la prelegere, într-o zi sau alta -- sunt puțin confuz în ceea ce privește ordinea în timp a acestei clase, din cauza modului în care o filmăm -- am descoperit un algoritm care calculează distanța dintre fiecare pereche de vârfuri. Și asta se numește algoritmul lui Johnson. Așadar, dacă ar fi să facem o versiune completă a rezolvării acestei probleme, poate pentru comoditate, primul lucru pe care l-am face este să calculăm delta u, v pentru fiecare pereche u, v posibilă. Și pentru că graficul nostru nu are un ciclu de greutate negativ, putem face asta cu algoritmul lui Johnson. Deci, primul pas este să folosiți algoritmul lui Johnson pentru toate perechile, calea cea mai scurtă. Și vă voi îndruma la prelegeri despre cum să faceți asta. Dar lucrul important este timpul de rulare al acestui pas al algoritmului nostru. Deci algoritmul lui Johnson, vorbind generic, are cinci plus v pătrat log v -- sper că am înțeles corect -- timpul de execuție. Și ce știm despre problema noastră? Ei bine, cred că ni s-a dat că graficul este conectat. Și deci un lucru pe care îl putem face este să observăm că e este mărginit de v pătrat -- cred că chiar dacă nu este conectat. Îmi pare rău. A fost un lucru prost de spus. Doar general vorbind, graficul nostru este simplu. Deci, știm că e, cel mult, este, cred, 2v pătrat, ceea ce înseamnă că acest termen este mărginit superior de v cub, nu? Deci avem v cub plus ordinea v pătrat log v. Și astfel, la sfârșitul zilei, primul termen câștigă. Și avem că acesta este timpul v cub. Observați că ni s-a dat acel buget în declarația problemei noastre. Deci asta este perfect. Cu alte cuvinte, acesta este un mod îndelungat de a spune că este cușer să calculăm toate perechile căi cele mai scurte în constrângerile problemei noastre aici. Deci, este convenabil, pentru că acum, la pasul doi, ei bine, poate că acum pur și simplu păstrăm... facem din nou abordarea Toucan Sam. Ne urmăm nasurile. Și ei bine, acum că avem distanțele noastre pe perechi, acum putem calcula excentricitatea pentru fiecare vârf, pentru tot u, doar direct. Desigur, în temele tale, ar trebui să scrii ce înseamnă asta. Dar aici, direct înseamnă doar că pentru fiecare u, fac bucla peste fiecare v și iau orice valoare este cea mai mare. Deci, observați că am două bucle, 1 peste u, 1 peste v. Deci, acesta este ordinul mod v timp pătrat. Deci deja, primul termen domină aici. Deci e un lucru bun, cred. Și apoi, în sfârșit, trebuie să luăm cea mai mică excentricitate dintre orice u, care, aceasta necesită încă o buclă for. Deci, de data aceasta, fac bucla peste această matrice. Și iau doar cea mai mică valoare, nu? Deci aceasta este doar una pentru buclă. Deci, asta necesită ordine și timp. Și apoi am terminat, nu? Deci aceasta este tehnica noastră de calcul a razei. Și observați că tot ce am făcut a fost să traduc definiția într-un algoritm. Nu am făcut nimic inteligent în această problemă. Și atunci ar trebui să ne verificăm rapid timpul de rulare. Deci, primul pas durează v cub de timp. Pasul doi durează v pătrat ori. Pasul trei necesită timp. Așa că le adun pe toate împreună. Și, desigur, v cubed câștigă. Și asta a fost dat în problema noastră ca buget. OK, deci cred că primele două probleme din această sesiune cu probleme sunt destul de simple. Există întrebări până acum? vorbesc repede. Misto. Bine, așa că acum vom trece la problema 3, care îl implică pe Atniss Keverdeen, care probabil joacă pe... ce, Gunger Hames? Jocuri Unger. Am fost aproape. Îmi pare rău, Under... ah, orice. Înțelegi ideea. Da, așa că înainte să mă las purtat de cap să citesc aici glumele lui Jason, ce se întâmplă în această problemă? Deci aceasta este problema 3. Există o rețea de canalizare subterană. Presupun că și el ar fi putut scrie această problemă despre MIT, nu? Sunt tot felul de tuneluri subterane nebunești aici. Îmi amintesc că, când mă uitam la MIT ca pe un potențial absolvent, ne aveau ca să ne plimbăm prin tuneluri. Am crezut că sunt foarte murdare și nu am înțeles ideea. Așa că m-am dus la Stanford. Dar în orice caz, corect. Deci ceea ce mi se oferă este o hartă. Și chestia asta are n țevi bidirecționale. Nu o voi scrie , dar problema vă spune că toate sunt conectate. Ei fac... ca, poți ajunge de la sursă la țintă, mișcându-te prin conducte. Și corect, și sunt conectate la joncțiuni. Dar la fiecare joncțiune, există mai puțin sau egal cu patru lucruri care se unesc. Așa că, la fel ca în ultima noastră sesiune, de fiecare dată când vezi o astfel de frază , este ca și cum ai țipa, în graficul tău se ascunde un grad. Și mai mult, cred că fiecare intersecție este accesibilă din orice altă intersecție. BINE. În plus, ni se oferă o lungime întreagă pozitivă pentru fiecare conductă. Așa că începe să miroasă ca o problemă cu calea cea mai scurtă. Dar este? Asta e întrebarea noastră. Dar doar pentru a înrăutăți puțin lucrurile, Atniss Keverdeen încearcă să scape prin țevi. Și ea nu vrea să fie detectată. Și în special, există joncțiuni cu senzori de mișcare. Și aparent, informațiile lui Atniss sunt destul de bune aici. Și știe care dintre joncțiunile din rețeaua ei de conducte au de fapt senzori de mișcare care pot detecta oamenii care se mișcă. BINE. Acum, ceea ce o cere această problemă să facă este să spună, poate... se pare că știe unde sunt senzorii de mișcare. Dar poate că ea nu știe dacă sunt ca... ce fel de marcă sunt. Este un senzor Microsoft, sau un senzor Apple sau ceva de genul ăsta? Și, desigur, senzorii au intervale diferite. Deci Atniss Keverdeen aici, ea vrea să fie cât mai conservatoare posibil când traversează această rețea de conducte. În special, ceea ce căutăm, ceea ce vrea ea este în n log n timp aici, găsiți calea care maximizează distanța până la senzori. Deci, sperăm că această problemă are sens. Deci ai un grafic grilă. Ei bine, nu neapărat un grafic grilă, ci o grămadă de vârfuri de valență 4, poate așa ceva. Are sens. Ea locuiește într- un oraș undeva. Și are o sursă de la care începe, o destinație la care vrea să meargă. Și apoi câteva dintre aceste vârfuri sunt marcate ca având senzori de mișcare la ele. Și în loc să- ți dea o rază sau ceva de genul asta, ceea ce spunem noi este că ea vrea să meargă de la sursă la țintă. Este dispusă să meargă o distanță lungă. Lungimea drumului nu contează. Ceea ce contează este că ea nu vrea să se apropie niciodată de vreun senzor de mișcare -- poate că există un al doilea ca aici -- decât trebuie, bine? Deci, în acest caz, cred că dacă ar fi să-l privesc, se pare că nu poți face mai bine decât o margine, nu? Deci ea ar merge așa. Și, desigur, într- un scenariu extrem, s-ar putea să existe un senzor în fiecare joncțiune, caz în care ea este furtunată. Dar am dori să- i anunțăm asta înainte de a începe călătoria ei aici. OK, deci problema noastră are suficient sens? Excelent. BINE. Deci, corect. Deci, din păcate pentru noi, aceasta nu este... din nou, nu pare o problemă cu calea cea mai scurtă. Și motivul este că nu este. Ci mai degrabă, este un fel de problemă de lizibilitate mascată. Și să ne gândim la ce vreau să spun aici. Deci, corect. Deci există un grafic evident aici -- îl vom numi G din lipsă de creativitate -- unde ceea ce voi face este să dau un vârf pe joncțiune. Și voi avea o margine nedirecționată pentru fiecare țeavă a cărei greutate este lungimea. BINE. Apropo, cred că lungimea... nici măcar nu am menționat-o în descrierea problemei. Dar cred că vrea să găsească cea mai scurtă cale care să maximizeze raza. Deci, dacă există mai multe căi diferite pe care ar putea să le urmeze și care ambele au aceeași rază de la senzori, atunci și-ar dori să fie leneșă și să nu meargă prea departe. Deci aici va intra în joc. Dar asta e un fel de îngrijorare secundară, mi-aș imagina, din partea lui Atniss aici. BINE. Și, în plus, nici nu voi încerca să-mi amintesc detaliile acestei probleme. Dar, mai degrabă, există o sursă, care sunt sigur că are un nume drăguț al Jocurilor Foamei atașat și o altă țintă. Și acestea sunt doar două noduri din rețeaua de conducte. Și ea vrea o cale de la s la t. BINE. Deci, în primul rând, să numărăm și să ne asigurăm că știm. Deci câte vârfuri sunt? Ei bine, problema îi dă de fapt un nume. Există ordine n vârfuri, deoarece acesta este doar numărul de joncțiuni, care este ceea ce definim ca fiind n. Presupun că am uitat să scriu asta acolo. Și pentru că avem o legătură de grad, argumentul nostru preferat din această clasă, știm că există și ordine n muchii. Deci sunt vești bune. De ce nu pot folosi acest grafic direct? De exemplu, să presupunem că am calculat calea cea mai scurtă de la s la t. Observați că asta ignoră complet sensul problemei, nu? Ideea problemei este că Atniss vrea să evite aceste vârfuri marcate cu stea pe graficul nostru de aici. Dar calea cea mai scurtă poate să nu facă asta. Cu alte cuvinte, este posibil să fii nevoit să mergi ca pe o cale cu adevărat indirectă pentru a evita să fii detectat de senzori. Asta e o problema. Deci trebuie să fim puțin mai deștepți decât atât. Trebuie să ne gândim puțin la această problemă, dar nu prea mult. Și iată trucul de bază. Să spunem că... să avem mai întâi o problemă puțin diferită , și anume, să spunem că îți dau o rază k și vreau să știu dacă există o cale care să mă poată duce de la s la t fără să vin mai mult decât distanța k de la senzori? Observați că, odată ce am... dacă am un instrument care poate răspunde la asta, ca da sau nu, aș putea veni cu un algoritm care să-mi găsească numărul de senzori făcând bucla peste k sau ceva. poate să nu fie suficient de rapid. Dar aș putea face asta. OK, deci problema nu este de fapt teribil de dificilă, pentru că, în esență, ceea ce aș putea face conceptual este doar să îndepărtez vârfurile care sunt prea aproape de senzori și apoi să rezolv o problemă de accesibilitate. Cum ar fi, pot ajunge de la s la t fără a ajunge la distanța k de vreunul dintre senzori? Ei bine, ce să fac? Doar scot orice vârf care se află la distanță k de senzori. Și apoi calculez accesibilitatea. Deci conceptual, cred că acesta nu este un salt uriaș, intuitiv vorbind. Dar sunt multe detalii de completat, nu? Deci, dezvăluind doar puțin mai mult, am putea defini un grafic Gk. Și Gk va fi subgraful vârfurilor a căror distanță - distanță mai mare decât k față de orice senzor, nu? Și cumva, accesibilitatea în acest lucru poate răspunde, da sau nu, pot ajunge de la s la t fără a ajunge distanța k la un senzor? Apropo, cunoaștem acest termen, subgraf, în această clasă? În esență, este destul de clar ce este doar din cuvânt, nu? Ca, în esență, voi elimina vârfurile din interiorul graficului nostru mai mare și orice muchii care ating acele vârfuri. Și, evident, dacă graficul meu inițial avea o dimensiune de ordine n, atunci subgraful are O mare de n dimensiune. S- ar putea să ai mai puțin. Dar cu siguranță, este o limită superioară. OK, așa că dezvăluim puțin mai mult. Și cumva, aceasta pare o structură convenabilă. Dar nu ți-am spus cum să o calculezi. Și, în special, genul de lucru enervant este această piesă, nu? Trebuie să pot să-mi dau seama dacă sunt la distanța k de vreun senzor. Sau, mai generic vorbind, ar putea fi util să calculez distanța de la fiecare... de la setul de senzori la orice alt vârf din graficul meu, orice altă joncțiune din rețeaua mea de conducte, OK? Ei bine, am acoperit deja un truc în sesiunile noastre cu probleme care ne va ajuta să facem asta, nu? Pentru că, OK, care ar fi un algoritm foarte simplu pentru a face asta? Ar fi să faci bucla peste fiecare senzor, să apelezi algoritmul lui Dijkstra pentru fiecare. Așa că îmi dă distanța până la senzorul numărul 1 și distanța până la senzorul numărul 2, distanța până la senzorul numărul 3. Și apoi iau minul peste toate acestea. Și această funcție îmi oferă distanța până la orice senzor. Asta va fi o problemă, nu? Deoarece algoritmul lui Dijkstra rulează în n log n timp. Dar acum am avut un alt factor, pentru că trebuie să fac bucla peste toți senzorii. Și nu ți-am dat o limită cu privire la câte sunt. Deci, mai generic, aceasta este de fapt o problemă care apare tot timpul în viața mea de zi cu zi, și anume că nu vrem doar să calculăm calea cea mai scurtă către un singur punct. Uneori vrem calea cea mai scurtă către o grămadă de lucruri. Ca, cu alte cuvinte, nu-mi pasă ce senzor este aproape de mine. Nu vreau să mă apropii de niciun senzor, nu? Acest lucru apare în geometrie tot timpul. Poate vreau să știu cel mai apropiat... Vreau să găsesc cel mai apropiat punct de pe autostradă. Deci autostrada trece pe lângă casa mea. Deci autostrada este o grămadă de puncte pe o rețea. Și vreau doar să intru pe autostradă și să încep să conduc. Nu-mi pasă de calea cea mai apropiată de fiecare punct de pe autostradă. Vreau doar ce este mai aproape de mine, nu? Deci, acesta este un lucru destul de practic la care să te gândești. Deci, cum rezolvăm asta? Deci, să presupunem că aceasta este rețeaua noastră de conducte. Simt că desenez foarte mult această rețea. Poate o voi condimenta cu un plus. Și poate, în scopul desenării pe tablă, aceste două vârfuri au senzori. Deci încerc să găsesc cea mai scurtă distanță de cale până la oricare dintre aceste două vârfuri de la fiecare alt vârf de pe grafic sau invers. Nu contează. Este nedirecționat. Și nu vreau să trec peste toți acești senzori. Aceasta este durerea de cap de bază aici. Deci un lucru pe care îl pot face... acesta este un fel de truc ascuns. Și este exact același truc pe care l-am aplicat de câteva ori în sesiunile cu probleme aici -- este să adăugați un nou vârf care să fie un fel ca o sursă și să facem acea distanță de vârf la 0 la fiecare dintre senzorii mei. Și acum ceea ce voi face este să fac o singură sursă, cea mai scurtă cale de la acest nou vârf suplimentar pe care l-am adăugat la restul graficului meu. Acum, de ce fac asta? Ei bine, dacă te gândești bine, ei bine, există o margine de lungime 0 la orice senzor. Din punct de vedere topologic, mă pot gândi la asta ca și cum aș fi lipit toți senzorii într-un singur vârf dacă vreau. Dar asta chiar nu contează. Simt că ar fi o modalitate diferită de a rezolva această problemă, cred că ar fi să luăm toate vârfurile senzorilor, să le lipim într-unul singur și apoi să rezolvi această problemă. Dar mă abat. Așadar, cea mai scurtă distanță de cale de la noul nostru vârf sursă la toate celelalte va fi doar calea scurtă către orice senzor, pentru că observați că orice cale care iese din s trebuie neapărat să treacă printr- un vârf marcat cu stea. OK, deci hai să scriem asta. Practic, ceea ce încerc să fac aici este, la pasul unu al algoritmului meu, vreau să etichetez fiecare joncțiune cu distanța ei până la un senzor. Acesta este obiectivul de nivel înalt aici. Și felul în care voi face asta este că o să fac... hopa, în soluția problemei, au numit-o x. Deci voi fi consecvent. Voi face un nou vârf, sau un nou grafic, mai degrabă, G prim, care este egal cu graficul meu original, G, care provine din rețeaua de conducte, cu un vârf suplimentar, pe care îl vom numi x, care este conectat la fiecare senzor de mișcare cu greutatea 0. Și acum voi face Dijkstra-ul începând de la x, care durează n log n timp, pentru că tocmai ți-am dat dimensiunea graficului nostru aici și îmi oferă în esență cea mai scurtă distanță până la orice senzor de mișcare de la toate vârfurile din graficul meu. Deci e un lucru bun. Este un fel de informație convenabilă. Când rezolvăm aceste tipuri de probleme de algoritmi, observați că am făcut un fel de raționament similar în ambele ultime două probleme, ceea ce puteți face. Și de fapt, este un mod destul de practic de a gândi la algoritmi, unde, de exemplu, această problemă îmi spune că, la sfârșitul zilei, algoritmul meu trebuie să ruleze în n log n timp, nu? Sau cum ar fi, în problema anterioară, rulase în n timp cub-- cred că v timp cub. Deci, un lucru pe care îl pot face este să spun, care sunt toate informațiile pe care le pot aduna din graficul meu în n log n timp? Și aș putea la fel de bine să-l calculez, nu? Deci, de exemplu, distanța până la cel mai apropiat senzor, tocmai ți-am dat un algoritm n log n pentru a-l calcula. Pare o informație utilă. Deci ce naiba ? Aș putea la fel de bine să- l calculez în pasul unu și să-l am prin preajmă. Evident, ai putea face o căutare pe lățimea întâi pe toate numerele calculabile. Și aceasta ar putea să nu fie cea mai eficientă modalitate de a rezolva o problemă. Dar cred că pentru grafice, există doar atâtea lucruri pe care de obicei dorim să le calculăm. Așa că merită să-ți cobori lista de verificare. Ca, în mod similar, aici, observați că vă oferim un buget de timp cub de v. Deci, ați putea la fel de bine să calculați calea cea mai scurtă a tuturor perechilor , pentru că o putem face în timp v cub. Și de ce să nu ai aceste informații în preajmă? Pare util pentru calcularea razei. OK, deci în orice caz, acum, la pasul unu, știm acum cât de aproape este fiecare joncțiune de fiecare senzor. Așa că acum pot să argumentez... Numerez acești pași asemănătoare. Dar nu sunt chiar pași. Acestea sunt mai mult ca niște bule de gândire. Deci bula numărul doi va fi, cum construiesc de fapt Gk, nu? Și observați, am o informație frumoasă aici. Acum știu ce vârfuri sunt în interiorul lui Gk și care nu sunt, nu? Pentru că pot doar să fac bucla peste toate vârfurile. Dacă distanța este mai mare decât k, o păstrez. Și dacă nu este, nu o fac, da? Deci asta îmi oferă un algoritm pentru calculul Gk. Așa că putem construi-- „construiți” cu un C-- construim Gk din graficul nostru original, G. Și acest lucru este foarte ușor de făcut, doar prin bucla peste vârfuri și eliminând orice a cărui distanță este prea mare-- sau prea mică, mai degraba. v. Are sens? Pentru că aceia sunt periculoși. Dacă raza senzorului meu este k, orice vârf cu distanța mai mică sau egală cu k, vreau să arunc. Și cât timp durează asta? Ei bine, există doar o buclă peste vârfuri. Cred că trebuie să țin cont și de stocarea graficului meu. Dar, desigur, acest grafic ocupă mai puțin spațiu decât G. Deci, în general, acesta ia ordine n timp-- Tim-- timp și spațiu. Dar există o captură, care este aceasta este per k, bine? Deci, de fiecare dată când vreau să fac un nou Gk, suport o cheltuială a ordinului n. Dar acest lucru ne aduce deja destul de aproape de problema noastră, pentru că ce putem face? Dacă am Gk, pot spune că BFS pe Gk stabilește accesibilitatea de la s la t, care este ceea ce ne pasă, în afara razei k. Și cât timp durează BFS? Linear în dimensiunea graficului. Îi pun o singură întrebare lui Jason, care este... are întotdeauna același răspuns. Corect, deci BFS ia timp liniar în dimensiunea graficului nostru. Graficul nostru are dimensiunea n, sau un fel de 2n-ish. Deci, la sfârșitul zilei, aceasta ia ordinea n. Deci, dacă problema noastră ar fi scrisă puțin diferit, am fi terminat, nu? Dacă problema a spus, având în vedere o rază k și un grafic, spuneți-mi, da sau nu, există o cale care să rămână în afara razei k a senzorilor? Așa am face asta. Să sperăm că toți suntem de acord. Și putem face asta în ordinea n timp. Oh, glumesc. Comandă n log n timp, pentru că a trebuit să fac mai întâi algoritmul lui Dijkstra . Mulțumiri. BINE. Dar, din păcate pentru noi, nu am terminat, pentru că vrem să găsim cel mai mare k posibil. Vrem să găsim cea mai mare rază pe care să putem sta departe de senzori și să ajungem în continuare cu succes de la s la t. Deci, să spunem că vreau să găsesc acest număr. Așadar, acesta este -- Voi defini k stea -- Am o țintă mobilă pe care să scriu -- este cel mai mare k unde este conectat Gk -- oh, nu este tocmai corect -- de la s la t. Acesta este un mod ciudat de a o exprima. Într-adevăr, asta ar trebui să spună, acolo unde există o cale de la s la t în Gk. Îmi pare rău. Da, unde Gk-- tocmai am formulat asta într-un mod amuzant-- are calea de la s la t. Iată-ne. [RÂDE] Bine. Deci întrebarea noastră este, cum găsim asta? Ei bine, iată un algoritm prost. Aș putea să fac bucla peste toate k, să construiesc Gk și apoi, dacă răspunsul meu este, da, este accesibil, apoi să merg la următorul k, să cresc cu 1 și să o iau de la capăt, nu? Deci acesta este răspunsul prost. Când spun prost, mă refer la răspunsul pe care instructorul tău l- a notat pe notele sale și apoi și-a dat seama că a fost prost, care este o buclă peste k până ajungi la k stea, cred că plus 1, pentru că odată ce ajung acolo, atunci primesc cu degetul mare în jos. Evident, devenind mai mare decât atât va face graficul meu mai mic. Acesta este un fel de filtrare, deoarece fiecare grafic este conținut în interiorul unuia diferit. De fapt, o filtrare ar fi invers. Mă voi gândi mai târziu, pentru că aceasta nu este o clasă de analiză a datelor topologice. Dar, în orice caz, dacă am făcut asta, cât timp va dura? Ei bine, ține minte... OK, deci pentru un singur lucru, am n log n din algoritmul lui Dijkstra. Nu ocolesc asta. Așa că întotdeauna trebuie să socotesc pentru asta. Dar acum, de fiecare dată când încerc un nou k, suport cost n, nu? Asta am argumentat aici. Și astfel, la sfârșitul zilei, acest algoritm ia ordinea k stea n timp așa. Desigur, este puțin ciudat să ai răspunsul la problema ta în timpul de execuție. Dar k stea aici, ar putea fi... nu avem nicio legătură aici. Ar putea fi numărul de vârfuri sau ceva de genul ăsta, da? Și deci, dacă avem un buget de n log n timp, acest lucru nu funcționează. Și deci întrebarea este, putem salva această strategie aici? Și răspunsul, desigur, este da, altfel nu aș sta aici astăzi. Un mod în care ai putea face asta... deci există o modalitate prin care ai face asta ca o persoană reală cu algoritmi. Și mai este modul în care ai putea face asta prin diagnosticarea psihologică a instructorilor. Deci haideți să vorbim despre ambele. De fapt, să o facem mai întâi pe a doua , pentru că cred că este cea mai practică dacă vrei să-ți faci temele rapid, care este după cum urmează. Această problemă vă spune că aveți un buget n log n de timp pentru a rula algoritmul. Și ce înseamnă asta? Ei bine, când trecem peste potențialele Gk pe care le putem încerca, avem un buget de log n încercări înainte de a termina, da? Așa că știm că orice algoritm care construiește un Gk și îl încearcă îl poate face doar de n ori. Și din câte știu, avem un singur algoritm care rulează în log n timp în această clasă, care este căutarea binară. Și așa s-ar putea să ne gândim foarte critic la modul în care am putea folosi acel instrument. Dar, mai general decât atât, cred că aceasta este de fapt o strategie care apare foarte mult, atât în ​​algoritmi, cât și de fapt în analiza numerică , și anume, aveți un răspuns ca da sau nu. Și doriți să găsiți punctul de pe interfață în care da se întoarce la nu. Și așadar, o modalitate de a o face este să- l legați la două capete și apoi să continuați să îl împărțiți în jumătate. Și atâta timp cât relația ta este o grămadă de da și apoi o grămadă de nu, poți continua să faci asta prin căutare binară. Deci, să ne gândim la asta în acest fel. Deci avem un interval lung de k valori. Apropo, evident, aici există o limită superioară, care este ca cea mai mare distanță până la orice vârf din graficul meu, sau ceva de genul acesta. PUBLIC: Suma tuturor distanțelor? JUSTIN SOLOMON: Da, cum ar fi suma tuturor distanțelor sau a unora... PUBLIC: Acesta ar fi un număr foarte mare în comparație cu n. JUSTIN SOLOMON: Dar îți poți permite multe. Ai putea-- dacă ai lua suma fiecărei margini-- iată o modalitate de a face asta. Dacă ai considera că aceasta este suma fiecărei lungimi posibile de margine -- PUBLIC: Nu ar fi mărginit în n polinom? JUSTIN SOLOMON: Mărginit polinom în n? PUBLIC: Diferența dintre u și n. [INAUDIBIL] numere foarte mari în spațiul apropiat. JUSTIN SOLOMON: OK. Nu sunt sigur dacă este corect. Dar este in regula. În orice caz, să presupunem că avem o limită superioară pentru k pentru moment. Atunci ce știm? Știm că aici e steaua k pe care o vreau. Și la stânga, algoritmul meu va reveni da. Algoritmul ăsta de aici sus, sus , va spune nu. Deci un lucru pe care pot să-l fac -- un lucru pe care ar trebui să-l fac este să pun k steaua nu chiar în centrul intervalului meu, în scopuri ilustrative. Dar acum pot căuta binară, nu? Pentru că aș putea interoga aici. Și acum voi primi un nu. Și poate că subdivizez la mijloc din anumite motive. Acum primesc un da. Și pot să triangulez în ceea ce vreau. Deci aceasta este strategia noastră de bază este căutarea binară aici. Dar trebuie să ne dăm seama cum să facem exact asta. OK, deci în primul rând... OK, există o limită superioară evidentă aici, care este doar cea mai mare distanță de la orice vârf la orice senzor. Corect, așa că probabil am putea veni cu unul conservator. Nu am avut chef. Dar în mod convenabil, la pasul unu, amintiți-vă că calcularea numerelor convenabile este întotdeauna un lucru convenabil de făcut. În mod clar, dacă Katniss vrea să... Îmi pare rău, Atniss vrea să meargă într-o rază care este mai mare decât distanța oricărui vârf, a oricărui senzor, are probleme, pentru că asta acoperă întregul grafic, da? Deci corect. Deci avem de fapt o limită superioară aici, care este cea mai mare distanță până la un senzor. Și acum vrem o căutare binară. Dar trebuie să fim puțin atenți cum să o facem, pentru că vrem să fim logaritmici în n, care este ca numărul de vârfuri din graficul nostru. Și, desigur, modul în care am tras acest interval aici, așa cum subliniază Jason, nu am, cel puțin imediat, o limită pentru acest număr în termeni de n. De exemplu, s-ar putea ca greutățile mele să fie foarte mari. OK, deci corect. Deci cum am putea ocoli asta? Ei bine, în esență, ceea ce vrem să facem este căutare binară într-o matrice care se scalează ca vârfurile. Și iată soluția cu care am venit, care sunt destul de sigur că este aceeași cu cea din răspuns -- Ar trebui să verific asta înainte de a preda acest lucru -- care este să fac următoarele, care este a. Amintiți-vă, din nou, avem un buget de n log n. Și astfel putem face un număr constant de lucruri care durează n log n timp. Am putea la fel de bine să continuăm, nu? Și, așadar, un alt fel de lucru convenabil pe care l-am putea face este să-mi sortăm vârfurile după distanța la x, care, desigur, rețineți, este exact distanța până la cel mai apropiat senzor al lor. De ce ai face asta? Ei bine, într-un anumit sens, pe măsură ce mă deplasez de-a lungul acelei matrice, acesta este genul de ordine în care voi elimina vârfurile din graficul meu și voi face ca raza să devină din ce în ce mai mare și mai mare. Are sens? Pentru că acestea, primele cupluri sunt cele de lângă senzor. Pe măsură ce mă deplasez de-a lungul acestei matrice, ei se îndepărtează din ce în ce mai mult. OK, deci vom spune... și bineînțeles, de ce putem face asta? Pentru că sortarea -- cred că aceasta este una pe care toți studenții la informatică de pretutindeni o știu -- ia n log n timp folosind orice sortare preferată-- ei bine, nu este adevărat-- oricare ar fi algoritmul meu de sortare preferat . OK, și vom lua di ca fiind distanța-- a 1-a cea mai mare-- de fapt, cred că în notele mele, am luat-o pe aceasta-- a- a cea mai mică. Mă abat de la notele mele. Deci, există o mare probabilitate ca o greșeală de semn care este pe cale să se întâmple. Și acum ceea ce voi face este să caut o căutare binară pe i. Cu alte cuvinte, sunt pe index în matricea mea de distanțe. Există un motiv să faci asta. Există vreun motiv - cum ar fi, să spunem că distanțele mele sunt ca 1, 2, 5, 7. Deci acestea sunt distanța dintre un vârf și un senzor. Si sa zicem ca testez 3. Si observ ca 3 este admisibil. Cu alte cuvinte, ea poate trece de la un vârf la altul, fără să ajungă niciodată într-o rază de 3. Ar trebui să încerc o rază de 4? Ei bine, nu, pentru că voi elimina nodurile doar atunci când trec un element din această matrice. Deci, are sens să facem căutare binară nu în spațiul îndepărtat, ci mai degrabă în spațiul index al matricei , deoarece acestea sunt genul de conjuncturi care determină când voi elimina lucrurile. Deci, corect. Deci, amintiți-vă, cât de mare este această matrice? Are lungimea n. Deci, în general, această căutare binară durează log n timp. Și asta e bine, pentru că întregul nostru algoritm acum... ce facem? Căutăm binare pe d. Sau mai degrabă, căutăm binară pe i. Și apoi luăm di și îl conectăm la algoritmul nostru acolo sus pentru a ne construi subgraful. Testăm da sau nu. Și asta ne spune intervalul din stânga sau din dreapta în căutarea noastră binară. Și recurgem. Și, în general, aceasta necesită log n timp, sau mai bine zis, log n pași de căutare binară. Și, desigur, fiecare dintre acești pași, așa cum am argumentat acolo sus, ia ordine n timp. Deci, în general, algoritmul nostru ia ordine n log-- oh, nu, am făcut un theta accidental-- n log n timp. Și asta a fost limita pe care am vrut să o atingem. Ca de obicei, există o mulțime de detritus pe care trebuie să le curățăm la sfârșitul problemei noastre aici. Una dintre ele este că vrem de fapt să întoarcem o cale. Dar asta nu e chiar atât de rău, nu? Deci acum am stabilit în esență că putem calcula k stea în n log n timp. Asta e bine. Deci acum, dacă vrem de fapt calea, ne putem construi graficul încă o dată, chiar la k stea. Presupun că îl avem deja de la sfârșitul căutării binare. Și apoi folosește oricare ar fi algoritmul tău favorit de accesibilitate pentru a merge de la s la t și a da lui Katniss calea pe care o dorește, sau mai exact algoritmul lui Dijkstra dacă vrei calea cea mai scurtă, care este politicoasă, pentru că nu vrea să meargă prea departe dacă ea nu trebuie. Mai mult, să vedem. Există câteva cazuri limită care probabil merită menționate în problema dvs. Deci, de exemplu, dacă k steaua este egală cu 0 - cu alte cuvinte, îmi fac căutarea binară. Mă întorc până la primul element al matricei mele. Și încă spune că nu pot. Ce înseamnă asta? Asta înseamnă că nu pot trece de la sursă la nodul țintă fără a trece printr-un vârf care are un senzor la el, caz în care, ce faci? Ei bine, poți întoarce orice cale sau ai putea la fel de bine să te întorci pe cea mai scurtă cale, astfel încât ea să poată alerga. [râde] OK. Și asta, cred, încheie problema noastră. Aveți întrebări despre asta? Degetele în sus, cool. Cum mergem la timp? Ca de obicei, cred că voi termina mai devreme. Suntem exact în același timp în care sunt mereu la problema 4. OK, deci problema 4, trecem de la un univers fictiv la altul aici. Deci acum ne jucăm ca Okepon sau ceva de genul ăsta. Îmi pare rău. Dacă nu aș scrie atât de mare, nu ar fi trebuit să pierd jumătate din ștergerea cursului. Dar este in regula. Corect, atât de tare. Așa că acum o avem pe Ashley Gettem. Și Ashley Gettem încearcă să meargă de la Twinkletown la Bluebluff. Și acestea sunt ambele două poieni din regiunea Tanko. Sunt sigur că dacă aș juca Pokemon, asta ar avea un sens pentru mine, sau orice ar fi asta. Dar în orice caz, avem o grămadă de hărți... avem o hartă a unei grămadă de poieni. Nu-mi place ștergerea de pe această tablă. Deci poate vom începe aici. OK, deci avem n lumini. Și sunt conectate prin trasee cu două sensuri. Și, din fericire, există mai puțin sau egal cu 5 poteci care se conectează în fiecare poiană. Acesta este ca și cum detaliul nostru preferat de adăugat la 6.006 probleme este legat de un grad, da? BINE. Acum, cu fiecare traseu, asociem o lungime, pe care o vom numi l sub t pentru traseul t. Dar, pe lângă asta, vom avea o altă informație, și anume că are acest set de creaturi pe el, c sub t. Așa că acum fiecare potecă... personajul nostru de aici merge pe potecă. Și ce vrea să facă? De fiecare dată când merge pe o potecă, ea strânge o creatură, sau câte creaturi se află pe acea cale. De fapt, ea se simte foarte asemănătoare cu ceea ce mă simt eu la TJ Maxx, nu? Ea merge pe culoar și nu se poate abține. Trebuie să prindă fiecare creatură pe lângă care trece pe potecă. Nu există nicio opțiune aici. Ea nu poate lăsa în urmă, pentru că dacă o face, atunci va fi tristă. Iar motivul pentru care personajul nostru ar putea să nu poată ridica una dintre creaturi ar fi dacă ar rămâne fără uneltele ei pentru a ridica aceste creaturi, care aparent sunt sfere de buzunar. Și are k sfere. Cu alte cuvinte, are ca un rucsac. Și rucsacul poate ține atât de multe sfere simultan, bine? Există câteva detalii aici. Una este că de fiecare dată când merge pe o potecă, adună toate creaturile. Dar dacă merge din nou pe acea cale, va colecta același set de creaturi. Se pare că reapar. Sunt foarte prolifici, aceste creaturi. Și mai mult, sunt magazine la unele din poieni. Și la aceste magazine, ea poate scăpa de creaturile pe care le are în prezent și le poate lăsa și, în schimb, poate ridica sfere goale. Deci, în esență, de fiecare dată când face asta, își golește rucsacul și primește un nou set de material, de unde poate continua să ridice creaturi. Am multe întrebări despre acest personaj. De exemplu, le lasă doar acolo? Se întoarce după ei mai târziu? Ce face ea cu creaturile? Sunt o mulțime de întrebări. De exemplu, are o geantă mai mare pe care să o poată întoarce la magazine și... dar în acest univers fictiv, nu ne vom îngrijora de aceste probleme, bine? Și așa, corect. Deci, în esență, întrebarea aici este că există două locații. Nu-mi amintesc numele... De la Trundletown la Bluebluff pe care încearcă să călătorească între ele. Și se întristează dacă dă peste o creatură pe care nu o poate colecta. Deci întrebarea este, poți găsi calea cea mai scurtă fără a fi trist? Și într-un fel de întorsătură Dada în această problemă, dacă nu există o astfel de cale - cu alte cuvinte, este ca și cum, așa că trebuie să meargă pe o potecă lungă cu o grămadă de creaturi - mai mult decât k creaturi, cred, în cel mai rău caz, atunci tristețea este inevitabilă, este ceea ce se presupune că codul tău ar trebui să revină, ceea ce este cu adevărat defetist. Nu știu cine a scris acest set de probleme. BINE. Întrebarea este cum rezolvăm asta? Pare o problemă cu cea mai scurtă cale. Dar, ca și în cazul tuturor problemelor din 6.006, există o ușoară întorsătură, nu? Și în acest caz, întorsătura este că este calea cea mai scurtă fără a deveni trist, unde tristețea înseamnă că ai rămas fără sfere pentru a- ți aduna creaturi. Uf. Acum, observați că ni se dă un buget, apropo, de, cred, nk log nk time. Este corect? Ca asta. BINE. Observați că acest lucru este puțin suspect. Cumva, ne face să credem că dimensiunea problemei noastre este într-adevăr nk, mai degrabă decât n sau k. OK, deci cum am putea face asta? Să ne gândim la o problemă pe care am rezolvat-o ieri, presupunând că vă uitați la 6.006 sesiuni cu probleme aici. Și amintiți-vă, în problema de ieri, am avut tipul ăsta care mergea pe poteci. Și ca, la fiecare a treia cale, trebuia să bea o bere. Am încercat acest lucru pe drumul spre casă și nu funcționează îngrozitor de bine. Dar, în orice caz, avem un fel de scenariu similar aici, în care există un număr pe care trebuie să-l urmărim, nu? În acest caz, este numărul de creaturi pe care personajul nostru le are rămase pe care le poate ridica. Așa că începe cu o pungă goală. Pe măsură ce le colectează, cantitatea de capacitate din geanta ei scade până ajunge la un magazin, iar apoi se întoarce din nou. Dar vestea bună este că legătura noastră de rulare include k în ea. Deci, de fapt, este în regulă să faci un algoritm care să crească în numărul de creaturi pe care le poate transporta. Este un fel de atipic, dar o alegere interesantă aici. Deci, amintiți-vă, termenul pe care l-am introdus data trecută pentru acest tip de univers este că este un fel ca o mașină de stat. Ca, pe lângă faptul că merge de-a lungul graficului, trebuie să știe câtă capacitate are pentru creaturi. Și iată o modalitate de a face asta. Deci, cred că, de fapt, această problemă nu este prea rea, având în vedere că ați văzut problema în care faceți fiecare al treilea vârf în ultima noastră sesiune de probleme. Într-un fel, este la fel ca aceeași biserică, un alt tip de scenariu aici. Deci, în acest caz, un lucru pe care îl putem face este să facem un grafic. Îi spunem G. Are vârfuri v și muchii E, doar pentru distracție. Dar ceea ce vom face este să avem k plus 1 vârfuri pentru fiecare degajare. Și motivul este că ceea ce vom face este să mergem de-a lungul graficului. Și pe măsură ce ne traversăm marginile, nu vom ține doar evidența costurilor, cum ar fi distanța pe care o parcurge, ci și numărul de creaturi pe care le are rămase în geantă și pe care le poate nota. Și modul în care putem face asta este păstrând o grămadă de copii ale graficului nostru și urcând de fiecare dată când colectăm o creatură nouă. Are sens? OK, deci iată un... haideți să adăugăm puțin mai multe detalii aici. Deci, în special, pot defini vc virgulă i va fi vârful per curățarea spațiului de critter de virgulă. Și modul în care îl pot vedea este că asta reprezintă într-un fel că sunt la compensare... hopa, ar trebui să fie un c. Și am sfere de buzunar care sunt goale. Deci, inițial, voi începe de la v s virgula 0 și voi merge de acolo, OK? BINE. Bănuiesc că depinde dacă o scădeți sau o creșteți. PUBLIC: Ai sfere de buzunar goale [INAUDIBILE]? JUSTIN SOLOMON: Oh, ai dreptate. Da, îmi pare rău. Deci, în acest caz, cred că ar fi k. Vom vedea dacă reușesc să fac asta în mod constant pe parcursul răspunsului meu aici. OK, așa că acum trebuie să vă spun cum să faceți marginile în graficul nostru. Și să facem asta în continuare. Deci, în special, pentru toate traseele de la a-- între a și b, cu lungimea l și creaturi c-- așa că ea ridică c creaturi. Ea parcurge distanța l. Ea trece de la a la b sau invers. Și traseele noastre sunt bidirecționale aici. Trebuie să definim marginile. Și arată așa. Deci avem două cazuri diferite. Unul este locul unde ai un magazin. Și unul este atunci când nu, pentru că asta va afecta modul în care starea ta se va schimba. Deci, corect. Deci prima ar fi... oh, am dat totul înapoi? Oh, nu-mi spune asta. Nu, nu am făcut-o. OK bine. Grozav. Deci primul caz ar fi un nu are un magazin. Deci, în acest caz, ea pleacă cu același număr de creaturi pe care le avea în geantă, minus orice creaturi pe care le ridică pe parcurs. Deci acum voi avea o margine de lungime l. Si o sa trec de la va virgula i la vb virgula i minus c. Deci ideea este că merg de la a la b. Și în acest proces, pierd c creaturi. Dar trebuie să fac asta pentru toate i-urile posibile pe care le-am putut vedea în starea mea. Deci asta merge de la ct la k, nu? c, asociat cu traseul, t, pe care am decis să nu îl folosesc. OK, corect. Deci, punctul de bază aici este că există o grămadă de stări diferite în care pot traversa acest traseu. Dar trebuie să am cel puțin c creaturi în geantă dacă am voie să parcurg această potecă, altfel voi fi trist, bine? Și așa am cam copiat această margine de mai multe ori pentru a reprezenta toate tranzițiile posibile pe care le pot face. Și, în mod similar, să spunem că a are un magazin. Ei bine, încă vreau să adaug un avantaj. Dar acum am luxul de a șterge toate lucrurile din geantă înainte de a aduna creaturi, da? Așa că acum mai vreau o margine de lungime l. Dar acum pot să conectez mai multe vârfuri și să-mi resetez starea în acest proces. Deci acum voi trece de la va virgulă i la vb. Și unde o să ajung? Ei bine, câte creaturi vor fi în geanta mea? Am un sac de capacitate k. Și tocmai am traversat această margine de la a la b, care conținea c creaturi. Așa că primesc v k minus c, așa. Și, bineînțeles, pot face asta pentru tot ce am din... oh, da. Trebuie să fiu atent... ei bine, nu. De fapt, doar pentru toate sunt bine. Da. Cred că ar putea fi... fie o greșeală în modul în care am copiat-o, fie o greșeală în problemă... o greșeală în problemă. PUBLIC: Mai aveți nevoie de [INAUDIBIL]? JUSTIN SOLOMON: Da, cred că este corect. Da, deci cred că... am scris pentru tot i într-un interval, dar nu a fost nevoie. BINE. Da, deci acestea sunt cazurile noastre diferite, nu? Deci, în esență, în acest caz, ne eliberăm coada aici. Ei bine, nici măcar o coadă, doar setul nostru de sfere. Resetăm și mergem mare aici. Observați că al doilea vârf nici măcar nu are un i în index, pentru că nu contează. BINE. Și apoi, în mod similar, asta mă duce de la a la b. Trebuie să fac și chestia simetrică pentru a trece de la b la a. OK, deci acum am un grafic. Și, în primul rând, ar trebui să raționăm și să ne asigurăm că putem construi efectiv acest grafic într-o perioadă rezonabilă de timp. Deci hai să facem asta foarte repede. Dreapta. Deci, numărul de vârfuri din graficul nostru - ei bine, practic am k plus 1 copii ale graficului meu. Deci este egal cu k plus 1 ori n. Și asta e bine. Deci asta e ordinea kn timp - ordinea kn spațiu, presupun. Și, în mod similar, există k muchii care sunt asociate cu fiecare traseu. Și există ordine n trasee, pentru că am o diplomă. Deci, în general, există ordine kn muchii în graficul meu, OK? Grozav. Deci acum problema mea nu este atât de rea. Am o sursă, care este locul de unde începe plimbătorul nostru. Am t, care este destinația, unde vrea ea să meargă. Deci de ce am nevoie? Ei bine, am nevoie doar de orice cale care începe la v s, k. Cu alte cuvinte, ea începe la s și are o geantă plină cu capacitate k și ajunge la - la v t virgulă i pentru orice i, pentru că nu contează câtă capacitate are în geantă când ajunge la destinație. . Deci asta este pentru toți i. Orice cale evită tristețea în modul în care este scrisă această problemă. Deci, cum aș putea face asta? Ei bine, ea vrea calea cea mai scurtă. Deci pot face doar algoritmul lui Dijkstra , de la v s, k. Voi face un pic de curățare după aceea pentru a verifica toate i-urile diferite și a găsi pe acesta cel mai apropiat. Și cât timp durează asta? Ei bine, graficul meu ocupă kn spațiu, deoarece are kn vârfuri și ordine kn muchii. Deci, în general, acest lucru va dura timp de ordine kn log kn , ceea ce este un lucru bun, pentru că exact asta cere problema. Și, desigur, dacă calea cea mai scurtă este infinitul, atunci ce știm? O poți spune cu mine. Tristețea este inevitabilă. [Râsete] Este doar un lucru ciudat de scris pe o tablă. OK, și asta este problema noastră de bază aici. Deci, care a fost strategia noastră? Dacă ne dăm înapoi cu 10 picioare, în esență, ne-am luat graficul. Și mai degrabă decât să ne facem graficul, am făcut k copii ale acestuia cu margini în acest fel de punct la etaj, ceea ce înseamnă că oferiți sfere în procesul de parcurgere a acestor margini diferite, cu excepția cazului în care dați în magazine, ceea ce vă aduce înapoi la nivel. 0. Deci aceasta a fost structura noastră de bază a graficului. Și atunci trebuie doar să facem calea cea mai scurtă pe acel lucru. Aveți întrebări despre asta? Da? PUBLIC: Ultima dată când am făcut duplicarea graficelor, am făcut... a fost un grafic stratificat. Și ai continuat să faci aceste tranziții. Și a fost un DAG. Deci nu putem face asta în timp liniar? JUSTIN SOLOMON: Nu putem face asta în timp liniar? Deci, cu alte cuvinte, de ce graficul nostru nu este un DAG în acest caz particular? Lasă-mă să mă gândesc la asta o secundă. Nu există nimic în această problemă care să spună că graficul trebuie să fie un DAG. În special, cred că ai putea să mergi în continuare... de exemplu , dacă ai avea o potecă cu un magazin care să fie exact același cu numărul de creaturi, ai putea continua să mergi înainte și înapoi pe acea potecă. Și deci există un mic ciclu acolo, care ar fi suficient pentru a nu putea face acest lucru în timp liniar. PUBLIC: Ei bine, marginile pe care le-am construit nu sunt... nu corespund neapărat marginilor din traseele originale. Asta nu este în problemă. JUSTIN SOLOMON: Sigur. Este absolut corect. Așa că am construit un grafic direcționat din cel original. Dar și acel grafic direcționat poate conține cicluri, nu? Deci da, deci cred că exemplul pe care ți-l dau funcționează. Deci am un grafic cu două vârfuri. Poate că se întâmplă și alte chestii grafice, dar orice. Am două vârfuri aici. Și am un număr de creaturi aici. Și am un magazin la fiecare capăt al marginii mele, doar pentru că sunt plictisitor și conservator. Și acum, ei bine, presupunând că c este mai mic decât k, pot continua să merg înainte și înapoi de-a lungul acestei margini de câte ori vreau. Și asta este gratuit, nu? Pentru că de fiecare dată când ajung la capătul marginii îmi arunc toate creaturile. Deci acesta este un exemplu de ciclu din graficul meu. Și pentru că există un ciclu, nu mai sunt în cazul DAG. PUBLIC: Ei bine, este un ciclu în graficul construit. JUSTIN SOLOMON: Îmi pare rău. Da, este un ciclu aici și, de asemenea, un ciclu în graficul construit. Da scuze. Bănuiesc că este adevărat. În regulă, alte întrebări pe care le pot face un hash aici? Excelent. Deci nu am timp? Ah, gălăgie. Nu. OK. În acest caz, vom face ultima problemă aici. De fapt, ultima problemă, cred, este cea mai interesantă. Așa că, ca de obicei, m-am binecuvântat fără suficient timp. OK, care dintre aceste plăci este cea mai ordonată? Cred că răspunsul nu este unul dintre... da, niciunul dintre cele de mai sus. Deci, să folosim spatele aici. OK, corect. Deci ultima noastră problemă este o problemă de transport, nu o problemă de transbordare, care se întâmplă să fie domeniul meu de cercetare, ci mai degrabă, doar o chestiune veche de transport. Așa că aici, în mod ciudat, nu mi-am dat notele mele complete. Deci asta va fi distractiv. Dreapta. Așa că încerc să expediez servere de la San Francisco la Cambridge cu un camion. Și am toate aceste companii terțe care au toate perechi de orașe prin care pot expedia, și doar atât. Aceste companii sunt un fel de dive. Au o limită de greutate. Au doar orașe. Sunt margini direcționate. De exemplu, ei nu-și conduc camioanele înapoi, aparent, sau poate că ridică lucrurile altcuiva și doar îți ridică lucrurile în direcția plictisitoare, sau orice altceva. Deci am o grămadă de... Am n rute de transport. Și fiecare traseu, r sub i, este un tuplu cu si, ti, wi, ci. Și care sunt toate aceste lucruri? Deci aici, aceasta este sursa fiecărei rute de transport maritim, fiecărei rute de transport aici. Aceasta este ținta, nu? Deci aici este ca locul unde pornește camionul. Aici se termină camionul. Aceasta este greutatea maximă pe care o poate suporta camionul. Deci camionul are doar atât de mult spațiu în el. Cauciucurile sunt doar atât de mari. Și dacă pun ceva mai mare decât w, atunci camionul meu va muri. Deci, asta este cel mai mult pe care îl pot pune pe acest camion. Și acesta este costul. BINE. Și am n rute care arată așa. Și încerc să expediez servere. Și, desigur, unele dintre serverele mele sunt prea ocupate. Apropo, facem aici o presupunere, și anume că rutele noastre de transport cu camioane formează un fel de rețea continuă. Pot să merg de la s la t și să expediez, cel puțin, ca o gumă de creion, ca o cantitate minimă de greutate. OK, și deci punctul final de bază al acestei probleme va fi acela de a descoperi cel mai greu lucru pe care îl pot livra. Și vă oferim o problemă pe calea către asta pentru a vă ajuta să demonstrați puțin despre asta. Acesta este un tip foarte tipic de configurare. Deci, din nou, am o grămadă de rute de transport, fiecare dintre ele având o greutate maximă. Și o să vreau să știu, în primul rând, care este greutatea maximă pe care o pot expedia? Și atunci care este costul minim pe care îl pot expedia acea greutate? Deci, în problema A, care este marcată ca digresiune utilă, vom demonstra mai întâi o inegalitate utilă. M-am hotărât să ies din carte cu dovada mea atât de puțin despre asta. Așa că încântați-vă că acest lucru este ușor greșit într-un mod subtil, care este ceea ce mă specializez. Dar, în special, vom face o definiție aici. Deci, să presupunem că pi este o cale ponderată. Atunci blocajul lui pi va fi greutatea minimă a marginii oricărei margini în pi. Și pentru a ne asigura că vedem cum este conectat acest lucru la problemă, dacă încerc să expediez un server și trebuie să-l pun pe camionul 1 și camionul 2 și camionul 3 și camionul 4 și camionul 5 , evident, dintre acele cinci camioane, cel a cărui capacitate de greutate este cea mai mică este singurul care contează în ceea ce privește cel mai greu lucru pe care îl pot expedia. BINE. Deci, corect. Acum, având în vedere un grafic direcționat și două vârfuri, s și t, vom defini o cantitate numită b de s virgulă t. Și vom spune că acesta este maximul pe orice cale, pi, de la s la t a blocajului pi. Bine, deci pentru a verifica această cantitate aici, în esență, ceea ce spune este că, la sfârșitul zilei, am această mare rețea de rute de transport. Vreau doar să merg dintr- un oraș în altul. Și nu-mi pasă ce serie de camioane vreau să folosesc. Vreau doar să maximizez greutatea pe care o pot expedia, nu? Și asta înseamnă că mă voi uita la toate căile diferite pe care le-aș putea lua. Fiecare cale este un fel de bandă limitată de un singur camion care are cea mai ușoară greutate pe care o poate transporta. Și voi găsi calea care are cel mai bun blocaj măsurat prin această cantitate. Folosesc cuvântul „cel mai bun” pentru că am tendința de a face greșeli de semne. Și acesta este un termen vag. BINE. Și apoi, corect. Deci scriu prea mare. Sper că nu voi rămâne fără spațiu. Vom face o definiție suplimentară, care este I din t este vecinii de intrare ai lui t. Și atunci problema vă cere să demonstrați o anumită inegalitate aici, susține, care este că b din s, t este mai mare sau egal cu min a două valori, b din s, v sau w din v, t, pentru toate v în I din t. Deci, să vedem ce spune asta. Deci, amintiți-vă că aceasta este ca și capacitatea pe care o pot expedia de la s la t folosind orice rută și că acea limită superioară este minim două lucruri, nu? Fie capacitatea de expediere către unul dintre vecinii mei cu un avantaj de intrare, fie greutatea practic de expediere de la acel vecin la mine. Observați, aceasta este oarecum similară cu o inegalitate triunghiulară, motiv pentru care vom ști cum să rezolvăm partea B a acestei probleme destul de ușor. BINE. Și mai mult, cu egalitate pentru o stea v în i din t, OK? Ghici ce va fi acea stea. Va fi vârful care este un fel de precedent pe calea camioanelor pe care de fapt îl iau pentru a expedia lucruri, nu? BINE. Deci, cum am putea demonstra asta? Deci, intuiția aici este că calea care vă dă de fapt acest blocaj, această virgulă, trebuie să includă una dintre marginile mele de intrare. Și doar încerc să o găsesc, nu? Cam asta se întâmplă în această inegalitate. Și, apropo, ori de câte ori o problemă îți cere să dovedești o inegalitate, trebuie doar să dai înapoi. Simt că îmi petrec aproximativ 85% din zi cu studenții de cercetare spunând, cum ar fi, OK, dar cum îmi spune asta cu adevărat despre viață? Și acesta este un exemplu bun. OK, deci, în acest scop, voi face o definiție, pe care am găsit-o a fi convenabilă când am rezolvat această problemă, care este următoarea. Am de gând să spun că virgula pi va fi calea reală care îmi dă blocaj. Deci, acesta este un fel de arg max peste toate pi-- Voi folosi notație foarte proastă-- pis care conectează s prin t. Așa ne vom gândi la blocaj. Deci, cu alte cuvinte, aceasta este calea care realizează de fapt această cantitate, b, nu? Deci, cu alte cuvinte, b din s, t este egal cu blocajul - pi are doar două linii - s, t. Acest lucru este convenabil pentru mine, pentru că raționamentul despre acea cale are oarecum sens. BINE. Deci, acum, vom demonstra mai întâi inegalitatea. Și atunci putem demonstra sau nu cazul egalității, în funcție de ceea ce mă simt. OK, deci corect. Deci haideți să dezactivăm acest lucru și să încercăm să folosim placa mea puțin mai conservator aici. OK, deci corect. Deci acum să luăm un vârf, v, din muchiile de intrare aici ale lui t, pentru că asta este ceea ce trebuie să dovedim acest lucru. Și vom demonstra inegalitatea direct aici. În special, putem defini o cale care merge de la s la t după cum urmează. Aș putea să iau pi s, v și apoi să concatenez la capătul acestui tip, t, pentru că știm că există o margine direcționată de la v la t, prin definiția a ceea ce este acest i, OK? Dreapta. Și așa este un fel de convenabil, pentru că aceasta este ca calea blocajului pentru unul dintre vecinii mei. Și acum am cam întins o margine acolo. Și știm că, desigur, aceasta este o cale candidată pentru a ajunge de la s la t. Dar s-ar putea să nu fie cel care realizează blocajul. BINE? Corect, deci da. Și hai... hopa, hai să definim asta ca fiind pi twiddle, doar pentru distracție. Îmi place să dau nume lucrurilor. BINE. Deci ce știm? Știm că b din s virgulă t - ei bine, acesta, prin definiție, este blocajul maxim al oricărei căi de intrare care merge de la s la t. Aceasta este o cale de la s la t, da? Deci, pentru că acesta este maximul, este mai mare sau egal cu gâtul de sticlă al pi twiddle, nu? Acesta este lucrul drăguț cu maxurile, este că tind să fie mai mari decât alte lucruri. BINE. Ei bine, care este blocajul pi twiddle? Ei bine, amintiți-vă definiția noastră de blocaj aici, nu? Este greutatea minimă pe marginea întregului meu drum. Ei bine, am două opțiuni. Fie greutatea marginii este marginea de la v la t, fie greutatea marginii este asociată cu restul acestor lucruri, da? Deci, fie acesta este minul de blocaj al primului segment al drumului nostru, pi s, v-- apropo, care poate fi gol. Și asta e în regulă. Este ca o cale cu o singură margine. Ne putem renunța destul de ușor la acel caz. Sau greutatea lui v, t. Misto? Ei bine, prin definiție, blocajul de pi s, v este exact această cantitate, pentru că asta am ales să fie aici, da? Deci, acesta este exact min din b s virgula v-- care trebuia să fie un v, dar am scris un t-- sau w din v virgula t. Și exact asta am vrut să dovedim, da? Deci asta are grijă de cazul nostru de inegalitate. Vreau să fac cazul egalității? Nu cred că da, da. Deci nu este prea greu să verifici cazul egalității. În esență, poți face o contradicție destul de ușoară, nu? Pentru că dacă este strict mai mare, atunci ce înseamnă asta? Asta înseamnă că fiecare margine de intrare, niciuna dintre ele nu poate fi marginea în care intră calea blocajului tău. Și, evident, este ceva în neregulă cu asta. OK, așa că vă voi îndruma la notele pentru acesta. Și, în sfârșit, problema spune, presupunând că... așa că acum avem o constantă amuzantă aici, doar pentru a-ți face viața puțin enervantă. Avem cel mult 3 rădăcină pătrată n orașe la care ne pasă. Din nou, de ce 3? De ce nu? Cred că. Și ceea ce ne dorim este greutatea celui mai mare server unic și costul minim pentru a expedia acel lucru. Deci vrem una, cea mai mare greutate pe care o putem expedia. Vom numi acea steluță pentru expediere. Și două este cel mai mic cost pentru a expedia acea greutate, w stea, OK? Deci, să facem mai întâi două, pentru că este ușor. Deci, să presupunem că am putut să calculez w steaua. Deci acum ce pot face? Ei bine, pot construi un grafic în care să păstrez doar camioanele care pot transporta cel puțin această greutate, pentru că celelalte nave sunt... Îmi doresc foarte mult să fie bărci în această problemă. Dar celelalte camioane sunt inutile, nu? Dacă nu pot acoperi steaua, atunci nu își trage greutatea, da? Deci, pentru a face partea a doua aici, ce pot face? Pot face un nou grafic, G sub c, cu un vârf pentru fiecare oraș și-- dreapta-- și o muchie-- o margine direcționată, scuze, pe rută de transport cu-- aceasta va fi o ciocnire nefericită în terminologie . Voi spune greutatea marginii pentru a mă referi la greutatea marginii din graficul meu. Și asta va fi egal cu costul marginii. Și ține-te doar în jur, dar numai pentru rute care pot transporta cel puțin w o cantitate de stele. Și acum ce facem? Ei bine, este doar cea mai scurtă cale, nu? În acest moment, calea cea mai scurtă, care este într-adevăr costul minim în acest caz, pentru că asta asociem la margini, îmi va oferi costul de expediere cu stea în rețeaua mea. Cred că asta este destul de evident din această construcție. Deci, acesta este Dijkstra, D-I-J-K-S-T-R-A. Și acum singura întrebare este, cât timp durează? Așa că să presupunem că fac versiunea fără creier a Dijkstra, unde folosesc doar o matrice de acces direct pentru a-mi face coada de prioritate. Deci, dacă vă amintiți, va fi nevoie de O mare de mod v cub aici... pătrat? Pătrat. Da, ai dreptate. Îmi pare rău. Mă gândeam la algoritmul lui Johnson. BINE. Ei bine, în acest caz, cât de mare este v? Ei bine, este rădăcina pătrată a lui n, de 3 ori rădăcina pătrată a lui n, cel mult. Deci, desigur, v pătrat este cu adevărat mare O din n. Și acea parte este rezolvată, da? Deci, într-adevăr, singura noastră problemă rămasă aici este să facem partea întâi. Și nu prea am timp suficient. De fapt, nu am timp. Așa că poate vom vorbi pe scurt despre asta. Îmi pare rău pentru asta. În esență, observația de bază aici este că inegalitatea pe care am demonstrat-o în partea A a problemei noastre este într-un fel ca inegalitatea triunghiulară a lumii blocaj, într-un anumit sens. În esență, ceea ce vă oferă este o formulă de actualizare care arată cam ca formula de actualizare pe care am aplica-o în algoritmul lui Dijkstra pentru calea cea mai scurtă , ipoteza de bază aici fiind că, ei bine, calea mea cea mai scurtă trebuie să vină de undeva, nu? Deci, dacă mă uit la toți vecinii mei și apoi adaug într-un fel la marginea mea cea mai apropiată, sau mai degrabă, suma lungimii căii la vârful anterior plus marginea pentru mine, care îmi dă calea cea mai scurtă. Aici, în loc de asta, spunem cea mai mare cale de blocaj. Deci ce fac? Mă uit la toți vecinii mei care vin. Îl găsesc pe cel cu cel mai mare blocaj, care este limitat de blocul lor, plus blocajul marginii de intrare. Și apoi mă actualizez. Deci, singurul lucru care rămâne aici este să facem exact algoritmul lui Dijkstra. Dar, în loc să actualizăm prin însumarea lungimii marginilor, actualizăm folosind această formulă. Și, în esență, totul rămâne la fel. Așa de convenabil, am rămas fără timp. Deci nici nu va trebui să-l amestec pe acesta pe tablă. Vă las să faceți asta acasă. Dar, de fapt, cred că explicația din materialul scris este destul de evidentă pentru această problemă. Deci probabil că este la fel de bine.