[SCRÂȘIT]
[FOSȘIT]
[CLIC]
ERIK DEMAINE: Bine.
Bine ați revenit la 006 și la
cvadrupla noastră programare dinamică
de prelegeri.
Suntem la jumătatea drumului,
în cursul trei din patru.
Astăzi, vom
continua această idee de
constrângeri și extindere a problemelor care a
fost menționată, în special,
spre sfârșitul prelegerii trecute.  Am
văzut un exemplu de
extindere a subproblemei cu un factor de 2
în jocul pentru doi jucători
cu monede
în care am vrut să avem
două versiuni ale jocului,
una în care merg primul și
alta unde mergi tu primul.
Deci, aceasta a fost extinderea
numărului de astfel de probleme
cu un factor de 2.
Astăzi, vom vedea
mai multe exemple ale acestei idei,
inclusiv într-un cadru pe care l-am
văzut deja,
care este Bellman-Ford, la
care vă puteți
gândi.  ca program dinamic.
Poate că este un
moment bun să menționăm
că Bellman a inventat
programarea dinamică în anii '50.
Același Bellman în
algoritmul Bellman-Ford.
Aceasta a fost de fapt o
descoperire independentă
a amândoi
și a altor oameni.  A
inventat programarea dinamică
și apoi, câțiva ani mai târziu, a
aplicat-o pentru a rezolva problema celor
mai scurte căi cu o singură sursă
.
Le-am văzut în cealaltă ordine.
Am văzut
mai întâi cele mai scurte căi cu o singură sursă,
pentru că a fost puțin mai ușor.
Și acum vedem
cadrul general în care se încadrează acest lucru.
Și așa vom vedea cum funcționează.
De ce a numit Bellman
programare dinamică
programare dinamică?
Mai ales pentru că
suna cool și el
încerca să impresioneze
agențiile guvernamentale, oferindu-i granturi.
Adică, cum poți să te cert cu
ceva la fel de cool
ca programarea dinamică?
Dar există ceva logică.
Programarea este o referire la
o formă veche a acestui cuvânt, care
înseamnă optimizare.
Și, în general,
încercăm să optimizăm lucrurile.
Și în loc să
optimizăm în conformitate
cu un fel de
abordare sau program static, o
facem dinamic.
Aceasta este o referire la
forța brută locală pe care o facem
pentru a o optimiza în fiecare etapă.
Nu poți spune, în
partea de sus, ce vei
face la mijloc.
Și așa este un fel de--
fiecare subproblema se
comportă diferit.
Și așa, în acest sens, dinamic.
Și sună cool.  În
regulă.
Apoi vom merge la
cele mai scurte căi ale tuturor perechilor.
Vom vedea un nou algoritm pentru
asta, care nu este asimptotic
mai bun, dar este
drăguț și simplu,
și o altă modalitate de a-- un mod minunat
de a vedea extinderea subproblemei.
Și apoi ne vom uita la un
fel de probleme practice -- punerea în
paranteze a
expresiilor aritmetice
și o problemă din lumea reală,
degetarea la pian și la chitară,
deci alocarea unei degetări
cum să cânte o piesă.
Și vom face asta
cu cadrul nostru SRTBOT.
Amintește-ți rapid ce
este asta.
Definim subprobleme.
Și am văzut cum să facem
asta pentru secvențe.
Încercăm fie prefixe,
sufixe, fie subșiruri.
Preferăm prefixele și sufixele
pentru că sunt mai puține.
Dacă există mai mult
de o secvență,
luăm produsul
acelor spații.
Și apoi ideea pe care o vom
sublinia astăzi
este că putem
adăuga oricând subprobleme
pentru a face următorul pas mai ușor.
În special, adăugarea de
constrângeri la subprobleme,
într-un anumit sens, ne permite să ne amintim
lucruri despre subproblema
care ne cheamă --
sau despre trecut,
este o modalitate de a ne gândi la asta --
sau, în general, de a
„ne aminti starea”.
Doar adăugând mai multe subprobleme, ne
putem aminti mai multe lucruri --
nu doar lucrurile la care
lucrăm, ci și un anumit context.
Și asta este ceea ce vom vedea o
mulțime de exemple de astăzi.
Sperăm că va avea sens
până la sfârșitul prelegerii.
Apoi, trebuie să relaționăm aceste
subprobleme cu relația de recurență -
de fapt, de obicei o
numim doar o relație.
Și ideea cheie aici este
să veniți cu o întrebare
pe care, dacă ați cunoaște
răspunsul la acea întrebare,
ați putea reduce
subproblema pe care
încercați să o rezolvați la
soluții de subproblemă mai mici.
Această întrebare este un fel de
aspect fundamental al...
un
aspect fundamental al unei soluții.
De obicei, atunci când aveți
de-a face cu sufixe,
doriți să puneți o întrebare
despre primul articol, s din i.
Când ai de-a face
cu prefixe,
vrei să pui o
întrebare despre unele...
lângă ultimul element,
s din i minus 1.
Și pentru subșiruri, cine știe?
Undeva la mijloc.
Vom vedea un exemplu
în acest sens astăzi.
Odată ce ai... oh,
aceasta este o dezvăluire.
Ceva vine mai târziu.
Odată ce ați identificat o
astfel de întrebare, abordarea de
programare dinamică
este:
nu fiți deștepți cu privire la cum
să răspundeți la acea întrebare -
doar forță brută locală.
Încercați toate
răspunsurile posibile la întrebare.
Pentru fiecare dintre ele, recurgeți
și luați cea mai bună soluție
în funcție de valoarea pe care
încercați să o faceți, de obicei
minimizarea sau maximizarea.  Un
alt mod de a mă gândi la
această forță brută locală, pe
care îmi place să o
cred în capul meu --
așa că poate unora le place
asta, altora nu --
este să mă gândesc să ghicesc
răspunsul la întrebare.
Deci, poate că răspunsul
ar putea fi 0, 1 sau 2.
Și algoritmul meu va spune,
ghici care este răspunsul corect.
Și voi presupune că
algoritmul meu ghicește corect
răspunsul și îl analizez.
Deci, ne putem gândi la program
ca mergând direct --
ghicind răspunsul
și apoi recurgând
și apoi combinând
soluțiile.
Dar apoi, la
final, desigur,
nu putem presupune că
presupunerea a fost corectă.
De fapt, trebuie să trecem
peste toate aceste presupuneri.
Deci este același lucru.
Doar, dacă te gândești
la asta în acest fel,
există mai puține bucle
în programul tău.
Dar când o analizezi
, cu siguranță, bucla
este cu adevărat acolo.
Trebuie să plătiți pentru toate
răspunsurile posibile.
BINE.
Apoi trebuie să ne asigurăm că
această relație este aciclică,
obținem o subproblemă DAG.
Și îmi place să specific o
ordine topologică explicită
pentru a clarifica acest lucru.
Avem cazuri de bază
pentru relație.
Trebuie să rezolvăm
problema inițială
în termenii acestor
subprobleme și apoi analizăm

timpul de rulare, de obicei,
ca numărul de subprobleme
înmulțit cu munca nerecursivă
din relație.
Deci recursiunea este gratuită
pentru că înmulțim
cu numărul de subprobleme.
Puteți, de asemenea, să
însumați subproblemele.
Uneori, asta
vă oferă o legătură mai strânsă.
Și apoi,
desigur, trebuie să
adăugăm și timpul de funcționare pe care îl
petrecem în problema inițială.  În
regulă.
Asta a fost o recapitulare rapidă.
Acum, o problemă pe care am văzut-o
în acest cadru în
urmă cu două prelegeri--
prima prelegere a fost
cele mai scurte căi cu o singură sursă
într-un DAG,
care, o mulțime de
programe dinamice, de fapt,
pot fi reduse la o
singură sursă cele mai scurte căi
într-un DAG.
De fapt, este adevărat invers.  Se pot gândi la
cele mai scurte căi dintr-o singură sursă
într-un DAG.  Algoritmul de
relaxare DAG pe care l-am
văzut
este în esență un program dinamic în
care subproblemele sunt
delta lui s, v. Relația
dintre delta lui s, v este min.
Deci la ce ne
gândim aici?
Bănuim... aceasta este
un fel de expresie nouă pe care vreau să o adaug.
De fapt, am scris-o chiar aici.
Ultima muchie, u, v, pe cea mai
scurtă cale de la s la v.
Aceasta este o deltă a
s, v. Problema pe care
încercăm să o rezolvăm este să
găsim cea mai scurtă cale de la s la v.
Și este o cale și
nu știm cum arată,
dar o caracteristică a
soluției acestei căi pe care
încercăm să o găsim este, ei
bine, care este ultima margine?
Acesta provine de la un vârf de aici,
cu excepția cazului în care calea este de lungime 0
și s este egal cu v. Acesta este
un caz special tratat
în cazul de bază.
În caz contrar, există
un vârf u înainte de v.
Nu știm ce
este, așa că vom folosi
forța brută local sau vom
ghici care este răspunsul corect.
Deci, uitați-vă la toate
muchiile de intrare de la u
la v și, pentru fiecare dintre ele,
luați calea cea mai scurtă recursivă
de la s la u, plus
greutatea muchiei.
Deci aceasta este perspectiva ghicirii sau a
forței brute locale.
Și motivul pentru care funcționează
este pentru că G este aciclic
și deci are o
ordine topologică.  În
caz contrar, dacă
graficul are un ciclu -
și acesta este cazul la care
vrem să trecem la următorul -
acest apel recursiv de la
delta de s, v la delta de s,
u va avea bucle în el.
Și astfel nu veți
evalua niciodată această recursivitate.
Nu vei termina niciodată.
Nu vei minimiza niciodată.
Vei fi trist.  Va
dura un timp infinit.
Deci nu utilizați acest algoritm
decât dacă aveți un DAG.
Pentru DAG, este grozav.
Este timpul liniar.
Deci a fost o mică recenzie.
Acum, iată cele mai
scurte căi cu o singură sursă
în graficele generale, pe care le
cunoaștem ca Bellman-Ford,
dar reformulată în
cadrul SRTBOT.
Așa că am definit această problemă,
în prelegerea Bellman-Ford,
delta sub k a lui s,
v. Amintiți-vă, aceasta
a fost greutatea unei
căi cele mai scurte de la s
la v care este restricționată
la utilizarea, cel mult, k muchii.
Acest lucru a făcut problema fezabilă.  Am
ajuns să luăm
produsul graficului
în toate aceste
subprobleme diferite, de fapt.
Dar din perspectiva
programării dinamice, ne
gândim la aceasta ca la o
constrângere subproblemă.
Ceea ce ne dorim cu adevărat este cea
mai scurtă cale de la s la v,
dar asta este greu.
Așa că
o vom împărți în bucăți mai mici.
Pentru fiecare k între
0 și v, vom
spune, ei bine, să ne gândim
la această problemă limitată
la utilizarea, cel mult, a k muchii.
Iar pentru trasee simple, dacă
nu există cicluri de greutate negative,
trebuie doar să
urcăm până la v minus 1.
Am demonstrat că.
Și știm că suntem...
atunci suntem fericiți.
Dar acesta este un fel de ultimul
lucru pe care vrem să-l rezolvăm.
Deci, dacă ne uităm în jos la
problema inițială pe care o dorim,
este delta sub v minus
1 din s, v pentru toate v.
Deci, dacă am putea rezolva
aceste subprobleme,
așa cum am văzut cu
Bellman-Ford, putem
rezolva
problema inițială --  cu excepția cazului în care
există cicluri negative de greutate.
Și folosim delta sub v din s,
v pentru a verifica dacă sunt
cicluri de greutate negative.
Nu vreau să repet
asta, dar asta este totul
în problema inițială.
Și apoi putem
lua această relație pe
care am scris-o pentru
cele mai scurte căi DAG
și pur și simplu o portam aici.
Deci, amintiți-vă, pentru
un grafic general,
acesta are cicluri,
deci nu îl putem folosi,
pentru că ne referim doar
la delta arbitrară a lui s,
vs, deci nu există niciun motiv
să nu ne așteptăm la niciun ciclu acolo.
De fapt, graficul de apel
este exact graficul G,
deci are un ciclu dacă
și numai dacă G are.
Dar acum, pe aici, rulez
exact aceeași formulă
pentru acest min, dar am
adăugat un sub k aici
și un sub k minus 1
aici, observația
fiind, dacă am
ghicit deja care este
ultima muchie u, v
este pentru această cale,
atunci dacă tot acest lucru
are lungimea de cel mult k,
atunci această piesă are
lungimea de cel mult k minus 1.
Deci trebuie doar să rezolv delta
sub k minus 1 din s, v aici.
Și așa am
scris-- scuze, de s, u.
Asta am scris aici.  Mai
există un
lucru, și anume,
așa cum am menționat cu
puțin timp în urmă,
s-ar putea să
folosim mai puține decât k muchii.
Și deci să luăm în considerare
cazul în care
nu urmăm ultima muchie
și doar adăugăm la acest min
cea mai scurtă cale folosind,
cel mult, k minus 1 muchii.
Aceasta este o opțiune pentru a
avea, cel mult, k margini.
Dacă am scrie egalitate
aici, atunci am
elimina asta, ca și
ultima secțiune cu probleme.
OK bine.
Observația cheie aici este
că această recurență nu
are cicluri.
Doar adăugând acest indice,
dacă rezolvăm aceste probleme
în ordinea creșterii k, toate
referințele din delta sub
se îngrijesc în termeni de
delta k minus 1.
Și astfel, acest lucru este acum
magic aciclic.
Acesta este motivul pentru care Bellman-Ford a lucrat.
Dar acum, cred că într-
un mod foarte plăcut,
luăm graficul nostru aciclic.
Și răspândindu-l
pe diferite copii ale lui k
și referindu-ne întotdeauna la cea
mai mică,
obținem un grafic aciclic -
relații aciclice.
Avem cazuri de bază, ca în mod normal.
Și apoi putem analiza
timpul de funcționare
în mod obișnuit,
care este însumând--
cât costă asta?  Vom lua
costul
calculării relației, care
este numărul de
muchii de intrare la v--
asta este theta-- și apoi
o subproblemă generală.
Deci, suma peste k și
suma peste v. Am scris-o
ca sumă în loc de
produs, deoarece acest lucru
este theta E. Suma muchiilor de intrare
peste toate vârfurile
este exact de dimensiunea lui
E. Și apoi însumăm...
nu există k în  această formulă,
așa că doar înmulțim cu v
și obținem v E. Deci bunul nostru
prieten Bellman-Ford a reformulat cam
invers.
Înainte,
folosim relaxări.
Acum, doar scriem
min-ul în mod explicit.
Dar în esență
același calcul, doar
într-o ordine diferită.
Bine, in regula.
Acestea sunt recenzii
ale unor algoritmi vechi,
dar în acest nou cadru
pentru a arăta cât de puternic este.  Să ne
uităm la un alt
exemplu, care este prietenul nostru--
chiar aici-- cele
mai scurte căi toate perechile.
Cu câteva prelegeri în urmă, am
văzut algoritmul lui Johnson,
care rezolvă acest lucru foarte bine.
Așadar, o opțiune pe care am
putea-o folosi este
același set de subprobleme,
dar pentru toate u și v.
Pentru u și v și v--
asta ne
pasă cu adevărat.
Și apoi am putea spune k până
la v. Așa ceva.
Deci, ar funcționa, dar ar
oferi același timp de rulare
ca și rularea Bellman-Ford v ori.
Aceasta este o soluție pe care o
cunoaștem, dar nu
cea mai bună soluție pe care o cunoaștem, pentru
cum să rezolvăm cele mai scurte căi.
Acest lucru ar da v pătrat E,
care este cel mult v până la al patrulea.
Pentru graficele dense,
este theta v până la al patrulea.
Deci, acesta este de v ori v
ori v. Dar cel mai rău caz
este de la v la al patrulea
ceea ce aș dori să
vă arăt acum
este o modalitate diferită
de a rezolva această problemă -
aproape identică, dar oferă
v timp de rulare cub, care, pentru
grafice dense  , este chiar bun.
Deci vom reduce
acest 4 la 3.
Și acesta este un algoritm
numit Floyd-Warshall.  Cu
siguranță nu este
un algoritm evident.
Este o idee foarte tare.
Și este un exemplu frumos
al unei modalități diferite...
amintiți-vă, aceasta este
extinderea subproblemei.  Am
luat problemele de care ne
pasau înmulțite
cu această alegere a lui k.
Aici, vom
face același lucru,
dar îl definim diferit.
Vom defini acele
subprobleme diferit.  În
primul rând, vreau să
numerez vârfurile,
începând cu 1 pentru comoditate.
Deci, să vedem, y--
și apoi vom
defini câteva subprobleme, care
sunt delta-- O
voi numi u, v, virgulă k.
Poate, pentru a evita conflictul,
voi scrie un d aici.
Aceasta este doar o definiție
locală a acestui algoritm.
Deci vreau greutatea celei
mai scurte căi de la s la v.
Până acum, la fel
ca problema pe care
vrem să o rezolvăm.
Aceasta este delta de-- îmi
pare rău, u, v. Dar voi
adăuga o constrângere, adică
folosind numai vârfuri în
u, v și 1 până la k.
Aceasta este inspirația divină
de a defini subproblemele în acest fel.
Este o constrângere diferită
de cea pe care am văzut-o aici,
care folosea,
cel mult, k muchii.
Deci, într-un anumit sens,
ceea ce este lent la
acest algoritm este că
trebuie să facem buclă peste
toate nodurile de intrare.
Acest lucru este scump.
Costurile ordonă gradul,
care se termină cu un termen E.
Vom încerca să convertim
acel termen E într-un termen v
doar știind de la ce
vârf să provină -
ceea ce sună imposibil.
Dar se dovedește, dacă scrieți
subproblemele în acest fel,
așa că numesc vârfurile.
Și spuneți, ei bine, să
găsesc o cale care folosește u,
v și vârful etichetat 1.
Există doar două opțiuni.
Aș putea merge direct de la u la v,
sau aș putea merge de la u la 1 la v.
Și apoi, ce zici cu 1
și 2, și 1 și 2 și 3?
Aceleași vârfuri.
Prin etichetă în loc de
numărarea lor.
Ușoară modificare, dar se dovedește că
acest lucru accelerează algoritmul.
Așa că mai întâi să vă spun
câte subprobleme există.
Aceasta este subprobleme cub.
Două opțiuni pentru u și v
și am v opțiuni pentru-- îmi pare
rău, am v opțiuni
pentru u, v opțiuni pentru v
și v opțiuni pentru k, aproximativ.
v cub din acestea.
Dar cheia este...
asta sună mult.
Dar relația
devine mai ieftină acum,
pentru că pot doar să
scriu delta u-- îmi
pare rău, d din u v k este
minul a două lucruri, d din u,
v, k minus 1 și d din u,
k, k minus 1, plus d  de k,
v, k minus 1.
Este o formulă ciudată,
deoarece folosim indici
precum k și pentru vârfuri,
precum și u și v pentru vârfuri,
dar folosim și
k ca numărător.
Dar putem face acest lucru deoarece
vârfurile noastre sunt numerotate.
BINE.
Deci ideea este următoarea.
Avem vârful u, avem un
vârf v. Și am
găsit deja calea cea mai scurtă
care folosește vârfurile de la 1
la k minus 1.
Aceasta este această cantitate.
Deci ar putea fi...
și acum, încercăm
să adăugăm în acest vârf k
și să ne gândim la, care sunt
toate căile care ar putea
merge de la u la v folosind 1 până la k?  Ei
bine, ar putea fi cea
mai scurtă cale de la u
la v folosind 1 până la k
nu folosește vârful k.
Asta e prima varianta.
Folosiți doar vârfurile
1 până la k minus 1.
Poate că nu trebuie să folosim k.
Sau s-ar putea ca
drumul să treacă prin k.  Ei
bine, începe de la
u și merge la k
și apoi trece de la
k la v, toate folosind--
pentru căi simple, dacă presupunem că
nu există cicluri negative de greutate
și trebuie să rulați
Bellman-Ford pentru a le detecta  --
dar presupunând că nu există
cicluri de greutate negative, calea cea mai scurtă
de la u la v prin k trebuie
să înceapă prin utilizarea vârfurilor mai mici
decât k și apoi să folosească din
nou vârfuri mai mici decât k.
Și asta
am scris aici.
Este de la u la k folosind k minus
1 până la k minus 1 etichete
și de la k la v folosind
etichete până la k minus 1.
Lucrul tare aici este că
minul are doar doi termeni.
Deci, acest lucru necesită
timp constant de muncă nerecursivă.
Deci, aceasta este, k nu este
pe calea cea mai scurtă.
Și aceasta este, k este pe
calea cea mai scurtă.
Misto.
Deci aceasta este o
muncă constantă nerecursivă.
Dacă trecem înainte la
timpul de rulare pentru acest algoritm,
obținem numărul de
subprobleme, care este v cubat,
ori cantitatea de lucru pe
subproblemă, care este constantă.
Deci, acesta este doar un
algoritm cub cu v.
Pentru grafice dense,
acest lucru este foarte bun.
Când E este v pătrat, atunci acesta
este același lucru cu v ori E,
deci la fel de bun ca Bellman-Ford.
Nu este la fel de bun ca
Johnson pentru grafice rare.
Grafice rare, amintiți-vă--
sau, în general, cu Johnson,
avem v pătrat log n
plus v. Și asta înseamnă întotdeauna
cheltuirea v cub.
Dar este mișto pentru că este
un algoritm foarte simplu.
Să scriem rapid
ordinea topologică.
Tot ce avem nevoie este să garantăm că
rezolvăm problemele în
ordinea k crescătoare, deoarece
fiecare referință aici
este la un k mai mic pentru
al treilea argument.
Și astfel, de exemplu,
puteți
scrie o buclă triplu imbricată -
k este egal cu 0, 1 până la v și
u și v și v și v.
Deci, dacă doriți să scrieți
acest algoritm de jos în sus,
scrieți doar  acest
triplu cu patru bucle
și apoi conectați această
relație de recurență aici.
Și gândiți-vă la d ca pe un
tabel, ca pe o mapare de set,
în loc de un apel de funcție.
Și boom, în patru rânduri,
ai algoritmul tău,
doar că ai
nevoie și de un caz de bază.
Cazul de bază aici este u, v, 0.
Deci trebuie să definesc
ce înseamnă asta.
Dar când k este egal cu 0,
setul de la 1 la k este gol.
Deci, tot ce am voie să folosesc
sunt vârfurile mele u și v.
Există trei cazuri pentru aceasta--
0 dacă u este egal cu v. Este w de u, v
dacă există o margine de la u la v. În
caz contrar, este infinit.
BINE.
Dar caz de bază ușor,
timp constant pentru fiecare.
Și atunci
problemele inițiale pe care vrem să le rezolvăm
sunt delta u, v, dimensiunea lui
v. Pentru că îmi amintesc
vârfurile de la 1 la dimensiunea lui
v. Și dacă k este egal cu dimensiunea lui v,
asta înseamnă că pot
folosi toate vârfurile mele.
Deci, acestea sunt cele
mai scurte căi obișnuite.
Aceasta presupune că nu există
cicluri negative de greutate.
Știm deja cum să
facem detectarea ciclului negativ al greutății
, așa că nu o să
mai vorbesc despre asta.
Dar apoi, aceasta va fi
calea mea cea mai scurtă pentru că...
da.
Am presupus implicit aici
că calea mea a fost simplă
pentru că mi-am imaginat că
folosesc k doar o dată --
0 sau 1 dată.
Și asta este adevărat dacă
nu există cicluri negative de greutate.
Misto.
Și am făcut deja
partea de timp a SRTBOT.
Deci v cub algoritm.
Foarte simplu.
Practic, cinci linii
de cod și
aveți cele mai scurte căi pentru toate perechile.
Și dacă graficul tău este dens,
acesta este un timp de rulare grozav.
Dacă graficul dvs. nu este
dens, ar trebui să
utilizați Johnson, așa cum o veți face în--
sau așa cum ați implementat
în setul dvs. de probleme.
Da.
PUBLIC: Cum se
compară asta
cu doar rularea
algoritmului lui Dijkstra de câteva ori?
ERIK DEMAINE: Ce
zici de folosirea Dijkstra?
Să calculăm.
Running Dijkstra v times este
timpul de rulare al lui Johnson.
Rularea Dijkstra de
mai multe ori
este grozavă dacă graficul are
doar greutăți de margine nenegative.
Atunci ar trebui să
rulezi Dijkstra.
Obții acest timp de funcționare.
Și pentru graficele rare,
acest lucru este superior.
Dacă aveți
greutăți de margine negativă,
ar trebui să rulați Johnson, care
este Bellman-Ford o dată și apoi
Dijkstra de trei ori.
Și comparăm asta cu
v cubed, pe care tocmai l-am primit.
Deci, asta... Adică,
modul în care acestea se compară
depinde de modul în care v și E se leagă.
Pe de o parte,
poate v este theta E.
Acesta este ceea ce aș numi
un grafic foarte rar.
Și este destul de comun.
Apoi, timpul de rulare pe care îl
obținem aici este v pătrat log v--
aproximativ v pătrat.
Pe de altă parte, dacă
avem un grafic foarte dens,
v este teta E pătrat --
care, pentru grafice simple, este
cel mai mult la care am putea spera --
atunci acest
timp de rulare este v cub.
Dacă știți că v
este aproape de E pătrat,
atunci acest lucru vă oferă
oricum v cubit, de la termenul vE.
Deci, de ce să nu
folosiți acest algoritm?
Și adesea, știi, a
priori, dacă graficul tău
este foarte rar sau foarte dens
sau undeva la mijloc.
Dacă este undeva
la mijloc, ar
trebui să utilizați în continuare
algoritmul lui Johnson,
pentru că veți obține
beneficii de la sparsity
și trebuie să plătiți doar acest
vE în loc de v cubed.
Dar dacă știi din
timp că există o fracțiune constantă
a marginilor
, atunci folosește--
sau ai un grafic suficient de mic pe
care nu-ți pasă,
doar Floyd-Warshall pentru că
este simplu și rapid.
Buna intrebare.
Alte intrebari?
Acesta este un exemplu de
extindere a subproblemei -- unul
foarte neintuitiv
, în care folosim
un prefix al vârfurilor.
Dar observați, sunt din
nou prefixe --
un număr de
vârfuri de la 1 până la v.
Și am luat un prefix
al acelor vârfuri.
Așa că tocmai am rezolvat problema
folosind vârfurile prefixului de la 1
la k.
Deci este de fapt
o idee familiară.
Dacă tot ce ați văzut sunt
exemple de programare dinamică
de prefixe, sufixe,
subșiruri, de fapt,
este o modalitate destul de naturală
de a rezolva cele mai scurte căi -
poate chiar mai
natural decât acesta.
Oricum, în regulă.
Destul de drumuri scurte.  Să
rezolvăm
încă două probleme care
se află mai mult în
timoneria noastră standard, care
vor implica secvențe
de intrări, nu grafice.
Prima este
paranteza aritmetică.  În
primul rând, permiteți-mi să
definesc această problemă.
BINE.  Ni se
oferă o formulă
cu, să zicem, plus și timpi.
Permiteți-mi să vă dau un
exemplu real --
7 plus 4 ori 3 plus 5.
Acum, când citiți asta, pentru că
ați fost bine antrenat,
vă gândiți, OK, voi
înmulți mai întâi 4 și 3
pentru că asta  are o
prioritate mai mare,
iar apoi voi aduna
rezultatele.
Dar ceea ce o să vă las să faceți
este să introduceți această expresie în paranteze
așa cum doriți.
De exemplu, puteți adăuga
paranteze aici și aici.
Trebuie să faceți o
expresie de paranteză echilibrată,
o modalitate validă de a asocia --
sau nu doar a
perechi, ci o modalitate validă
de a evalua această expresie.
Orice comanda doriti.
Aș putea fi inconsecventă.
Aș putea, de exemplu, să fac această
sumă, apoi să fac acest produs
și apoi să fac această sumă.
Dar un fel de
arbore de expresie peste asta.
Și fiecare evaluează
la ceva.
Acesta este 11 și acesta este
8, deci acesta este 88.
Și scopul meu este să
maximizez acest calcul.
Și susțin că aceasta
este modalitatea de a maximiza
acel exemplu special.
Permiteți-mi să-l scriu în general
și să fac ca notația mea
să se potrivească cu notele mele.
Având o formulă a 0,
stea 1, a 1, stea 2, a 2
și așa mai departe până la
stea n minus 1, a n
minus 1, unde fiecare a i
este un număr întreg, așa cum ne
place în această clasă, și fiecare
stea i  este fie plus, fie ori.
OK, deci folosesc stea
ca operator generic.
Am ales steaua pentru că este
suprapunerea unei stele
peste un simbol al timpului.
Deci e clar.
Așa că vi se oferă o formulă,
orice amestec de plus și timpi
care vă place, care
implică n numere întregi.
Și scopul tău este să
plasezi paranteze
pentru a maximiza rezultatul.  Așa că
puteți încerca toate combinațiile
aici.
Dacă, de exemplu, iau
produsul de 4 ori 3, primesc 12.
Dacă fac asta mai întâi, primesc 12.
Apoi, dacă adun 5 și 7, primesc
24, adică mai puțin de 88.
Și le verific.
toate, iar acesta
este maximul pentru acel exemplu.
Interesanta problema.
Este un pic o
problemă cu jucăriile, dar este
motivată de o mulțime de
probleme reale, pe care
nu voi intra aici.
Pentru a aplica acest cadru, trebuie
să identificăm câteva subprobleme.
Aceasta este o problemă de secvență.  Ni se
oferă o
secvență de simboluri.
Și astfel, lucrul natural este
să încerci prefixe, sufixe
și subșiruri.  O
să trec înainte și să mă
gândesc mai întâi la relație.
Vreau să identific o
întrebare despre o subproblemă
sau soluția ei
care să mă permită să mă
reduc la subprobleme mai mici.
Acest lucru este puțin mai complicat.
Acest lucru este foarte diferit.
Nu facem întotdeauna ceva
în stânga sau în dreapta,
sau nu putem presupune că se
întâmplă ceva
în stânga, pentru că poate
luăm mai întâi un produs la mijloc
.
Dacă iau
mai întâi un produs la mijloc,
atunci am un rezultat aici,
dar mai am trei lucruri.
Am lucrul în stânga, îl
am în mijloc
și îl am
în dreapta.
Se dovedește a fi foarte
dezordonat să te gândești care
este prima operație.
Pentru că ne putem gândi
la asta ca la un copac,
în care luăm un produs aici -
luăm o sumă de 7 și
4 și 3 și 5 aici
și apoi luăm
produsul la rădăcină.
Dar nu știu ce
este copacul, nu?
Cunosc doar aceste numere
și acești operatori,
dar nu știu cum
să organizez acest arbore.
Ideea este, dacă te
gândești la acest copac,
care este singurul lucru
care este cel mai ușor de identificat?
Este rădăcina.
Rădăcina corespunde
ultimei operații pe care o
fac în acest calcul.
Ultimul lucru pe care l-am făcut
a fost să iau un produs.
Și asta este mult mai ușor, pentru că
dacă bănuiesc cine este la rădăcină -
care operator este la rădăcină -,
asta se descompune în mod natural
în subarborele din stânga
și subarborele din dreapta.
Și acestea vor
fi întotdeauna subșiruri.
Cam știm asta.
Acest nod corespunde
tot ceea ce
rămâne din acest operator, iar
acest subșir sau acest subarbore
corespunde tot ce este la
dreapta operatorului.
Deci aceasta este ideea noastră, dacă vom
ghici care operație,
steaua i, este evaluată ultima
sau, cu alte cuvinte, la rădăcină.
Deci aceasta este întrebarea.
Are n răspunsuri posibile --
Bănuiesc, de fapt, n
minus 1 de la operatorul 1,
operatorul n minus 1.
Și așa vom folosi
forța brută toate aceste alegeri.
Am vrut să încep de aici pentru că... să
realizez că dacă
aleg o stea
i în mijloc, care
ar putea fi lucrul potrivit,
ca în acest exemplu.
Steaua i este cea din mijloc -
operatorul de mijloc.
Eu mă descompun în mod natural
în tot ce se află
în stânga acelui
operator și tot
în partea dreaptă a acelui operator.
Acesta este un prefix.
Acesta este un sufix.
Deci s-ar putea să credeți, oh,
subproblemele mele sunt toate prefixe
și toate sufixe.
Dar ar fi
greșit, pentru că dacă
aveți o grămadă de operatori...
și spuneți că îl alegeți pe
acesta să fie ultimul.
Deci am un prefix
aici și un sufix aici.
Și apoi vor fi ceva--
în acest sufix, voi
alege un operator care să
fie rădăcina
acestuia și am un prefix
și un sufix al acestui sufix.
Dar, în special,
va trebui să evaluez
această subproblemă, care
este un prefix al unui sufix -
cu alte cuvinte, un subșir.
Deci, nu folosiți niciodată un amestec
de prefixe și sufixe.
Dacă aveți nevoie de ambele,
probabil că aveți nevoie de toate subșirurile.
Deci subproblemele noastre
vor fi subșiruri.
BINE.
Nu voi scrie
încă subproblemele,
pentru că
avem nevoie de o altă idee.
Deci, ce trebuie să
fac cu subșirul?  Voi
ghici
operatorul de mijloc
și apoi evaluez
subșirul din stânga,
evaluez subșirul din dreapta.
Ce încerc să fac
cu acele subșiruri?
Bănuiesc că încerc să
rezolv această problemă, adică să
pun paranteze
pentru a maximiza rezultatul
și apoi să returnez
rezultatul.
Și pot folosi
indicatori de parante pentru a reconstrui ceea ce
sunt de fapt parantezele.
Odată ce ghicesc care este
ultimul operator
, este suficient să maximizezi
piesa la dreapta
și să maximizezi
piesa la stânga?
Va maximiza întotdeauna
suma sau produsul meu
în funcție de ceea ce
este acest operator?
Și dacă te gândești la
asta o vreme.
Da.
Dacă vreau să maximizez suma, ar
trebui să maximizez cele două părți.
Și dacă vreau să
maximizez un produs, ar
trebui să maximizez cele două părți.
Pare corect.
Numai că nu am spus că
numerele mele întregi sunt pozitive.
Este adevărat dacă
numerele dvs. întregi sunt pozitive.
Dar pentru a face această problemă
mai interesantă,
vom permite
numerelor întregi să fie negative.
De exemplu, 7 plus minus
4 ori 3 plus minus 5.
Așa că tocmai am adăugat
câteva minusuri
la câteva numere de aici.
Atunci nu mai este mai bine
să le împerechezi în acest fel.
Dacă le împerechez
astfel, așa,
sau dacă adaug paranteze în
acest fel, primesc 3 aici
și primesc minus 2 aici.
Așa că obțin-- produsul
acestuia este negativ 6,
ceea ce probabil
nu este maxim.
De fapt, pot face
mai bine, cred,
făcând ultimul operator din stânga.
Deci aceasta, susțin, cea
mai bună parantelizare,
dacă mi-am amintit corect.
Aceasta înseamnă că minus 2 ori
minus 4 este 8, plus 7 este 15.
Așa că am primit un
număr pozitiv - cu siguranță
mai bun decât
numărul negativ pe care l-am primit.
Eu susțin că acesta este cel mai bun.
Și proprietatea cheie
aici este că, atunci când
luăm un produs din
două numere negative,
obținem un număr pozitiv.
Uneori, chiar
vrei să faci lucrurile mici,
pentru că mic ar putea
însemna foarte negativ.
Luați două
numere negative foarte mari - numere
negative foarte mici
, cu alte cuvinte.  Le
iei produsul, primești
un produs foarte mare, pozitiv,
pentru că semnele se anulează.
BINE.
Deci asta pare complicat.
Vrem să lucrăm la
subșiruri, dar
nu știm dacă
încercăm să maximizăm
sau ați putea crede că, ei
bine, poate
încerc să maximizez
valoarea absolută.
Dar asta nu e bine.
Poate per total, pe
toată această expresie,
primesc negativ 1 milion.
Și nu asta mi-am dorit.
Am vrut să maximizez suma.
Deci mai trebuie să
rezolv evaluarea maximă pe
care o pot obține,
paranteza maximă,
dar trebuie să rezolv și
paranteza minimă.
Dacă pot rezolva max și min,
voi cunoaște întreaga gamă pe care o
pot obține.
Și într-adevăr doar...
Îmi va păsa de min mai ales
când mă lasă să devin negativ.
Dar haideți să rezolvăm, în toate
cazurile, min și max,
și apoi doar
forța brută restul.
Asta am de gând
să scriu.
Deci asta a fost o motivație
și de ce vom
defini subproblemele în acest fel.  Voi
defini x din i,
virgula j, virgula opt to be--
opt, aici, va fi
fie min sau maxim.
Și aceasta este
extinderea subproblema mea.
Chiar îmi pasă de
max la sfârșit,
dar o să-mi pese
de min pe parcurs.
Și i, j va
specifica subșirul meu.
Deci aceasta va
fi valoarea opt--
opt înseamnă aici „optim”
sau „optimizare”.
Valoarea opt pe care o pot obține pentru
subșirul a i stea plus 1,
a i plus 1 și așa mai departe pentru a
stea j minus 1, a j minus 1.
OK.  Fiind
atent să-mi
corectez indicii aici.
Și vreau 0 mai mic sau
egal cu i, mai mic decât j,
mai mic decât egal cu n.
Reclam și optez așa.
BINE.
Voi obține valoarea minimă
și valoarea maximă separat.
Sunt două
subprobleme diferite.
Aceasta este expansiunea mea.
Aceasta este
constrângerea pe care o adaug.
Și mă concentrez doar pe acest
subșir de la i inclusiv
la j exclusiv.
BINE.
Așa că susțin că acestea sunt
subprobleme bune.  Să
scriem o
relație de recurență.
BINE.
Raporta.
Vreau să scriu x din
i, j, opt pe stânga.
Și vreau să optimizez-- deci
acesta va fi minim sau maxim--
pe un set de opțiuni.
Care este setul meu de alegeri?  Ei
bine, așa cum am spus,
vreau să ghicesc
care este ultima
operațiune evaluată.
Am scris steaua i aici, dar
steaua i este deja definită,
așa că voi folosi steaua k.
Deci, voi ghici care
dintre operațiile mele între i
plus 1 și j minus 1 este
ultima și evaluez.
Și asta descompune
tot ce a rămas din k.
Deci ar fi x din i,
virgula k, virgula ceva.
Și apoi vom face
operatorul steaua k pe partea
de după k, care este de la
k la j, ceva.
Și aleg între...
Cred că este i mai puțin
decât k mai puțin decât j.
k este un operator între ele,
pentru că am început i plus 1
și am terminat j minus 1.
Deci, acestea sunt
opțiunile posibile pentru k.  Le-am
încercat pe toate.
Aceasta este forța mea brută locală.
Și apoi iau ce
pot obține în stânga, ce
pot obține în dreapta
și le înmulțesc sau le adun
după ce
operatorul este plus sau ori.
Acum, ar trebui să o maximizez
sau să o minimizez pe aceasta?
Ar trebui să maximizez sau să o
minimizez pe aceasta?  Nu
știu.
Deci voi face
mai multă forță brută locală.  Ei
bine, să spunem doar
opt prime pentru stânga--
sau poate o voi numi
opt L pentru stânga
și opt R pentru partea dreaptă.
Și voi adăuga
asta la bucla mea de patru.  Să
încercăm doar să optăm L și să optăm R.
Luați toate opțiunile posibile
dintre min și max.
Acum, ai putea să te gândești bine -
și, pentru a adăuga, de exemplu,
dacă maximizezi,

trebuie să maximizezi doar cele două părți.
Și dacă minimizați,
puteți dovedi că toți
trebuie să minimizați cele două părți.
Dar pentru multiplicare,
este dezordonat.  Ar
putea fi, într-adevăr,
oricare dintre opțiuni.
Pentru că uneori,
când minimizi,
primești un termen negativ.
Uneori, nu.
Și deci depinde ce
încerci să faci.
Trebuie să luați în considerare
toate semnele.
Dar nu trebuie să ne gândim bine.
Putem doar să încercăm toate opțiunile.
Există doar patru
opțiuni pentru opt L
și opt R între min și max.
Puteți face min-min,
min-max, max-min și max-max.
Așa că încercați-- este doar o
înmulțire cu 4
în această buclă de patru.
Costul mare este
de fapt acesta,
deoarece există j
minus i opțiuni pentru k.
Există un număr constant de
opțiuni pentru opt L și opt R.
Și trebuie să dovediți
că acest lucru este corect.
Nu o voi face aici.
Dar ideea este că, dacă
încercați să minimizați sau să maximizați
suma sau produsul dvs.,
este suficient să știți în ce
intervale ar putea intra acestea.
Și
alegerea optimă va
fi întotdeauna o extremă în acel interval.  Le
luăm în considerare pe toate aici.
Și astfel obținem această recurență.
Acum, are nevoie de un
caz de bază și trebuie
să verificăm dacă este aciclic.
Dar ordinea topologică este
doar crescătoare j minus i.
Aceasta este ordinea obișnuită
pentru problemele subșirului,
deoarece aceasta crește
lungimea subșirului.
Deci, începeți cu
subșiruri foarte mici.
Aici, vom începe cu
lungimea 1 subșiruri.
Avem doar un a, eu acolo.
Deci acesta va
fi cazul nostru de bază.
Și crești până la
întregul șir.
Și nu
contează cum ordonăm
relativ să optăm atâta timp cât
creștem în j minus i,
pentru că i la k și
k la j vor
fi întotdeauna strict mai mici decât i la
j, și deci acest lucru va fi aciclic.
Cazul de bază este x
din i, i plus 1, opt.
Acesta este întotdeauna un i.
Nu contează ce
opțiune este, pentru că nu există
nimic... nu ai de ales.
Aveți doar un singur
număr în acel subșir,
pentru că suntem
exclusivi pe i plus 1.
Și atunci
problema inițială pe care vrem să o rezolvăm
este x de 0, n, max.
Ai putea de asemenea să rezolvi min și să
vezi cât de mic îl poți obține.
Deci, dacă ați dori să
maximizați valoarea absolută,
puteți rezolva
problema maximă și problema minimă
și puteți lua cea mai mare
dintre aceste două opțiuni.
Și cât timp
durează asta?  Ei
bine, câte
subprobleme există?
Pentru problemele subșirurilor,
avem n subprobleme pătrat.
Acum, înmulțim
numărul de subprobleme cu 2,
dar acesta este totuși n pătrat.
Deci avem n
subprobleme pătrat.
Și câtă muncă
facem pe subproblemă?  Ei
bine, așa cum am menționat,
facem opțiuni j minus i pentru k
și un număr constant de
opțiuni pentru opt L și opt R.
Deci acesta este theta j minus i,
care, dacă voi fi neglijent,
este cel mult mare.  O din n.
Și oricum se dovedește a fi
răspunsul corect.
Deci, există o cantitate liniară
de muncă nerecursivă.
De fapt, este ca
un număr triunghiular,
dar este totuși teta n cub.
Același timp de funcționare ca
v cubed pe care tocmai l-am primit.
Dar timp polinom.
Și acest lucru este destul de impresionant,
pentru că forțăm cu adevărat
toate
parantezele posibile.
Există aproximativ 4 până la
n, exponențial multe,
paranteze
ale unei expresii.
Dar găsim cel mai mare --
cel care evaluează
cea mai mare valoare și cel care
evaluează la cea
mai mică valoare în doar n
timp cubit -- polinom.
Și o cheie aici a fost
extinderea subproblemei,
unde noi, pe lângă
rezolvarea problemei max, am
rezolvat și
problema min, pentru că uneori,
doriți să luați două
numere negative foarte mici
și să le produceți împreună pentru a
obține un număr pozitiv mai mare.
Misto.
Întrebare?
PUBLIC: Ar
merge ceva prost
dacă aș adăuga minus sau împărți?
ERIK DEMAINE: Și dacă aș avea
operatori minus și împărțire?
Este o întrebare bună.
Sunt sigur că minus
ar trebui să funcționeze bine.
Dacă facem min și max,
acest lucru ar trebui să evalueze în continuare cel
mai mare
lucru pentru divizare.
Trebuie să mă gândesc la cazuri.
Bănuiesc că
funcționează, dar ceea ce
trebuie să dovedim este că
modalitatea de a maximiza sau a minimiza
o diviziune, să zicem, având în vedere două
numere în stânga și dreapta,
este că fie corespunde
maximizării sau minimizării
lucrului din stânga și
apoi  maximizând sau minimizând
lucrul din dreapta.
Deci, atâta timp cât ai
acest tip de...
nu este tocmai monotonitate.
Doar că, pentru a
calcula max sau min,
este suficient să cunoști max
și min din cele două părți.
Este ca aritmetica de intervale.
Știi, aritmetica de intervale?
Vreau să știu, care
sunt extremele pe care le
pot obține la
ieșirea unei diviziuni
dacă mi se dă că un număr
este într-un anumit interval aici
și un anumit interval aici?
Dacă răspunsul este întotdeauna, utilizați
unul dintre punctele finale extreme
aici și utilizați unul dintre
punctele finale extreme aici,
atunci acest algoritm va funcționa.
În caz contrar, toate pariurile sunt oprite.
Misto.
Deci, dacă negați--
dacă puneți un minus aici,
asta va funcționa bine,
pentru că
anulează acest interval.
Și apoi este la fel ca suma.
Dar--
PUBLIC: [INAUDIBIL]
ERIK DEMAINE: Oh, un divizor--
dacă ești atent la 0, da.
De fapt, nu
funcționează, pentru că ne
pasă cât de aproape
poate ajunge acest lucru la 0 pentru divizare.  Ar
putea fi suficient
să le luăm în considerare.
Este ca, în loc să minimizez
și-- în loc să calculez
întregul interval, dacă
acest interval se întinde pe 0,
poate că trebuie să știu--
dacă 0 este aici, trebuie
să știu cât de aproape de 0
pot ajunge în
partea stângă și  cât de aproape de 0
pot ajunge pe partea dreaptă.
Încă doar patru
cantități pe care trebuie să le știu.
Bănuiesc că, pentru
împărțire, este suficient.
Da.
Grozav.
Rezolvată o mică problemă.
Apoi, am înmulți
spațiul subproblemei, în
loc de 2, cu 4.
Hei, poate ar trebui să
punem asta în final.
Nu, doar glumeam.
Acum este în curs,
așa că nu-l putem folosi.
Dar este un set grozav
de probleme, nu?
Puteți face multe cu
programarea dinamică.
Nu trebuie să fii atât de
inteligent, ci doar forță brută
orice pare greu.
Și când funcționează,
funcționează grozav.
Și această clasă se referă la
înțelegerea când funcționează
și când nu funcționează.
Desigur, vă vom oferi doar
probleme acolo unde funcționează.
Dar este important să
înțelegeți când nu funcționează.
De exemplu, DAG cele mai scurte
căi - acel algoritm
pe un non-DAG, foarte rău.
Timp infinit.
BINE.
Ultimul nostru exemplu
este degetarea la pian.
Aici, ni se oferă o
secvență de note t 0, t 1--
t pentru notă-- până la t n minus 1.
Acestea sunt note simple.
Și toate notele unice...
toate notele unice, nu?
Și avem degetele
pe mâini.
Acesta nu este ca un
algoritm cu două degete.
Acesta este
algoritmul cu cinci degete.
Deci, în general, voi
presupune
un
obiect antropomorf arbitrar.
Deci acesta este 5 pentru oameni,
majoritatea oamenilor.
Unii oameni... Cred că
maximul pentru fiecare mână este 7.
Ar putea fi mai mic.
Poate ai avut un accident.
O voi rezolva pentru F arbitrar.
Și ceea ce am dori să facem
este să atribuim degete notelor
pentru a spune pianistului nostru ce
deget să folosească pentru fiecare notă.  În
mod normal, când vi se
oferă partituri,
vă oferă doar o secvență
de note pe care doriți să le cântați.
Nu vă spune cu ce
deget doriți să îl jucați,
decât dacă aveți niște
broșuri de antrenament frumoase
și au câte un mic
număr deasupra fiecăreia.
Și le numesc
1, 2, 3, 4 sau 5
și, simetric,
1, 2, 3, 4, 5.
Iată un pian uriaș
pentru mâinile mele uriașe.
Dacă Jason ar fi aici,
ar putea cânta aceste note.
Așa că poate cânt asta
cu degetul întâi,
asta cu degetul al doilea.  Să
spunem că
fac o scară.
Așa că pot merge.
Și acum, cred,
modul obișnuit
de a face o cântar este să te
întinzi cu primul deget --
degetul al doilea, cred, și
apoi să faci ceva de genul acesta.
Nu?
BINE.  În
mod clar, nu știu cânte
sau cum să cânt la pian.
Dar aici sunt limite.
Pot... dacă
merg de la această notă
și vreau să trec la o
altă notă de aici,
OK, poate am o
întindere decentă de la primul deget
la al cincilea, dar
span de la primul deget
până la al doilea deget
este  nu la fel de mare.
Nu pot ajunge atât de departe.
Deci, dacă vreau să cânt această
notă și apoi această notă,
aș dori să încep aici
cu o figură foarte extremă
în stânga și apoi să merg
la o figură foarte extremă
în dreapta.  O să
oficializez această
problemă destul de abstract,
pentru că nu vreau să
intru în interpretarea muzicală.
Voi spune că
există o metrică d pentru,
dacă sunt la nota t
cu degetul f și
vreau să merg la nota
t prim cu degetul
f prim, atunci această funcție,
d din t, f, t  prim, f prim,
îmi dă dificultatea
de a face asta--
dificultatea de a cânta
nota t cu degetul f
și apoi de a cânta nota t
prim cu degetul f prim.
Acest w este „cu”.
Deci aceasta este o
dificultate de tranziție.
Nu o să-mi fac griji cu privire la
dificultatea întregii piese
decât să spun, ei bine,
trebuie să cânt această notă,
apoi trebuie să cânt această notă.
Și deocamdată, doar note simple.
Cântați o singură notă
cu mâna dreaptă,
apoi cântați o
altă notă
cu mâna dreaptă,
apoi o altă notă
cu mâna dreaptă.  Să
presupunem că nu există pauze
deocamdată... fără odihnă.
Grozav.
Deci avem această dificultate
de a trece de la a-a notă
la i plus prima notă.
Și atunci scopul nostru este să minimizăm
suma dificultăților.
Suma minimă de d ti
fi ti plus 1, plus 1.
Și acestea-- f i și f i plus
1 este ceea ce vrem să calculăm.
Nu știm ce
degete să folosim.
Ni se oferă doar
ce note să cântăm.
Aceasta este de fapt
o problemă firească.
Există o mulțime de lucrări
despre această problemă.
Am citit o grămadă de ele --
evident că nu foarte bine,
dar cum să cânți cântare.
Dar există note precum-- există
constrângeri
în asta-- de obicei,
oamenii scriu această măsură ca o
sumă de termeni de penalizare diferiți,
dacă vreau să
reduc la minimum dificultatea.
Dificultatea este mare dacă
cânt o notă departe în stânga.
Deci, dacă trec de la o
notă joasă la o notă înaltă,
este mai ușor de făcut dacă
folosesc un deget cu numere mai mici
și merg la un
deget cu numere mai mari.
Nu vrei să
treci, așa cum făceam eu,
de la un deget cu numere mari
la un deget cu numere mici
pentru a cânta o notă în dreapta.
Asta e enervant.
Aș dori să fac o
misiune, dacă pot,
care să evite asta.
Așa că voi avea doar o penalizare
de, cum ar fi, 100 dacă se întâmplă asta
și 0 dacă nu se întâmplă,
rezumă o mulțime de termeni ca ăsta.
Alte exemple sunt, evitați degetele al
patrulea și al cincilea --
degete slabe --
sau, dacă cânt o porțiune
a melodiei care este legato,
atunci nu vreau să
folosesc același deget
pentru a cânta două note
imediat după  alte.
Trebuie să folosesc două
degete diferite pentru asta.
Deci aveți o penalizare dacă f i este
egal cu f i plus 1 și aceste două
note nu sunt la fel.
Apoi... și suntem
în modul legato -
apoi adăugăm un termen de penalizare.
Și lucruri de genul ăsta.  Aș
prefera... dacă trec
de la o notă foarte joasă la o
notă foarte înaltă, aș dori să
folosesc degete mai extreme.
Lucruri de genul acela.
Dar vom presupune doar că
această funcție d ne este dată.
Este o dimensiune de polinom.
Dacă vă imaginați că
notele de pe tastatură
sunt note de final sau note m, atunci
unele polinom și dimensiunea m
pentru această funcție.
Cum rezolvăm această problemă?  Am
rămas fără timp, așa că
permiteți-mi să vă dau ideea.
Și aceasta va folosi
extinderea subproblemei.
Deci subproblemele vor
fi x din i, virgula f--
aceasta este dificultatea totală minimă
de a reda sufix--
pentru că îmi plac sufixele-- t i
până la t n minus 1, începând
cu degetul f pe nota t i.
Subproblemele evidente ar
fi fără această constrângere.
Aceasta este aici o
constrângere a problemei.
Și ați putea încerca să definiți
subproblemele la fel cum,
care este cel mai bun mod
de a reda un sufix?
Dar susțin că este
important să știm cu
ce deget începem.
Deci vom înmulți
numărul de subprobleme
cu capitalul F, care este doar 5.
Deci o extindere foarte mică a
subproblemei.
Și apoi vom
constrânge
aceste subprobleme să
spună, ei bine, ce se întâmplă dacă aș
începe cu primul deget?
Dacă aș începe
cu al doilea deget?
Dacă... până la
al cincilea deget.
Încearcă-le pe toate.
Apoi, se pare, pot
scrie o relație, care
este X din i f este egal cu min.
Ce ar trebui să min peste?
Voi ghici doar că asta--
Mi s-a spus deja care
este primul meu deget să folosesc--
ce deget
ar trebui să folosesc pentru ti.
Deci, care este următorul
lucru care contează?  Ei
bine, bănuiesc ce deget
să folosești pentru t i plus 1,
nota următoare.
Care este următorul deget pe care îl folosesc?
Voi numi acel f
prim și voi minimiza peste
f prim, între
unu și capital,
F din
sufixul rămas, începând
cu f prim, plus funcția mea de dificultate
de la t i, virgula f,
la t i plus 1, virgulă f prim.
Capătul suportului.
BINE.
Deci se
întâmplă cam multe aici.
Acesta este un f prim minuscul.
Dar, de fapt, dacă
te gândești la ce
aș vrea să scriu
recurența, ei
bine, încep cu
sufixul i,
aș vrea să recurg
la sufixul mai mic,
deci este X din i plus 1.
Deci aici, dacă știu  că
prioritizez numărul degetului meu
pentru i,
atunci sunt pentru a
apela chiar această
funcție, trebuie
să știu ce deget
folosesc 4 plus 1.
Odată ce te hotărăști asupra
acestor subprobleme,
este foarte evident că ai nevoie  a
ghici care este următorul deget
și apoi recurge
la acel deget -
recureți la
sufixul rămas al acelui deget.
Acum, de ce trebuia să știm
ce sunt aceste degete?
De ce nu ghiciți care
este primul deget?  Ei
bine, are de-a face cu
această funcție de dificultate.
Pentru această
funcție de dificultate, știu
că vreau să măsor
dificultatea de la t i
la t i plus 1.
Și pentru a face asta, deoarece această
funcție este parametrizată
de patru lucruri, trebuie să
știu atât degetul pentru t i,
cât și, în același timp  ,
degetul pentru t i plus 1.
Dacă scot acest f, aș putea
adăuga un min peste un deget,
dar nu prea pot adăuga
un min peste două degete.
Deci, ce face asta,
parametrizând cu f aici
și notând optimul
pentru fiecare deget de început f,
pot-- într-un anumit sens, îmi
amintesc,
în acest apel, cu ce
deget am început.
Pentru că i-am spus, trebuie să
începi cu degetul f prim.
Și deci local la X i, f,
știu ce deget f prim
este folosit pentru t i plus 1.
Și, de asemenea, din cauza
definiției lui X i, f,
știu ce deget
folosesc pentru t i.
Și astfel ajung să cunosc
ambele degete.
Unul iese din acest
min și celălalt
îmi este dat ca
acest parametru.
Și apoi, desigur, dacă
pot rezolva aceste probleme,
pot rezolva problema inițială
doar cu încă un min de 1
până la F majuscul de x 0 f mic.
Nu știu cu ce
deget să încep,
dar sunt doar f alegeri.
Și atunci, această recurență
îmi oferă soluția generală.
Și voi trece doar la timp.
Avem nevoie de un caz de bază
și o ordine topologică.
Dar este n f timp pătrat.
Există de n ori
f subprobleme aici.
Și pentru fiecare, fac o
optimizare pe f alegeri,
așa că obțin de n ori f pătrat.
Este un polinom.
Și dacă f este o constantă, acesta
este de fapt timp liniar.
DP foarte rapid.
Acum, ceea ce am descris
aici este pentru o mână,
o notă la un moment dat.
Dar puteți generaliza acest lucru la
două mâini, fiecare cu o notă.  Ei
bine, sunt doar zece degete.
Deci, puteți rezolva acest lucru
separat pentru mâna dreaptă
și mâna stângă, dacă știți
ce note sunt jucate
cu mâna stângă și mâna dreaptă.
Dar unele piese,
asta nu este evident.
Deci, pentru a o face mai interesantă,
ce se întâmplă dacă aveți mai multe note
în același timp?
Și să spunem...
Cred că este rezonabil să spunem că
poți reda doar până la f note
la un moment dat, câte 1 pentru fiecare deget.
Și astfel ai o
limită superioară a numărului
de note la un moment dat pe care le
cântăm, ceea ce este bine.
Oh, am un desen
cu acest DP, apropo,
ca subproblema DAG.
Aceasta este
problema inițială,
adică nu știm cu ce
deget să începem.
Dar atunci avem aici doar un
grafic bipartit complet,
unde scriem pe fiecare
dintre aceste muchii, care
este dificultatea
acestei tranziții?
Axa y aici este
degetul pe care îl folosesc --
1, 2, 3, 4, 5 --
iar axa x este
sufixul pe care îl iau în considerare.  Cu
ce ​​notă încep?
Și astfel ați putea rezolva acest lucru
cu cele mai scurte căi într-un DAG,
sau ați putea să
o rezolvați direct
ca DP, fie de
sus în jos, fie de jos în sus.
BINE.
Sărind înainte, dacă faci
mai multe note simultan, în
loc de această alegere cu degetul,
care avea doar opțiuni f,
avem...
ce scriu aici?
t la cele f posibile
stări, unde
t este numărul maxim de
note pe care le-aș putea cânta deodată.
Și de obicei, acesta este
cel mult f, 1 pentru deget.
Dar am putea generaliza.
Și acesta este numărul de degete.
Așa că aș putea să mă ocup de toate cele 10
degete ale unui set tipic uman
de brațe--
mâini-- și să spun că sunt
cel mult 10.
Și deci acesta este 10 la 10. Este
o constantă mare,
dar este constantă -
ca 1 miliard corect.  ?
10 miliarde?
Dar atunci e că ori n.
Și poate că acei
timpi pătrați n
mă vor permite să enumerez exhaustiv
toate lucrurile posibile pe care le-aș
putea face
cu toate mâinile mele.
Puteți aplica acest lucru nu
numai la pian,
ci și la chitară --
și la Rock Band.
Rock Band este un
caz ușor în care aveți doar
cinci butoane și, de obicei,
doar patru degete pe care le folosiți.
Și asta nu
scoate cu adevărat niciun sunet,
așa că nu este atât de interesant.
Deci, în cazul în care f este egal cu 4, îl
puteți aplica pentru a afla în mod optim
care deget-- odată ce aveți
o funcție de dificultate a ce
tranziții sunt ușoare
și dificile pentru Rock Band,
atunci vă puteți da
seama optim de degetul
pentru melodiile Rock Band.
Cu o chitară adevărată, acest lucru
este puțin mai greu,
deoarece există
de fapt mai multe moduri
de a cânta aceeași notă.
De exemplu, pot cânta
nota acestui șir astfel.
Acestea ar trebui să
sune la fel --
dacă chitara mea ar fi fost perfect
acordată, ceea ce nu este.
Și acestea sunt proprietățile
corzilor și felul în care
aceste lucruri sunt jucate.
Deci, pe lângă
degetul pe care îl folosesc, ar
trebui să decid și pe ce
coardă să cânt nota respectivă.
Dacă tot ce mi se oferă sunt partituri
, note diferite de cântat, un
alt lucru pe care aș
putea ghici este pe ce
coardă să cânt nota respectivă.
Deci, de exemplu, poate vreau
să cânt aici melodia mea preferată.
[MUZICA]
PUBLIC: [APLAUZE]
ERIK DEMAINE: Super Mario
Brothers, cântecul meu preferat.
Aș putea continua, dar
de fapt nu pot continua.
Nu va fi la fel de impresionant.  De
fapt, nu știu să
cânt la chitară.
Dar există o mulțime de
opțiuni acolo, nu?
Am început să redăm această
notă pe acest șir.  Asta e
bine.
Aș fi putut să-l cânt și
pe acest șir.
Dar asta e mai multă
muncă pentru degetul meu,
așa că am o
funcție de penalizare care
spune, ei bine, dacă cânt o
coardă deschisă, este mult mai ușor.
Și apoi am avut o
tranziție de aici--
această notă [PLAYING A NOTE]
la această notă [PLAYING A NOTE]
la această notă.
[RĂCÂND O NOTĂ] Și dacă vă
concentrați pe degetul meu aici,
am ales să-mi folosesc
degetul arătător pentru primul,
pentru că acel deget arătător este
întotdeauna cel mai ușor de folosit,
dar îmi oferă și
mult spațiu
pentru a-mi muta mizicul peste  pana aici.
Și apoi îmi place să folosesc
degetul mijlociu pentru a veni aici.
Puteți folosi și
degetul arătător.
Este doar un
pic mai mult de atingere.
Deci trebuie să definiți
o funcție de dificultate.  Ar
putea depinde de cât de mari
sunt degetele tale.
Dar puteți face asta
și apoi optimiza,
folosind acești algoritmi,
care este cea mai bună
degetare la chitară pentru o anumită piesă -
o notă o dată sau
mai multe note la un moment dat.
Ai putea chiar să adaugi
parametri precum,
oh, poate vreau să cânt la bară.
Nu este un bar perfect.
Dar asta ar fi grozav
pentru mine să cânt această notă aici
jos și această notă aici -- un
exemplu prost.
Deci ai putea face alte
lucruri cu o chitară
pentru a o face mai interesantă și pentru a
generaliza acest program dinamic în mod
adecvat.
Dar cred că acest lucru
vă oferă o imagine despre
cum, cu
extinderea subproblemei,
pot surprinde aproape orice aspect
al unei probleme pe care mi-l doresc.
Atâta timp cât numărul de stări pe
care trebuie să le țin evidența
este mic, pot doar să înmulțesc
numărul de subprobleme
cu acea stare și pot
urmări orice fel de tranziție
de la o stare la alta, ceea ce
aș putea face și eu.  cu luarea
produsului unui grafic.
Dar programarea dinamică
vă oferă un fel de modalitate metodică
de a vă gândi la asta, prin
descoperirea unor proprietăți --
în acest caz, starea modului în care
degetele mele sunt aplicate
pe instrument -- și apoi pur și simplu
forțând
restul...
un cadru foarte puternic.