bine, bine ai revenit la 6006, vom avea o sesiune cu probleme, vom face o analiză a testului 2, suntem într-o cameră mult mai mare azi, așa că am puțin mai mult spațiu pe tablă, așa că vreau doar să trec prin ceea ce se întâmplă pentru a fi acoperit mai întâi la examen, în afara domeniului de aplicare, uh, testul, un material va fi un joc corect pentru acest test, dar nu este ceva care va fi subliniat în mod explicit sau ceva de genul acesta, trebuie să știți că știți când stocăm graficul structuri de date pe care le pot atinge anumite limite de timp și și și așa ceva, dar ne vom concentra cu adevărat pe grafice cele șase prelegeri pe care le-am avut despre grafice, două despre algoritmi grafici neponderați și cele patru pe care le-am avut pe algoritmi grafici ponderați au acoperit materialul care a fost acoperit în cele două seturi de probleme, uh, set de probleme cinci și setul de probleme șase, acum, de obicei, doar acest material acoperă trei seturi de probleme în valoare de material uh acest termen acoperă două seturi de probleme în valoare de de material, așa că ține cont de asta atunci când studiezi și vrei să te uiți înapoi la materialul anterior, bine, în general, există o mulțime de probleme grafice despre care am vorbit despre cum să le rezolvi, există într-adevăr un număr mic de algoritmi de grafic, dar pot rezolva o mulțime de probleme diferite, bine și așa că am văzut doi algoritmi pentru a rezolva problema accesibilității graficului o singură sursă uh, ce este accesibil de la mine, uh și pot căuta doar o componentă conectată a graficului meu de la mine și componenta conectată de la mine este de fapt mărginită superioară asimptotic de numărul de muchii din graficul meu, deoarece un arbore de acoperire al componentei mele are cel puțin sau are v plus o muchii drepte și, deci, numărul de vârfuri la care pot ajunge este delimitat superior de numărul de muchii din graficul meu, oricum asimptotic, uh, grafic, apoi am vorbit despre explorarea unui întreg grafic, chiar dacă este deconectat nu neapărat de la o sursă, doar doar atingând fiecare vârf dintr-un grafic, desigur că putem doar știi să atingem fiecare vârf dintr-un grafic Graficul din dreapta Pot să mă uit la reprezentarea adiacenței graficului meu și să o parcurg, dar acesta este într-adevăr că încercăm să explorăm întregul grafic, poate să numărăm câte lucruri sunt accesibile unul de la celălalt în grafic și asta este ceea ce am avut un am vorbit despre explorarea unui grafic și numărarea dimensiunii componentelor conectate într-un grafic într-un grafic neponderat corect și am putea face acest lucru prin bfs complet sau dfs complet, practic este să punem o buclă în jurul unuia dintre acești algoritmi de accesibilitate a graficului pentru a explora un întreg grafic prin Explorând componentă cu componentă și când am terminat cu o componentă, găsesc un vârf pe care nu l-am atins până acum și îl explorez din nou, bine și care încă devine timp liniar în graficul v plus e, atunci am avut uh tipuri speciale de grafice direcționate grafice direcționate grafice aciclice uh pe care le-am putea folosi, am demonstrat această proprietate, dacă am rula dfs full dfs pe acel grafic, am putea obține de fapt un fel topologic de acel grafic, practic, o ordonare a vârfurilor din grafic astfel încât toate muchiile să meargă într-o direcție cu cu privire la acea ordonare, ca toate înainte în acel drept de ordonare și am putea folosi asta pentru a detecta ciclurile într-un grafic direcționat, doar privind ordinea de sortare topologică și văzând dacă, dacă ne uităm la timpul de terminare, ordinea inversă a timpului de terminare a dfs și doar verificând dacă a fost un sortator topologic, deoarece orice margine din spate ar corespunde unui ciclu din graficul nostru, deoarece propunerea a fost că, dacă graficul nostru ar fi aciclic, efectuarea acestei proceduri ne-ar oferi un raport topologic în regulă, atunci am avut un algoritm bellman ford că a reușit să detecteze și să găsească cicluri negative de greutate în graficul nostru așa cum l-am prezentat în prelegere și, dar în mod normal, ne-am concentrat pe aceste două probleme, cele mai scurte căi cu o singură sursă și unele un pic toate perechile cele mai scurte căi cele mai scurte bine, uh, mai întâi în contextul neponderat și apoi în contextul ponderat pentru majoritatea cursurilor, bine, așa că hai să trecem la ce anume au fost acei algoritmi cu cele mai scurte căi cu sursă unică am avut pentru mine pentru a crește în general aici prima restricție este deja bfs rezolvă cele mai scurte căi neponderate în timp liniar în contextul neponderat, totul este bine, dar pentru graficele ponderate, indiferent de ponderi, dacă am avea această proprietate foarte puternică pe grafic, că proprietatea că graficul nu a avut cicluri direcționate atunci am putea obține asta în timp liniar prin relaxarea dag și apoi, pentru graficele generale, am avut aceste restricții crescătoare sau descrescătoare asupra greutăților, mai întâi, am avut restricția că au fost neponderate și că aceasta este constrângerea bfs sau că nu sunt negative, aceasta este constrângerea dijkstra. iar dacă nu avem constrângeri care să ne dea bellman ford și acestea cresc în timp, în general, vrei să alegi un algoritm care este mai sus pe această listă, dar uneori algoritmii mai sus pe această listă nu se aplică corect dacă tu dacă la un test vii la un grafic pentru care nu este un dag, dar folosești relaxarea dag care nu mai este un algoritm corect corect și astfel vei obține mai puține puncte decât dacă se întâmplă să folosești un algoritm ineficient care este corect, așa că dacă doar ori de câte ori am văzut căile cele mai scurte, am folosit bellman ford corect, este cel mai lent lucru care probabil va fi un algoritm corect, nu va fi neapărat cel mai eficient algoritm, dar veți obține mai multe puncte, deoarece este un algoritm corect, atunci dacă aplicați un algoritm corect. un algoritm mai rapid care nu se aplică problemei dvs., deoarece nu o va rezolva corect, are sens, și apoi, în ultima prelegere pe care am avut-o, am vorbit despre toate perechile de cele mai scurte căi și despre rularea unei singure surse pentru doar căile din fiecare vertex este destul de bun în majoritatea circumstanțelor, nu știm cum să facem mult mai bine pentru multe dintre acestea și apoi Johnson ne oferă, practic, în această ultimă linie a graficului nostru, restricții și restricții de greutate, uh, unde este Bellman Ford chiar acolo putem de fapt, obțineți o viteză de peste de v ori bellman ford uh, prin fel de două trucuri, corectați corect găsirea dacă graficul are cicluri negative de greutate și dacă nu, atunci există o reponderare a acestui grafic, astfel încât toate greutățile nu sunt negative, dar cele mai scurte căi sunt păstrate și astfel putem folosi dijkstra v times și obținem în schimb acel timp de rulare ok, deci asta este doar o prezentare generală a conținutului pe care l-am acoperit până acum, vreau doar să mergem la dreapta, doar o scurtă prezentare generală a ceea ce acești algoritmi fac de fapt relaxarea, uh, știi, găsește o ordine topologică a lucrurilor folosind dfs uitându-ne la ordinea inversă a timpilor de sfârșit, dovediți că acesta este un top o ordine topologică inversă și apoi relaxăm marginile înainte în acea ordine, deoarece să știm că am găsit cea mai scurtă distanță de cale până la tot ce avem înainte și folosim acel invariant pentru a demonstra că acesta o construiește în timp liniar bfs explorează lucrurile în niveluri, crescând imediat numărul de margini pe măsură ce ieșim și doar procesez toate sunt la același nivel în același timp și dijkstra generalizează această noțiune spunând bine că nu știu toate lucrurile care sunt la același nivel în sine de la fr în care merg, dar pot folosi un inteligent Utilizarea unei structuri de date Găsește următoarea Ar trebui să o procesez într-un fel de ordine de relaxare topologică pentru a găsi căile cele mai scurte atunci când ponderile sunt nenegative, deoarece într-un anumit sens știu că, odată ce am ajuns la lucruri de la o distanță scurtă, nu voi trebuie să-și actualizeze din nou distanța, acesta este un fel de invariant pe care îl avem cu dijkstra și apoi bellman ford în esență duplică graficul nostru, astfel încât fiecare nod să corespundă atingerii unui vârf folosind cel mult un anumit număr de muchii și apoi acel grafic duplicat este un dag și putem rula dag relaxare, așa că aceasta este ideea de bază a tuturor acești algoritmi, uh, atunci când abordez problemele la un test, uh, sunt câteva lucruri de care trebuie să ținem cont, sunt cam două lucruri de care trebuie să ne îngrijorăm când suntem te uiți la o problemă de grafic din această clasă, primul lucru este că s-ar putea să nu văd un grafic în problema mea, adică la testul 2, știi că va fi un grafic în problema ta, pentru că acoperim algoritmi de grafic în acest sens. test, dar, în general, unele dintre problemele de cuvinte pe care le-ați văzut în seturile dvs. de probleme, nu există nici un grafic definit pentru dvs., vă oferă o serie de lucruri sau un set de lucruri sau știți unele conexiuni între unele lucruri corecte și care ar putea fi un grafic pe care vrei să-l faci, dar definirea unui grafic este un aspect important al rezolvării problemei, care nu este neapărat ceva pe care l-am acoperit în prelegere, nu am subliniat atât de bine în prelegere, dar este ceva care ai trebuit să faci cu seturile tale de probleme și ceva care va apărea corect în chestionar, așa că partea din acesta este un context de modelare, poți să te uiți la o situație reală din lumea reală sau poate nu chiar atât de lumea reală, dar la un context non-matematic corect și Încercați să abstractizați, puneți-o în limba acestei clase, matematica acestei clase face un grafic, astfel încât rezolvarea uneia dintre problemele pe care știți să le rezolvați să poată rezolva în mod adecvat problema cuvântului pe care v-am dat-o corect, aceasta este o modelare parte, așa că sugerez întotdeauna când vedeți o problemă cu un cuvânt la testul 2 sau la problema dvs. așezată corect, uh, vedeți dacă puteți afirma clar o problemă abstractă legată de faptul că, dacă ați ști răspunsul la acea problemă abstractă, ați putea rezolva cu ușurință problema cu cuvintele. poate face puțin mai ușor decuplarea complexității cuvântului problemă chiar atunci nu trebuie să vă gândiți la nu știu, uh, știți diferite personaje ciudate în care venim în contexte ciudate și sunt condiții ciudate, corect dacă poți mapa asta doar la un grafic cu un anumit cu anumite proprietăți și să rezolvi o problemă abstractă pe acel grafic, ar putea fi mai ușor să te gândești și să aplici materialul din această clasă, astfel încât să nu-ți faci griji. Trebuie să-mi amintesc că drumurile sunt conectate la alte cinci lucruri sau trebuie să vă amintesc, poate vi se dă drept intrare un grafic rar sau ceva de genul acesta corect, la care este puțin mai ușor de gândit atunci când aplicați acest material, bine și deci conversia problemei dvs. într-o problemă cu cea mai scurtă cale sau găsirea unui ciclu sau găsirea unei sabie topologice sau a unei componente conectate sau a unui ciclu de greutate negativ sau în oricare dintre aceste lucruri corect vă poate face mai ușor să vă gândiți la uh, nu este ca și cum material fundamental din această clasă, asta este super uh, despre care trebuie să ținem prelegeri, dar este foarte important pentru tine când te afli în lumea reală și te uiți la probleme să poți face acea transformare dintr-un context non-matematic într-un matematică îmi place să mă gândesc la asta ca la o parte de modelare a problemei, dar în general, odată ce ai acea problemă abstractă frumoasă, atunci, în general, s-ar putea să ai un grafic, dar s-ar putea să nu fie graficul pe care ești singurul grafic pe care îl vrei când rezolvați corect această problemă, acesta ar putea fi graficul de intrare pe care îl aveți, dar, în general, o mulțime de trucuri ale acestui lucru nu sunt modificarea algoritmilor pe care v-am dat-o dacă încercați să modificați algoritmii pe care i-am dat. că am petrecut cursuri întregi pentru a demonstra corectitudinea lor și lucruri de genul acesta poate că nu este ceva ce vrei să faci la un examen, pentru că atunci vei scrie pagini de derivare și vei demonstra că acești algoritmi funcționează, în special, această unitate este mult mai multe despre haideți să reducem la o cutie neagră foarte puternică pe care v-am arătat cum funcționează și așa că, pentru că acesta este cadrul aici, modul în care introducem complexitatea în probleme este de a face graficul să nu fie evident în ceea ce se presupune că pentru a aplica corect și astfel graficul pe care ți-l oferim ca intrare poate fi diferit de graficul pe care vei dori să-l folosești pentru a rezolva problema și iată câteva strategii pe care le poți folosi pentru a modifica un grafic, cum ar fi dacă, uh, dacă Doriți să stocați starea pe măsură ce traversați corect acest grafic, puteți extinde numărul de vârfuri din graficul dvs. pentru a urmări starea în care mă aflu pot avea un vârf diferit pentru fiecare stare posibilă în care aș putea fi la acel vârf bine, știi că în ședința ta cu probleme ai avut tipul ăsta care bea când a ajuns la baruri corect și sau la fiecare a treia oară și trebuie să-ți amintești de câte ori au trecut de când am fost într-un bar corect sau am băut la bar. o bară și, astfel, puteți duplica vârfurile pentru a putea stoca acele informații un alt lucru dacă dacă doriți să căutați din mai multe locații în același timp sau să căutați în mai multe locații în același timp, puteți simula asta fără Dacă trebuie să rulați un algoritm de mai multe ori, puteți simula că adăugând un nod auxiliar un nod suplimentar în graficul dvs. cu margini la acele surse sau la acele chiuvete și rulați un algoritm de calea cea mai scurtă dintr-o singură sursă din acel super-nod pe care îl numim uneori uh, pentru a obține performanțe mai bune, este un fel de eficiență, adăugăm eficiență modificându-ne graficul pentru a se potrivi cu algoritmii pe care știm că-i rezolvă eficient și apoi, ultimul lucru, poate că ajută să preprocesăm graficul într-un fel la corectarea unor margini în graficul pe care ți l-am oferit, s- ar putea să fie interzis sau ar putea fi necesar să fie parcurs într-o direcție mai degrabă decât în alta, chiar dacă declarația problemei pare oarecum că ar trebui să poată fi traversate în orice direcție în dreapta și făcând această preprocesare a graficului ar putea însemna că vă împărțiți graficul în graficul conectat într-un set de componente deconectate pe care trebuie să le găsiți sau faceți un grafic nedirect face un grafic ciclic drept aciclic sau tăiați o parte a graficului pe care nu doriți să o explorați. nu vreau să mă ating de drumul meu de a ajunge într-o locație corectă, așa că toate acestea sunt strategii cu adevărat comune pe care le cunoașteți, uh, duplicarea graficului, adăugarea de vârfuri sau muchii auxiliare la grafic, nu știu contextul în care adăugăm marginile este o întrebare interesantă și apoi preprocesarea unui fel de filtrare a graficului sau transformare într-un fel pentru a-i oferi proprietăți care ne vor permite să rezolvăm problema mai bine, deci orice întrebări despre strategiile de rezolvare a problemelor pe care le avem sau despre conținut tipul de conținut de bază al acestei clase este un fel de prezentare generală a materialului de tip prelegere în care nu aplicăm neapărat acest material în prelegere, restul acestei sesiuni de revizuire a testului va fi pe aplicarea acestui material la unele uh a test de la un trimestru anterior, unele dintre aceste probleme, bine, deci da, care sunt câteva modalități comune în care oamenii pierd puncte, asta este un lucru grozav, îl voi adăuga la notițe atunci când postăm lucruri atât de comune încât oamenii pierd puncte în asta unitate atunci când rezolvă probleme vi se pune o problemă cu un cuvânt și nu definiți un grafic corect, e la fel de ușor ca să începi să rezolvi presupunând că știm despre ce grafic vorbești când graficul implicit din problemă poate fi sau nu corect, dar nu există nici un grafic definit în problemă, așa că trebuie să definiți un grafic în problemă, așa că acesta este primul lucru, al doilea lucru este de multe ori, este cu adevărat util ca strategie atunci când tu construiești acel grafic spune-ne câte vârfuri și muchii sunt în el spune-ne dacă spune-ne dacă este aciclic corect spune-ne care sunt greutățile pe fiecare muchie dacă nu ne spui aceste lucruri, este foarte greu pentru noi să ne bazăm pentru a- ți judeca aplicarea de algoritmi bazați pe acel grafic pentru că știți dacă există redundanță acolo, chiar dacă definiți pentru fiecare vârf din graficul meu original, am 10 vârfuri sau bla bla corect și poate adăugați un super nod sau toate aceste lucruri pot fi Este dificil pentru noi să urmărim câte lucruri sunt, așa că faceți contabilitatea pentru noi, elevii voștri vor fi mult mai fericiți și așa că greșelile obișnuite nu au definit un grafic, nu vă specificați graficul complet și apoi uh, nu uh, aș face De asemenea, sugerez ca, în loc să aplicați doar un algoritm unui grafic, să spuneți clar problema pe care o rezolvați în graficul din dreapta, vreau să rezolv această problemă, deoarece v-am oferit un număr de moduri de a rezolva problema pe care o rezolvați pe graficul din dreapta. și dacă se întâmplă să alegeți algoritmul greșit, atunci poate că este ca și cum ați separa problema de implementarea dvs. a modului în care ați rezolvat acea problemă, poate vă poate ajuta să obțineți câteva puncte pentru a afirma problema pe care o rezolvați, chiar dacă alegeți greșit sau ineficient. modalitate de a rezolva corect, astfel încât să poată ajuta cu adevărat la decuplarea uh uh unele dintre lucrurile pentru care vom acorda puncte în această clasă corect, așa că, de obicei, ceea ce suntem, despărțim rubrica grafică despre notare ați descris corect un grafic l-ați modificat într-un mod care să vă ajute să rezolvați problema ați identificat o problemă pe care trebuie să o rezolvați cu privire la acest lucru ați folosit un algoritm corect pentru a o rezolva ați analizat timpul de execuție de obicei implică dimensiunea graficului meu nu prea mare și care este timpul de rulare bazat pe acel grafic și apoi argumentul corectitudinii din această unitate este, practic, ca și cum am construit un grafic care are proprietăți, astfel încât cele mai scurte căi din acest nou grafic să corespundă cu orice ar fi ceea ce vreau în problema inițială, corect, o afirmație care leagă problema pe care o rezolvi în enunțul problemei tale cu problema pe care o rezolvi pe graficul tău, este o afirmație foarte bună să trebuiască să adună corectitudinea, dar deoparte din acea afirmație, te bazezi în mare parte pe corectitudinea algoritmului, așa că nu trebuie să faci mare lucru din punctul de vedere al corectitudinii, bine, dar a uita să analizezi timpul de execuție este un lucru mare, bine, așa că acestea sunt o grămadă de sfaturi. O să le adaug la sfârșitul acestui diapozitiv după ce după prelegere o întrebare grozavă orice alte întrebări în regulă, să trecem la rezolvarea problemelor în regulă, așa că aceste probleme pe care le vom rezolva sunt de la testul de primăvară 18 doi, ușor modificat dar uh, știi că le vom parcurge pe rând, așa că prima problemă pe care o avem, avem o imagine cu pătrate alb-negru, așa că este ca o grilă de pixeli, te gândești la ea ca și cum o știi. bitmap pe computerul dvs. corect și ceea ce spunem este că fiecare pixel alb este conținut într-un blob, bine, dar ce este un blob, nu știu bine, vă dau o reprezentare implicită a definiției a ceea ce un blob înseamnă două pixelii albi sunt în același blob dacă împart o margine a rețelei, bine, așa că acest fel îmi spune că acest grafic are o margine dacă acești pixeli sunt adiacenți, ambii sunt albi, asta înseamnă, dar o parte interesantă despre asta definiția este că este un fel de tranzitiv, corect dacă am un pixel alb care împarte o margine cu un pixel alb a care împarte un uh, hai să începem să scriem lucruri pe tablă, probabil că în loc să vă vorbesc corect, avem amabili de o grilă de pixeli aici, bine și nu știu cum să fac asta cu tabla pentru că este alb versus negru, cred că trebuie să colorez lucrurile albe, toate sunt albe în regulă, așa că tipii ăștia sunt în aceeași pată, drept pentru că au o margine acești bărbați sunt în același blob, bine, dar pentru că împărtășesc o margine în grila de pixeli acești bărbați sunt, de asemenea, în același blob, deoarece dacă aceștia sunt în același blob și aceștia sunt în același blob, există un argument de tranzitivitate aici corect, acest tip trebuie să fie în același blob cu acel tip și apoi spune că pixelii negri nu sunt în niciun blob, bine și așa că mi se dă o matrice n cu m. Nu-mi amintesc niciodată care vine primul, dar avem dimensiuni de acest lucru ca n cu m, deci avem de n ori m pixeli uh și așa că descriem uh, în esență, într-un algoritm de timp liniar pentru a calcula numărul de blob-uri din imagine de ce spun timp liniar este pentru că pentru fiecare pixel din grila mea Trebuia să vă dau o specificație dacă era alb sau negru corect și deci da, dacă ți-am dat naiv introducerea acestui algoritm cu un cuvânt pe unul dintre acești pixeli care ar fi dimensiunea de intrare a dreptului meu și așadar, chiar dacă aceasta are un aspect drept pătratic, dimensiunea reală a intrării este ceea ce definim drept drept liniar și, prin urmare, căutăm un algoritm de timp liniar pentru a număra numărul de blob-uri din imagine, deci ce este aceasta este puțin subspecificată ca problemă Recunosc, urăsc să recunosc că am fost implicat în această clasă la acel moment, dar ideea aici este că dacă aceștia au un avantaj, atunci totul este observația de aici dacă doar desenez această imagine, observ că orice fel de asta este accesibil prin conexiuni albe albe vor fi în același blob, așa că acesta este un blob și acesta este un blob și acesta este un blob și acesta este un blob, dar nu există nicio cale aici, această parte neagră nu face parte dintr-un blob acum de fapt, nu există nimic în această specificație care să nu spună că nu am putea ca aceste lucruri să fie în același blob, bine, așa că este puțin confuz, poate o sursă de eroare, că există o sursă de eroare pe care am avut-o când am citit această problemă după câțiva ani, um, dar știi că atunci când te uiți la o problemă, dacă dacă totul ar putea fi doar în același blob, atunci doar returnezi unul și această problemă nu este atât de interesantă, așa că modul corect de a interpreta această problemă, vreau să spun. n-ar avea nevoie de n ori de m timp, aș putea spune una corect, așa că, într-un anumit sens, aș dori să existe ceva interesant în această problemă, uh, și a avea aceste lucruri care nu sunt accesibile unul de la celălalt să fie bloburi diferite este un fel de ceva mai interesant din punct de vedere algoritmic și, deci, ce este acesta, atunci, aceasta este doar o grilă de pixeli, există adiacente, există conexiuni între pixeli, dar în special îmi pasă doar de conexiunile dintre pixelii albi, greu de desenat aici, dar această componentă are un grafic care arată ca acesta, această componentă este un singur vârf, aceasta este o muchie aici și aici este un singleton acolo și dacă ar fi să construim acest grafic, am avea un grafic neponderat, astfel încât numărul de blob-uri din imaginea mea ar fi numărul de componente conectate din acest grafic, vedeți corect cum relaționez lucrul pe care îl cer în problemă cu o proprietate a unui grafic pe care îl construiesc bine, așa că asta este cu adevărat partea cheie a argumentului corectitudinii ceea ce căutăm este ca tu să faci un fel de afirmație care leagă cele două, altfel doar construiești un grafic și nu am idee ce faci cu acel grafic, trebuie să-mi spui o parte din el. despre comunicarea cu noi, uh, deci cum construiesc bine acest grafic, pot doar să parcurg toți pixelii, să mă uit la cei patru vecini ai săi cel mult și dacă acele lucruri pe care le împărtășesc sunt ambele albe, atunci adaug o margine pe care o avem În esență, vom avea un grafic, vom construi un grafic, asta ți-am spus să faci asta bine, deci ce este v aici, atunci uh v este un vârf pentru fiecare pixel alb corect și pot să spun de la început Pot doar să parcurg toate lucrurile să găsesc toate nodurile albe, poate le identific în mod unic după coordonatele lor x y din aceasta în această grilă, este bine, așa că acum am toate nodurile și acum vreau să văd care sunt marginile pe care le pot bucla prin pixeli din nou și doar uită-te la cele patru posibile adiacene ale sale, vezi dacă vreuna dintre ele este albă. Ține acea margine în acest set, astfel încât marginea este oricare doi pixeli albi care împărtășesc [Muzică] o margine în regulă, așa că pot construi ambele lucruri în acest set în ordinea de n ori m pentru că există cel mult atâtea vârfuri, doar le parcurg și marginile pentru fiecare pixel, verific doar un număr constant de lucruri și le adaug la un set, astfel încât numărul de margini de dimensiunea lui numărul de vârfuri din graficul meu este de cel mult n ori m, iar numărul de muchii este de cel mult n ori m ori patru dreapta este mărginit de sus, deoarece acesta este numărul de adiacente pe care le am în grafic, bine, probabil că puteți obține o mai bună legat din punct de vedere al numărului de vârfuri corect, poate fi de cel mult v ori patru corect, dar asta este puțin mai puternic, nu contează cu adevărat că încercăm să ajungem în ordinea de n ori m legat în timp, așa că orice este bine aici, așa că este graficul pe care îl construim și apoi putem rula bfs complet sau dfs complet am identificat un grafic pe care l-am identificat și dorim să numărăm numărul de componente conectate din graficul meu, așa că ideea corectă numără conectați componentele conectate și apoi, de exemplu, folosind complet bfs sau full dfs corect, nu aș vrea să scrieți ambii acești algoritmi acolo, dar atunci când scriem soluțiile noastre, vrem ca acestea să acopere spațiul soluțiilor pentru studenți și așa că de obicei îl vom menționa, trebuie doar să menționați una dintre ele și pentru că acestea se desfășoară în timp liniar, aceasta se întâlnește și de n ori m, deci toate aceste lucruri sunt de n ori m și suntem de aur orice întrebare la această întrebare, da ce fel de lucruri ai căuta pentru a te asigura că este corect deci, atunci când scriu, ți-am descris algoritmul și întrebarea este ce fel de lucruri trebuie să notez când demonstrez sau când argumentez timpul de rulare al algoritmului meu și susțin corectitudinea corectă pentru timpul de rulare în cea mai mare parte, verificați dimensiunea graficului dvs., starea corectă pentru mine care este dimensiunea graficului dvs. aici, în acest caz, este ordinul de n ori m și apoi precizez care este timpul de rulare algoritmul pe care îl am este aplicat dreptului respectiv și, prin urmare, pentru că uh full bfs rulează în o din v plus e timp corect, este util să scriem acest lucru, deși corect nu este în termenii variabilelor noastre originale ale problemei, este util să scriem acest lucru jos, astfel încât, dacă greșesc atunci când conectez aceste variabile, uh, știi că îți arăți pașii și deci, dacă greșești aritmetic, te putem da puncte, dar pentru că dimensiunea numărului de vârfuri din grafic este de n ori m numărul de muchii este de n ori m le adun împreună este încă de ordine de n ori m și asta ar fi suficient pentru un argument al timpului de rulare și apoi am spus pentru corectitudine uh, majoritatea corectitudinii acestui algoritm se bazează pe faptul că acest lucru numără corect componentele conectate în graficul meu, observația cheie asupra unei probleme de cuvânt pe care i uh uh sau chiar o problemă de transformare a graficului este că proprietatea pe care o doriți a graficului original pentru problema originală îi corespunde Lucrul pe care îl rezolvați într-un nou grafic pe care l-ați făcut corect și, deci, aici un argument de corectitudine pe care l-aș căuta și că am putea permite câteva afirmații mai slabe este că numărul de blob-uri din imagine corespunde numărului de componentele conectate din acest grafic pe care le-am făcut bine, asta este cu adevărat tot ce are nevoie, dar aș dori o conexiune între acele valori, bine acum, de ce ai construi acest grafic și ai găsi componente conectate dacă asta dacă nu ai face asta nu a fost ceea ce credeai tau, nu stiu, dar este real, este bine cand comunici pentru a te asigura ca este foarte clar ca de aceea asta este uh, vreau sa spun ca ar trebui sa fii capabil sa argumentezi de ce sunt aceste lucruri uh aceasta este o componentă conectată, ai putea spune ceva de genul pentru că orice lucru accesibil este în același blob sau ceva de genul, bine, deci asta e problema unu, am primit aceste plăci mecanice frumoase, așa că asta e problema, una, două, este puțin ciudată, bine, a fost Reformulat puțin din primăvara 18, astfel încât să pot sublinia alte caracteristici ale acestui grafic, care ni se oferă o conexiune, astfel încât conectat este în aldine, astfel încât aceasta ar putea fi o proprietate importantă a graficului nostru pe care încercăm să o facem să vă comunice un grafic nedirecționat conectat cu ponderi strict pozitive la dreapta, astfel încât acestea să fie mapate la numerele întregi pozitive unde e este de aceeași dimensiune cu v dreapta, astfel încât dimensiunea lui e este de aceeași dimensiune cu dimensiunea lui v dreapta, așa că am Același număr de muchii ca și vârfuri, încercăm să găsim un algoritm de ordine v timp pentru a determina o cale de la un vârf s dacă la un vârf t cu greutate minimă bine, deci care este primul lucru pe care l-am observat că am observat că pe acest lucru am Avem o problemă cu graficul 2 avem un grafic este nedirecționat este conectat are această proprietate ciudată că v este egal cu e sau e este egal cu v și ponderile sunt pozitive, bine și cerem o singură pereche de drumuri cele mai scurte pe care le dorim uh o cale cea mai scurtă cale o cale cea mai scurtă între două vârfuri acum, dacă doar ni se oferă acest grafic și vrem să rezolvăm această problemă, o modalitate foarte ușoară de a face asta ar fi să spunem să rulăm dijkstra pe grafic chiar așa este un grafic are doar greutăți de margine pozitivă o direcție pe acest grafic cât timp durează dijkstra pentru această idee de grafic una corectă care este problema cu aceasta se aplică corect suntem în contextul greutăților de margine nenegative putem găsi o singură sursă căi de la s la orice altceva din grafic în utilizarea dijkstra se aplică este un algoritm corect care este dificultatea acestui algoritm lent prea lent corect acel algoritm ar rula în o din v log v plus e și în acest caz acestea sunt aceleași deci acesta este asimptotic mai mic decât acesta rulează în v log v, deci suntem puțin dezamăgiți, suntem dezamăgiți de un factor logaritmic în timpul nostru de funcționare, dar știți că acesta ar fi cel puțin un algoritm corect, știți dacă de fiecare dată când vă apropiați o problemă la examen și vezi un algoritm polinom cu adevărat stupid, care încă îți rezolvă problema corect, ai putea la fel de bine să scrii asta pe o linie, nu te doare atât de mult să scrii asta. pentru că este posibil să vă acordăm puncte pentru acest drept, dar acest lucru, dar la examen, observați de ce nu este suficient corect observați că oh, acest drept, acest lucru este v observați că acesta nu este timpul limită pe care îl căutăm noi trebuie să exploatez ceva diferit, bine acum, acesta nu pare că acesta este un context ponderat, avem căi ponderate, nu pare să fie într-una dintre condițiile în care putem obține un algoritm de calea cea mai scurtă sursă liniară ponderat în timp. în special folosind bfs, am văzut o transformare în care, atâta timp cât suma greutăților tale a fost liniară în dimensiunea combinatorie a graficului tău, am putea folosi bfs făcând fiecare muchie o grămadă de muchii nedirecționate, nu avem asta în acest context și acest grafic este nedirecționat, adică conține cu siguranță cicluri, așa că nu putem folosi cele mai scurte căi, deci cum naiba putem face asta bine Cum arată acest grafic aici, voi arunca o privire la această condiție v e egală cu e bine, deci cum arată acest grafic este conectat și este v plus e bine câte muchii are un copac v minus una dreapta, deci, într-un sens, dacă un arbore este, este cel mai mic număr de muchii pe care îl puteți avea într-un grafic conectat, deci acesta are o margine mai mult decât un copac, așa că într-adevăr, așa cum arată graficul nostru g este un fel de copac și undeva avem o margine suplimentară în acest grafic, chiar este un copac plus o margine suplimentară, așa este graficul nostru e bine, să facem un pas înapoi dacă tocmai am avut un copac și aș fi cântărit un grafic ponderat aici nedirecționat și ponderile sunt toate pozitive dacă dacă oricare dintre ponderi ar fi negativă, cum aș putea rezolva această problemă bine, fiecare margine este accesibilă de la fiecare vârf, pot merge la acea margine și să traversez o greutate negativă înainte și înapoi, iar calea mea cea mai scurtă ar fi infinită pentru toate vârfurile noastre, ceea ce nu este cazul pe care îl avem aici, avem ponderi doar pe marginea pozitivă, ceea ce înseamnă că cele mai scurte căi sunt simple și de fapt există o singură cale simplă între orice pereche de vârfuri dintr-un copac. În principiu, există un singur lucru pe care îl pot face și, de fapt, dacă aș lua dacă asta a fost s și asta a fost t t asta e un x ce fac bine dacă doar a rulat orice scurt neponderat, adică algoritm de accesibilitate, aș obține un arbore corect, un arbore bfs sau un arbore dfs corect, ar vizita nodurile într-o anumită ordine, acum, de fapt, într-un arbore, trebuie să scot un arbore care conectează toate nodurile corect și asta ar fie acest arbore corect și, într-un fel, căile pe care le-am primit de la bfs sau dfs în acest grafic ar fi exact cele mai scurte căi pe care ar trebui doar să merg și apoi să adun toate greutățile marginii căii pa de-a lungul marginilor care au sens, bine, deci bfs sau dfs în contextul neponderat îmi pot oferi cea mai scurtă cale în contextul ponderat, deoarece există o singură cale simplă în acest grafic, dar avem o complicație aici, care nu este întrebarea pe care o punem, avem un avantaj suplimentar și acum au o proprietate în care nu există doar o cale simplă către t, ar putea exista două căi simple, aș putea merge în acest sens în jurul ciclului sau ar putea merge în acest sens în jurul ciclului, deci este o complicație, dar există un singur ciclu dacă t este peste aici există o singură cale corectă, așa că dacă există o singură cale, voi fi de aur, dar dacă practic se poate ajunge la ciclul dintre aceste două lucruri, aș putea avea două căi simple, aceasta este dreptul de proprietate pe care avem cel mai apropiat vârf, deci acesta este ciclu exact, există un ciclu aici dacă acesta este cel mai apropiat vârf de s și acesta este cel mai apropiat vârf de t pe ciclu, atunci aș putea lua oricare dintre căile în jurul ciclului pentru a ajunge de la unul la altul și asta îmi oferă cele două căi ale mele, dar asta calea și această cale dreapta acestea sunt complet disjuncte cu muchia dreapta, cu alte cuvinte, orice cale simplă de la s la t dacă i dacă găsesc acest vârf care trece prin aici, poate folosi doar una dintre aceste muchii drept pentru că nu pot, nu pot veni înapoi la acest vârf odată ce intru aici trebuie să ies într- o direcție și nu mă pot întoarce corect, așa că este doar una dintre aceste două margini, așa că ideea din spatele acestui algoritm este că voi găsi ciclul sau în special, voi găsi acest lucru pe primul loc pe ciclu, găsiți cele două margini de ieșire aici, eliminați una și apoi căutați în arbore, găsiți practic cea mai scurtă cale prin rularea unui algoritm nedirecționat, adică un algoritm de accesibilitate neponderat care îmi va oferi o cale înapoi la f singura cale simplă din acel copac corect, scap de această margine și o fac o dată și o fac din nou fără această margine, așa că asta e ideea algoritmului meu, bine, așa că cum pot face brad, așa că mai întâi trebuie să găsesc s prime cum pot face asta bine, nu știu ce este această margine, dar dacă aș rula uh un uh uh un algoritm neponderat de calea cea mai scurtă, cum ar fi bfs sau dfs aici, aș primi un arbore chiar la marginea Graficul meu nu va fi în arborele meu ceva de genul aici, chiar cea mai scurtă cale către asta, așa că mă uit prin I rulez b, așa că ideea algoritmului doi doi mai întâi găsesc prim-ul bine și pot găsi prim cu rulare Nu cunosc o singură sursă calea cea mai scurtă neponderată uh cred că rulați accesibilitatea unei singure surse neponderate de la s folosind bfs sau dfs pentru a explora un arbore al graficului meu, atunci o margine nu este în arborele graficului meu care va exista pe ciclu, un fel, prin definiție, este contra că se conectează două părți ale arborelui meu acum pot să mă uit la acele două căi de aici și ultima din care sunt în comun de la s va fi punctul meu de despicare principal, este cea mai apropiată de sursa mea care se află pe ciclu corect pentru că am construit acest ciclu aici, bine, așa că pot găsi marginea u v nu în arborele părinte corect, deci poate acesta este u v corect nu în arborele părinte și apoi găsiți ultimul vârf comun în căile de la s la u și de la s la v bine asta o să-mi dea primul meu bine și pot face asta, adică acestea sunt fiecare de dimensiune liniară și mă pot uita doar la prefixul lor. prim dreapta, este primul chiar aici, odată ce am primul, știu care sunt muchiile atunci când diverg, elimin una dintre acestea din grafic, fac din nou același algoritm pentru a găsi o cale către t și fac din nou același algoritm pentru a găsi calea către t și văd care dintre ele este mai scurtă, asta este, sunt doar două și deci verific sau ar putea fi aceeași cale, caz în care t-ul meu este de fapt înainte de pornirea ciclului meu are sens, așa că asta e ideea, uh, ultimul lucru este să elimini o margine din prima. Nici măcar nu trebuie să fiu pretențios în privința asta, are gradul trei. Pot doar să rulez căi unice sortate pe toate și să le iau corect pentru a mânca elimina fiecare muchie de la v at de la s prim uh elimina hai sa pentru fiecare muchie de la s eliminam si rulam ssr de la s ok si una dintre caile de acolo la t va fi cea mai scurta calea mea cea mai scurta din graficul original pentru ca nu poate folosi uh mai mult de două dintre acele margini, aceasta este afirmația în regulă și aceasta rulează în timp liniar, pentru că ceea ce fac este că rulez accesibilitatea unei singure surse o dată și poate de încă două ori sau de încă trei ori de un număr constant de ori pe un grafic care are dimensiunea v corectă și această găsire a prefixului ia, de asemenea, doar ordinea v și, deci, am terminat bine orice întrebări despre această problemă nu, nicio întrebare, bine, vom trece la uh ce e mai sus, există o da, există un indiciu în titlu, de fapt, versiunea originală despre această problemă a spus în loc de această specificație e e equals v, a spus că există un singur ciclu în grafic, dar este în contextul ciclurilor nedirecționate, spre deosebire de ciclurile direcționate, care este de obicei despre ce vorbim în această clasă, corect spunem că există un negativ ciclu de greutate margine în grafic, dacă putem, știți că, de obicei, vorbim, permitem cicluri non-simple în această clasă, așa că pentru a ști să vă amintiți această proprietate despre copaci și să impuneți această proprietate fără a vorbi despre maladiv. am schimbat condiția uh pentru această sesiune cu probleme această recenzie da, aș putea, de asemenea, să rulez prima căutare în profunzime pe acest grafic, ați putea rula prima căutare în profunzime pe acest grafic pentru a face ce să găsiți cea mai scurtă cale corectă, deci mai întâi căutați în profunzime pe această cale dacă l-am alergat de la s când am ajuns la s prim, aș avea de ales ce să fac corect următoarea margine de ieșire, așa că dacă aș alerga prima alegere depth pentru una dintre acele alegeri, aș găsi o cale spre t dreapta și apoi aș găsi apoi aș putea alerga și aș găsi o cale spre t chiar sunt doar doi dintre ei sau cel mult două, dar există posibilitatea să fi ratat această altă cale care ar putea fi mai scurtă, cum aș rata trebuie să treacă prin nici cealaltă margine nu trece prin cealaltă margine, acesta este punctul corect, nu va trece prin nici o adâncime, prima căutare va trece de fapt prin acest lucru, traversează o margine, trece în jurul ciclului, deoarece totul aici este accesibil de la aici, pentru că este un grafic nedirecționat, va ajunge înapoi până aici și apoi va reveni până la capăt, astfel încât de fapt nu vom traversa niciodată această ultimă margine a ciclului, așa că este ceva ce puteți demonstra cu dfs acum că ați putea de fapt în timp ce rulați dfs încearcă toate posibilitățile corect, deoarece ramificarea mea factorii cel mult trei la unele dintre aceste lucruri corect, așa că ceea ce aș putea face este uh sau ar putea fi cel mult patru corect, aș putea conecta două lucruri cu aceeași ramificare, dar în general este un constantă și cu fiecare alegere pe care dfs le-ar putea face, aș putea încerca toate posibilitățile, câte posibilități ar fi să obțineți o explozie a gradului fiecărui vârf din graficul meu, astfel încât gradul de timp înmulțit unul cu celălalt este de câte ori aș avea trebuie să ruleze dfs, care este exponențial, într-un grad constant, deci o constantă uh [Muzică] înmulțită ca două sau trei drepte uh multiplicată de v ori este de trei la v care este exponențială în dimensiunea graficului meu uh sigur corect pentru că aș putea încă am ramificații mari pentru un număr mare de vârfuri bine, bună întrebare grozavă, bine, așa că asta e problema a treia, am jumătate de oră pentru ultimele două probleme, cred că ar trebui să fie bine, aceasta este uh, bine, aceasta este gogoașa este numele problemei uh Momar tocmai a terminat lucrul la centrala electrică împrăștiată într-o anumită locație p și trebuie să meargă acasă într-o locație cunoscută h, dar pe parcurs, dacă traseul lui ajunge vreodată la distanță de condus k de la un magazin de gogoși, nu va fi. capabil să se reziste și va trebui să meargă acolo și să mănânce gogoși, iar soția lui, Harge, va fi supărată, bine, poate puteți obține referința aici. de distanță cunoscută de condus care leagă unele perechi dintre ele și puteți presupune că nicio locație nu este incidentă cu mai mult de cinci drumuri, bine, așa că avem un grad legat aici, precum și locația și și el știe locațiile pe care toate locațiile care conțin magazine de gogoși există cel mult d dintre ele bine descrie un algoritm de n log n timp pentru a găsi cea mai scurtă rută de condus de la centrala electrică înapoi la casă care evită conducerea pe distanța k de la un magazin de gogoși, bine așa că avem câteva variabile aici. am k avem d, dar un timp de rulare limitat se bazează doar pe n corect bine văd căile cele mai scurte văd că uh nu văd o mențiune explicită a distanțelor pozitive ale văd lungimile corect ei spun că știe uh distanța de condus cunoscută care conectează unele perechi de locații, așa că de obicei cred că dacă aș scrie această problemă acum, probabil că aș fi puțin mai explicit, distanța este pozitivă, dar știi că ceva ce ai putea intra în contact cu distanțele corecte este pozitiv bine și deci nu putem avea distanțe negative aici, bine uh, deci mă uit la n log n sunt ca hei ce are un jurnal în el în această unitate dykstra poate pot folosi dijkstra bine, așa că hai să vedem dacă am rulat dijkstra de la p to h ok, deci avem, avem un grafic aici, avem graficul nostru, deci sunt aceasta este o problemă cu cuvinte, deci nu există nici un grafic acolo, așa că trebuie să definesc un grafic, bine așa că o să definiți un grafic v e și avem v care va fi setul meu de locații, așa că acesta are ordinea lor n dintre ele, sunt de fapt n n dintre ele și apoi e ce vom avea vom avea uh este un pereche de lucruri cunoscute drumuri corecte, cu greutate egală cu condusul condus, distanța de condus, care, după presupunerea mea, va fi mai mare decât zero în acest moment, nu este menționat în mod explicit, dar știi că ar fi o presupunere rezonabilă pentru tine la examen. deoarece distanțele sunt pozitive, probabil că am fi mai expliciți în acest sens în aceste zile, bine, așa că acesta este un grafic pe care l-aș putea face și am un vârf s sau un vârf p și un vârf h și încerc să găsesc cea mai scurtă cale între le-a dreapta cea mai scurtă distanță de condus drumul de conducere bine, așa că aș putea rula dijkstra, așteaptă, deci ce știu despre asta câte muchii am graficul meu am cel mult cinci pe vârf în dreapta, așa că acesta este delimitat de cinci ori v care este ordinea v bine, deci am un grafic ordin v mărime, care este un lucru bun ordinea n pentru că n este numărul de vârfuri și deci, dacă ar fi să rulez dijkstra aici din p, fac dijkstra pe g din orice s ia ordine n log n dreapta n log n plus n și n log n este mai mare decât n bine, așa că aceasta este o observație frumoasă pe care o putem avea, ne putem permite cel puțin să folosim dijkstra în această problemă pentru a găsi cele mai scurte distanțe, dar care este problema cu cea mai scurtă distanță găsită de dijkstra în acest grafic, gogoșile apreciază întregul punct al problemei, trebuie să evit să fiu prea aproape de magazinele de gogoși, bine, așa că s-ar putea să avem un magazin de gogoși aici și trebuie să rămânem în afara acelei distanțe k corect sau s-ar putea să avem un alt magazin de gogoși aici bine și așa că trebuie să găsim o cale care să ocolească aceste magazine de gogoși, bine, cu alte cuvinte, dacă am un vârf în graficul meu unde pot ajunge la o fotografie de gogoși în magazin la distanță k am, nu pot vizita niciodată acel vârf. bine pentru că atunci știi că mama nu va putea rezista și va trebui să mănânce o gogoașă, bine, așa că acesta este lucrul pe care încercăm să-l evităm, așa că cum putem face asta bine, iată o prostie pe care aș putea rula dijkstra de la fiecare dintre ele. aceste vârfuri aceste magazine de gogoși găsesc toate lucrurile accesibile în k distanță de mers de la ele și apoi elimină acele vârfuri din grafic, asta este o idee, dar cât timp ar dura asta ar însemna că trebuie să rulez dijkstra d ori corect pentru că există d cotlete de gogoși Trebuie să rulez dijkstra d ori, așa că îmi oferă un timp de rulare limită de rulat de ori pentru a filtra graficul corect pentru a modifica acest grafic și apoi mai fac una pentru a găsi calea cea mai scurtă dacă există una, dar în general asta va fi ia d ori n log n nu n log n i nu am nicio limitare pe d, cu excepția faptului că este sub n drept, așa că ar putea fi n și asta mi-ar da un timp de rulare prost, așa că vom folosi un truc foarte similar aici cu unul dintre Cred că o sesiune anterioară de revizuire, oprește-te aici, mergem, este atunci când vrei să găsești lucruri dacă suntem pe un prunograf din mai multe locații, unul dintre lucrurile pe care le putem face este orice truc, super nod corect, pot avea un vârf bine Poate că nu vreau să o pun încă, bine dacă am toate aceste magazine de gogoși, ceea ce pot face este să ofer o margine neponderată, nedirecționată chiar aici, putem modela toate acele lucruri direcționate după două margini nedirecționate. nu contează cu adevărat, dar aici știi că nu vreau să merg să mă pot întoarce la super-nodul meu, bine, dar ceea ce voi face este să adaug un super nod cu greutatea marginii, să spunem 0 la totul este corect și apoi dacă am rulat dykstra de la super-nodul și am găsit toate vârfurile accesibile la distanță k bine, nu am petrecut nimic din acea distanță trecând prin această primă margine dreapta și nu m-am întors la s pentru că aceste lucruri sunt direcționate către lucruri și, deci, orice ajung la care ajung va fi la distanță k de acest magazin de gogoși, dar pentru toate magazinele de gogoși și, într-un anumit sens, fac această căutare în paralel, așa că acesta este același truc pe care l-am avut noi. la fel, te uiți prin rețeaua de canalizare sau ceva și încearcă să evite monitoare sau știi senzorii sau ceva de genul ăsta, de fapt, am făcut această transformare și apoi am căutat binar pe distanță în care a fost cam implicat, dar asta este un exemplu mai ușor, acum puteți generaliza și mai mult, dacă fiecare magazin de gogoși ne-ar fi avut, uh, o sumă pe care lui Moamer i-a plăcut corect, așa că dacă uh momar se află la o distanță mai mare de un magazin de gogoși care îi place foarte mult, tot va câștiga. nu pot rezista corect, dar un magazin de gogoși care nu face gogoși foarte bune, știi că va putea rezista la o distanță mai mică, fără a fi nevoie să mergi la acel magazin de gogoși, cu alte cuvinte, fiecare dintre aceste gogoși Shops are un k diferit, o rază diferită pe care o va permite Momar. Există vreo modalitate de a generaliza această tehnică pentru a putea tăia toate acele vârfuri în schimb ah toate acestea aveau greutate zero înainte de aceeași greutate, adică algoritmul ar fi funcționat pentru orice greutate pe care o pun pe toate aceste margini, atâta timp cât caut distanța acea greutate plus k chiar aici, pot face doar distanța acestei frontiere pentru fiecare dintre magazinele de gogoși la fel, modificând distanța până la cea de intrare. marginea dreapta, astfel încât să pot seta lungimea uh discul greutatea de la la magazinul de gogoși cu cea mai mare rază la zero și apoi să pun diferența dintre cea mai mare rază la toate celelalte am pus asta ca greutate pe celelalte margini și atunci mai avem un grafic cu ponderi de margine pozitivă și pot rula dijkstra din asta și asta ar generaliza această problemă și ceva ce am făcut în unele examene de practică și sau în examene și seturi de probleme în trecut, bine, așa că este un alt lucru comun. astfel încât filtrul filtrul uh interzis există două b în interzis sau două d două d există trei vârfuri ds drepte folosind supernodul plus o rundă de dijkstra, acestea sunt literele suplimentare, bine, așa că probabil că la examen ați dori să fiți puțin mai explicit, acesta este un rezumat al lucrurilor despre care tocmai am vorbit, doar că știi, am vorbit 10 minute despre algoritm, dar nu strica să adaugi un rezumat în partea de sus a ceea ce vei scrie acesta este abordarea pe care o vom avea, vom filtra vârfurile din g, în esență, rulând dijkstra din fiecare dintre aceste cotlete de gogoși, dar o vom face în paralel adăugând super-nodul, bine, deci de fapt pe altul uh uh recomandarea pe care o am pentru tine la un examen este că aproape orice problemă pe care ți-o punem în această clasă poate obține 80 până la 90 de puncte, scriind cam trei rânduri aproape și poate nu unele dintre problemele cu structurile de date, dar aproape orice. Întrebarea din această clasă poate fi rezolvată nu cu toate punctele, ci cu majoritatea punctelor, scriind doar câteva rânduri despre care știm că știi cum să rezolvi problema corect și aceasta ar fi una dintre acele situații corecte. acum aș vrea să vă ofer puncte complete, aș dori toate detaliile aici, am construit un nou grafic, adaug acest vârf aici, trebuie să adaug muchii la fiecare dintre cele d lucruri, dar am adăugat doar d muchii și încă una vârf, așa că are încă această dimensiune liniară în intrarea mea și apoi vreau să spun că știi că pun greutățile aici pe baza distanței acum, toate au aceeași greutate pentru că nu am asta. generalizare și apoi rulez acest lucru și elimin toate acele grafice și construiesc un nou grafic din g, acesta este un al treilea grafic pe care îl construiesc acum, dar observă că graficul care era implicit în problema mea era foarte diferit de graficul pe care îl construiesc. În cele din urmă, rulez un algoritm cu cea mai scurtă cale, cum ar fi dijkstra, de la p la c, dacă există o cale, are sens, orice întrebare despre această problemă, bine, avem 20 de minute pentru ultima mea problemă, uh, omule, nu folosesc, scriu mult mai puțin decât unii dintre ceilalți instructori ai tăi, așa că îmi place să vorbesc mai mult decât să scriu, aparent în regulă, deci problema 4, hai să ne uităm la asta pe care l-am inventat aseară, un fel de distracție, căile lungi și scurte bine, având în vedere un grafic direcționat cu margine arbitrară greutăți, practic, acestea ar putea fi pozitive sau negative sau zero și două vârfuri din grafic descriu un algoritm de timp cub v pentru a găsi greutatea minimă a oricărei căi de la s la t ok care sună ca Bellman Ford chiar acolo, dar am această ultimă condiție și ultima condiția este puțin ciudată, care conține cel puțin marginile, așa că vreau o cale scurtă în ceea ce privește greutatea, dar vreau o cale lungă într-un anumit sens în ceea ce privește numărul de margini pe care le traversez are sens, așa că toate căile au cel puțin margini vreau unul cel mai scurt dintre ele din punct de vedere al greutății, aceasta este o problemă ciudată, de obicei, nu încercăm să facem acest lucru maxim min. avem două cantități diferite aici, încercăm să optimizăm oricine are idei despre cum aș putea aborda această problemă ce sună acest lucru ce sună cel puțin marginile v într-un fel cu cel despre care am putea vorbi în prelegere uh, uh, atunci când vorbeam despre min ford, am definit acest lucru numit o greutate k edge corect este greutatea oricărei căi care utilizează cel mult k muchii acest tip de constrângere de margine pare similară, cu excepția faptului că este un fel invers, nu este cel puțin, este un mo, este cel mult nu este cel puțin, este cel puțin bine, iată o observație pe care o am pentru tine dacă Vreau o cale care trece prin cel puțin margini, un prefix al acelei căi de trecere folosește exact marginile drepte, care are sens corect, așa că poate că are sens pentru mine, poate că ar putea ușura această problemă dacă nu este cel puțin marginile, dar dacă sunt exact marginile, poate mă gândesc la asta în acest fel încât mi s-a părut un alt mod rezonabil de a mă gândi la această problemă, știam cum să fac până la un anumit set de margini, cel mult, cerem aici, poate că lucrul dintre ele este un puțin mai ușor de gândit bine, așa că ceea ce facem ni se dă un grafic g are orice pondere este posibil ca acest grafic să aibă e mărginit inferioară de o pătratică în vârfurile din dreapta. Nu am restricții cu privire la câte muchii ar putea acest lucru fi și deci cel mai rău lucru pe care l-aș putea avea este că acest lucru, adică graficele mele sunt simple, cel mai rău lucru pe care l-aș putea face este ca acesta să fie pătratic în numărul de muchii, să spunem dacă este graficul complet, acesta este numărul maxim de muchii pe care l-aș putea am și încerc să găsesc în graficul meu o cale care folosește o mulțime de vârfuri, dar are o greutate mică acum, ceea ce este un alt lucru de observat aici este dacă folosesc cel puțin margini v, calea mea poate fi simplă nu este corectă, deoarece trebuie să folosesc cel puțin v plus un vârfuri și există mai multe decât vârfurile pe care le am în grafic, evident că acum ar putea trece prin vârfuri de mai multe ori, dar cu siguranță nu va fi o cale simplă, bine, deci care este un lucru cum ar fi iată ce dacă există un ciclu de pondere negativă în graficul meu care este greutatea minimă a oricărei căi de la s la t dacă ciclul de pondere negativă este accesibil de la s accesibil pe o cale de la s la t care este răspunsul la problema mea, atunci infinitul negativ corect, deoarece cu siguranță un infinit calea lungimii va folosi un număr infinit de muchii corect dacă se lungește în mod arbitrar, atunci pot rula bellman ford corect, așa că este un lucru pe care îl pot face, pot rula bellman ford pe acest grafic, am suficient timp să fac asta pentru că e este mărginită superioară de v pătrat și am v cub de timp și dacă există un ciclu de greutate negativ în graficul meu, pot ști că greutatea minimă a oricărei căi este minus infinitul, detectez că acesta este cazul dacă, dacă practic, t este accesibil de la s cu o distanță minimă de calea cea mai scurtă minus infinit, că calea care realizează asta va avea mai mult de v muchii, așa că știi că am terminat și că nicio cale nu realizează asta, dar știi că asta este în fema da supremum suprem sau infimum, îmi pare rău, mergem la limita inferioară, mă gândesc la căi lungi, totuși, deci numărul de muchii se apropie de infinit, bine, dar în contextul în care nu am cicluri negative de greutate, de fapt, unul dintre lucrurile pe care le-am arătat a fost că, dacă Nu se poate ajunge printr-un ciclu de greutate negativ sau dacă niciun ciclu de greutate negativ nu este parcurs de la s la t, atunci calea mea cea mai scurtă va fi simplă, dar asta nu pare să se aplice nici aici, deoarece trebuie să avem o cale non-simplu. Deci, ce facem, să ne întoarcem la această idee de a încerca să ne dăm seama de greutatea minimă a oricărei căi folosind exact marginile. Putem folosi unele dintre trucurile pe care le-am avut în Bellman Ford când ținem evidența numărului de muchiile pe care le trecem la un moment dat, aceasta este ideea corectă dacă avem un vârf dacă avem un vârf nou pentru fiecare vârf, versiuni diferite ale acestuia care vorbesc despre exact prin câte muchii am trecut, atunci poate că aș putea urmări asta în timp ce lucrez corect la acest grafic, deci să spunem că am mai multe straturi ale graficului, aceasta este ideea, poate că începem de la nivelul 0 de aici jos pentru a nivela câte muchii vreau vreau v plus 1 vârfuri deci voi avea v plus 1 niveluri, care este v corect, deci un nivel aici v câte niveluri există există v plus zero, da și deci voi avea pentru fiecare muchie din graficul meu pe care o voi merge să- l iau, astfel încât acesta este un grafic direcționat la dreapta, așa că îl direc în jos la nivelul următor pentru fiecare versiune a acestui grafic pe care o am, iau acea margine care a fost inițial între u și v aici în grafic, a fost inițial aici în g dar aici am îndreptat toate acele margini în jos, bine, nu este că ceea ce am făcut în Bowman Ford, am făcut o altă adăugare în Bellman Ford pentru a face să fie cel mult dreptul de proprietate. Care a fost acea transformare pe care am făcut-o, am avut zero opt muchii trecând de la fiecare vârf la altul la dreapta, însemna că nu trebuia să traversăm o muchie la dreapta, dar aici dacă nu adăugăm acele muchii, de fapt, această transformare ne dă că orice cale care trece prin muchiile v va fi o cale de la un vârf. în stratul 0 la un vârf în stratul v tocmai pentru că pentru a ajunge aici a trebuit să traversez exact marginile și acestea sunt marginile graficului meu original, acum observați că acest lucru codifică și căi non-simple, deoarece aceste lucruri nu ar putea du-te, aș putea merge aici și înapoi la tine și înapoi la v și înapoi la tine dacă aș avea un ciclu în graficul meu, dar de fapt, ce fel de grafic este acesta, acesta este un dac corect, deci acesta este dag uh, poate îl numesc g prim câte vârfuri sunt în g prim v ori v plus 1 dreapta, așa că voi spune ordinea v pătrat și câte muchii sunt pe graficul meu de v ori e dreapta i am copiat fiecare muchie a făcut-o îndreptată în jos între fiecare nivel există v tranziții între niveluri și copiez fiecare muchie pentru fiecare dintre acestea, astfel încât numărul de muchii este de ordine de v ori e bine, deci acest grafic este aruncat în aer, există o mulțime de lucruri în acest grafic, dar observ că știți că acest grafic are ordinea mărimii v cub este la ce căutăm, așa că îmi pot permite să construim acest grafic, deoarece v este, de fapt, mărginit superior de v pătrat prin simplitate, bine, așa că avem acest grafic, am putea găsi vârfurile noastre aici ca 0 aici și ne-am putea permite să să calculez cea mai scurtă distanță de cale până la toate celelalte vârfuri folosind exact marginile din graficul meu exact, asta este ceea ce am putea face, pot găsi tot ce este accesibil de la s 0 în acest grafic și să calculez cea mai scurtă cale aici, în partea de jos, astfel încât să pot face asta în timpul cubului v, deoarece relaxarea dag este liniară în dimensiunea graficului, dar nu asta mă întreabă problema, din păcate, în special, aș putea găsi calea către t la t v și asta mi-ar oferi cea mai scurtă cale folosind exact marginile, dar asta este nu este ceea ce cer, cer cel puțin, așa că este posibil să ajung aici la un alt vârf și poate că există o cale de greutate negativă care merge la t și vreau să pot găsi asta, deci cum pot face că cum pot permite căilor să continue dincolo de o sumă arbitrară, aș putea avea mai multe straturi corect, căi simple, de la orice versiune, mă refer la cele mai scurte căi care sunt simple, care folosesc mai puține margini aici, nu sunt limitat la număr de muchii pe care le folosesc corect, așa că cele mai scurte căi din acest grafic vor fi simple, deoarece nu există niciun negativ pe care l-am deja, îmi place deja să arunc cazul în care am cicluri negative pentru că am alergat pe bellman ford la început, pot, uh i așa că știu că voi dori o scurtă lovitură pe o cale simplă după ce am ajuns la margini, deoarece nu va fi niciodată benefic pentru mine să mă întorc la un vârf, deoarece aceasta va fi o cale de greutate mai lungă, așa cum este. genul de argument chirurgical pe care l-am avut atât în ​​context neponderat, cât și în context ponderat, bine, așa că acestea vor fi simple, așa că știu că trebuie doar să merg cu mai multe straturi, bine, așa că este o modalitate de a vedea, aș putea adăuga mai multe straturi. din acest lucru, găsiți cea mai scurtă distanță de cale către toate vârfurile folosind până la două margini v, poate chiar două v minus unul, dar comandați v și apoi pentru toate cele de mai jos, mă uit doar la fiecare vârf și văd ce greutate este minim, într- un alt mod în care îmi place să-l privesc, ceea ce este puțin mai distractiv, cred că este că, odată ajuns aici, încerc doar să găsesc căi simple în grafic de la acest vârf v până la acest vârf v dreapta deci unul dintre adaugă acestea urcă, așa că de fapt, pe acest strat de jos din dreapta vreau să găsesc căi foarte scurte către t de la fiecare vârf din dreapta și știu de fapt care este scurt de la ceea ce am făcut aici până la relaxare. pe acest grafic știam care este cea mai scurtă distanță de cale de la s0 la fiecare dintre aceste vârfuri, deoarece am făcut asta în timpul cubului v aici cu relaxare dag, astfel încât să pot adăuga un super nod la acest lucru cu o margine direcționată la fiecare vârf cu cel mai scurt cu ponderea cu cea mai scurtă distanță de cale pe care am găsit-o mai sus acum, am un grafic în care orice cale de la s0 la v la t v aici va fi o cale care folosește cel puțin marginile din graficul meu original, deoarece acestea reprezintă cele mai scurte greutăți ale drumului orice folosește exact marginile și apoi calea poate continua chiar în graficul original, așa că acum am un nou grafic aici, astfel încât fiecare cale de aici până acolo să corespundă unei căi pe care o caut, așa că vreau să găsesc o greutate minimă calea în acest grafic cum pot face asta acum, acest grafic ar putea avea greutăți negative negative. marginile noastre originale aici în stratul de jos al acestui grafic și rulați bellman ford pe întregul grafic de ce nu aș putea face asta este prea mare, corect numărul de vârfuri este v pătrat numărul de muchii este v potențial v cub rulând bellman ford pe acel grafic duplicat uriaș mi-ar da un v la al cincilea timp de rulare, ceea ce este îngrozitor, într-un sens, separăm complexitatea, partea superioară a graficului are o structură dag foarte frumoasă, așa că haideți să facem cele mai scurte căi în acea structură dag și apoi să reducem acea complexitate până la a fi doar lucrul care are ciclurile pentru care suntem îngrijorați, care reduce complexitatea aici jos, așa că cât de mare este acest grafic, știi acest grafic, știi uh v plus un nod corect pentru că am adăugat doar un super nod aici și are e plus, știi, comandă v margini, nu vreau să fiu atent aici, dar este liniar în dimensiunea graficului original, așa că rularea Bellman Ford aici durează doar de v ori e timp care este v cubit, deci sunt două moduri diferite cum să rezolv această problemă, folosind o grămadă de duplicare a graficelor și având cunoștințele că mergând cel mult mai mulți pași din această duplicare a graficului nu s- ar putea obține niciodată un lucru mai bun, așa că mă pot opri sau recunoscând că am acest algoritm foarte puternic aici, care pot găsi cele mai scurte căi căi simple într-un grafic fără cicluri negative de greutate și pot folosi această super-notă pentru a transfera o parte a graficului meu cu o structură foarte frumoasă până la acest alt grafic, bine orice întrebări despre această problemă, așa că acestea sunt câteva pe care le avem două probleme abstracte pentru tine, două probleme cu cuvinte pentru tine, cu o mulțime de transformări diferite și o mulțime de trucuri diferite ale meseriei tale, oricare dintre acestea ar fi ceva care fie apare la un examen, fie este la un nivel de ceva care ar putea apărea la examenul dvs., așa că mergeți mai departe și aruncați o privire la materialul de practică pe care l-am postat și care este accesibil de pe site-urile web din anii precedenți și vă urez succes în a lucra la problemele grafice la examenul dvs.