Algoritmus na optimalizaci číslovacího plánu

Pavel Troller patrol na sinus.cz
Čtvrtek Červenec 28 06:31:32 CEST 2011


Zdravím,
  potřebuji optimalizovat číslovací plán telefonní ústředny, zadaný v
"rozvinuté" formě v databázi např. dle tohoto vzoru:

0010 -> A
0011 -> A
0012 -> A
00130 -> A
00131 -> A
00132 -> A
001330 -> B
001331 -> B
001332 -> B
001333 -> A
0013340 -> A
0013341 -> C
0013342 -> A
....
0013349 -> A
001334 -> B
001335 -> A
....
001339 -> A
00134 -> A
....
00139 -> A
0014 -> A
0015 -> D
0016 -> A
....
0019 -> A

Ústředna je chytrá a umí "best match", takže tento číslovací plán je pro ni
zbytečně expandovaný. Cílem optimalizace by mělo být:

0013341 -> C
00133[0-24] -> B
0015 -> D
001 -> A

Čili pouhé 4 řádky pro daný příklad (zápisu v hranatých závorkách ústředna
také rozumí). Pro jednoduchost jsou vynechány znaky pro specifikaci, že nejde
o kompletní číslo, ale jen o prefix, to však na algoritmu nic nemění.

  Neřešil tohle už náhodou někdo ? Nejsem absolvent matfyzu, takže binární
stromy, trie a další vychytávky znám jen z doslechu a prakticky neumím 
pořádně používat, dovoluji si tvrdit, že bych asi něco napsal, ale bylo by to
hodně daleko od optima. Jak byste tento problém řešili vy ? Já bych tu databázi
celou uložil do nějakého pole, pak ho postupně procházel, hledal postupně od
nejdelších prefixů a pak zkoušel kusy "sdružovat" a eliminovat zbytečné 
položky... Prostě otročina, fuj. Myslím, že na to určitě existuje něco
elegantnějšího...

Zdraví Pavel




Další informace o konferenci Hw-list