AlgoritmusEzen az órán - szándékosan - csak a "nyers erő" módszerét alkalmaztuk: visszalépéses kereséssel előállítottuk a megadott telefonszám összes olyan felbontását, amely szótárbeli szavakhoz rendelt számsorozatokból képezhető. Ehhez egyszerűen minden lehetséges állapotban megnéztük, hogy a még előállítandó karakterlánc kezdőszeletére melyik szótárbeli szó kódja illeszkedik, mindegyik megfelelő kezdőszeletet ki is próbáltuk, majd a megmaradt részre rekurzív meghívtuk eljárásunkat. Ha a teljes karakterláncot lefedtük, azt a rekurzió vizsgálja, és kezeli: például kiírja a talált megoldást, illetve minimumkiválasztást végez. KódokHatékonyabb algoritmusA feladatot átfogalmazhatjuk. Csak azzal a részproblémával foglalkozunk, hogy egy karakterláncot hogyan lehet minimális számú, rögzített szótárból választott karakterlánc összefűzéseként előállítani. Legyen a megadott karakterlánc N hosszú (karakterei c[1], c[2], ...,c[N]) és feleltessünk meg neki egy N+1 csúcsú gráfot a következő módon: - a 0. csúcs speciális, az 1., 2., ..., N. csúcs pedig karakterlánc karaktereinek felel meg
- az i. és j. (i<j) csúcs között akkor megy i->j irányított él, ha a c[i+1]c[i+2]...c[j] szó szerepel a szótárban
Ekkor a minimális szóból álló felbontás megfelel a gráfban egy legrövidebb 0 -> N útnak. Itt az út hossza a benne szereplő élek száma. Használhatjuk a szélességi bejárást, vagy a Disjkstra-algoritmust is, de a gráf egyszerű szerkezete miatt (és mert nincs túl sok csúcs), egy szimpla "négyzetes" algoritmus is célravezető: d[0] := 0
d[1..N] := végtelen
Ciklus i := 0-tól (N-1)-ig
Ha d[i] < végtelen akkor
Ciklus j := (i+1)-től N-ig
Ha van_él(i,j) és d[j] > d[i]+1 akkor
d[j] := d[i] + 1
//itt érdemes feljegyezni azt, hogy melyik szó felel meg az élnek
Elágazás vége
Ciklus vége
Elágazás vége
Ciklus vége
|
|