Quina diferència hi ha entre la programació dinàmica i el backtracking?


Resposta 1:

Memorització.

De la mateixa manera que el retrocés, la programació dinàmica resol un problema computant recursivament la resposta per a algun estat reduint-la a respostes d'altres estats. Però la diferència és que la programació dinàmica aprofita la superposició de les trucades recursives. Això vol dir que la programació dinàmica és efectiva quan es necessita la resposta per a un estat determinat moltes vegades durant l'execució de l'algorisme recursiu. Per tant, podem optimitzar la recursió emmagatzemant el resultat d’un estat en alguna taula de cerca (en la majoria dels casos, és una matriu d’adreces directes o una taula de hash) i evitar el càlcul del mateix estat moltes vegades. Aquesta idea s’assembla molt a la memòria cau, només en cache els resultats ja coneguts. Això pot millorar notablement el temps d’execució d’un algorisme (en molts casos, pot reduir un algorisme exponencial a un polinomi).

És més fàcil veure la diferència si considerem l’espai de l’estat com un gràfic. Considerem tot estat com a nodes i transicions d'estat com a vores dirigides. La programació dinàmica només es pot aplicar si aquest gràfic és acíclic (per què? Perquè, per trobar el valor d'un estat, s'han de valorar tots els seus subproblemes, però si tenim un cicle, alguns estats esdevenen el seu propi subproblem. ). Ara, la programació dinàmica serà efectiva si els nodes de la gràfica espacial de l'estat tenen molts camins fins a l'estat d'origen. Això vol dir que el valor d'aquest estat serà necessari moltes vegades. Vegem el gràfic d'espai d'estat per al càlcul del nombre de Fibonacci per a

n=5n = 5

on

F(n)=F(n1)+F(n2)F(n) = F(n - 1) + F(n - 2)

i

F(1)=F(0)=1F(1) = F(0) = 1

:

Com podem veure, hi ha molts camins cap a qualsevol estat (cosa que seria més evident si utilitzéssim el gràfic per a un text més gran

nn

). Així, podem utilitzar programació dinàmica per optimitzar la recursió.

Però si el gràfic de l'espai d'estat s'assembla més a un arbre, és a dir, si només hi ha una ruta única cap a un estat procedent de l'estat d'origen, no ens permetrà recordar el valor de l'estat, perquè és necessari una sola vegada, de manera que hauríem d’utilitzar el backtracking. Per exemple, si intentem calcular el nombre de cadenes de bits de longitud 3 amb dos o més 1s mitjançant backtracking, obtindrem el gràfic d'espai d'estat següent:


Resposta 2:

Programació dinàmica: normalment, hi ha una equació de recursió que es pot escriure. Així, el codi es pot escriure de manera recursiva, però també es pot escriure mitjançant tècniques de memoització: mitjançant una taula per crear valors memorats.

El retrocés fa servir la recursivitat per explorar branques, amb l’opció de tallar aprofundir en una branca, i així tornar d’hora i explorar una altra branca de l’arbre de la recursió. No hi ha memoització i acumulació de la dependència dels valors anteriors.

Similituds: les dues es poden escriure recursivament, però les tècniques són diferents, i es pot escriure programació dinàmica amb taules i memoization.