Cuvinte - Programare dinamica

[•maritim]

Salut la toata lumea.

Am gasit intr-o culegere o problema ce suna cam asa:
Se dau N cuvinte (cuvintele contin doar caracterele 'a' ... 'z') si se cere sa se gaseasca cea mai lunga secventa astfel incat pentru fiecare cuvant i din secventa, prima litera a cuvantului i sa fie mai mare decat ultima litera a cuvantului i-1.

De exemplu : N = 4 si cuvintele sunt ana, capat, merge, repede.
Raspuns: cea mai lunga secventa = 3, secventa ana merge repede.

Cuvintele se pot gasi si in alta ordine decat cea initiala.

Solutii ca backtracking sau reprezentarea celor N cuvinte sub forma unui graf orientat si gasirea celui mai lung lant elemntar am gasit si eu. As vrea daca stie cineva daca aceasta problema se poate rezolva cu programare dinamica si daca da cum se poate, sa-mi dea un hint, sau sa-mi explice algoritmul (problema nu e departe de problema Zmeu2 de la OJI 2003) .

V-as fi recunoscator daca mi-ati oferi un raspuns. Va multumesc frumos si o zi buna!

[•skull]

Eu as face asa: best[ i ] = cel mai lung subsir care se incheie la pozitia i(include cuvantul de pe pozitia i). Problema este foarte asemenatoare cu cea a subsirului crescator maximal.

Succes!

[•pauldb]

Eu as face asa: best[ i ] = cel mai lung subsir care se incheie la pozitia i(include cuvantul de pe pozitia i). Problema este foarte asemenatoare cu cea a subsirului crescator maximal.

Succes!

Cred ca ai omis restrictia asta:

Cuvintele se pot gasi si in alta ordine decat cea initiala.

[•maritim]

Multumesc frumos pentru raspuns si imi pare rau ca am folosit cuvantul "secventa" deoarece se intelege gresit problema. Dupa cum a punctat si Paul, cuvintele se pot afla si in alta ordine decat cea initiala, altfel rezolvarea s-ar putea reduce la ceea ce ai spus si tu in post .

Any other opinions about the problem ?

[•crushack]

e destul de usor , ti un tablou T[ x ] = cat de lung pot sa fac un lant de cuvinte si primul cuvant sa aiba prima litera x,

parcurgi cuvintele intr-o ordine oarecare , si pt fiecare cuvant cu ultima cifra = uc , si prima cifra = pc
faci T[pc]= max( T[pc] , max{ T[ i ] | i='a'..uc-1 } + 1 )

Rezultatul va fi maximul dintre T[ x ] cu x='a'..'z'.
Sper ca te ajuta .

[•klamathix]

e destul de usor , ti un tablou T[ x ] = cat de lung pot sa fac un lant de cuvinte si primul cuvant sa aiba prima litera x,

parcurgi cuvintele intr-o ordine oarecare , si pt fiecare cuvant cu ultima cifra = uc , si prima cifra = pc
faci T[pc]= max( T[pc] , max{ T[ i ] | i='a'..uc-1 } + 1 )

Rezultatul va fi maximul dintre T[ x ] cu x='a'..'z'.
Sper ca te ajuta .

2
D A

Iti da 1.
Treaba cu 'ordinea oarecare' nu prea merge

@maritim esti sigur ca nu e NP-completa?

[•crushack]

nu e np completa. Exista algoritm in O(N^2)
Da, ai dreptate. Ma gandeam la o optimizare.

[•maritim]

Multumesc pentru raspunsuri.

@Popescu Silviu tot depinde de ordinea initiala a cuvintelor.

@Mihai Calancea nu sunt sigur ca problema nu e NP-completa. Mi s-a parut o problema interesanta si m-am gandit cum as putea sa o rezolv prin programare dinamica, fara sa ajung la o astfel de solutie am dorit s-o impartasesc si celorlalti, poate stie cineva.

Cunoaste cineva vreo rezolvare ?

Multumesc!

[•crushack]

Ti se da vre-o limita pentru N?
Acum am inteles cum trebuie problema , s-ar putea sa fie NP-completa

[•maritim]

Nu , nu are nicio limita N-ul. Daca ar fi sa dau o limita de la mine as zice poate 1000...

Daca stie cineva vreo solutie il rog sa posteze aici, daca intradevar e NP-completa ma multumesc cu un astfel de raspuns si cu rezolvarea polinomiala .

[•klamathix]

Nu , nu are nicio limita N-ul. Daca ar fi sa dau o limita de la mine as zice poate 1000...

Daca stie cineva vreo solutie il rog sa posteze aici, daca intradevar e NP-completa ma multumesc cu un astfel de raspuns si cu rezolvarea polinomiala .

cu rezolvarea exponentiala*. NP-completa inseamna ca nu exista inca/nu admite rezolvare in timp polinomial.

[•maritim]

Yup, ms ca m-ai corectat .

Daca se gaseste un raspuns astept posturi pe forum .