mr Jozef Kratica
mr Slobodan Radojeviæ
Vladimir Filipović
Ana Šćepanović
Poznato je da u problemima pretrage drveta postoje slučajevi u kojima mala promena vrednosti čvorova i grana drveta, dovodi do drastične promene u složenosti (vremenu izvršavanja) algoritma. Takva pojava, gde složenost algoritma pretrage prelazi iz eksponencijalne u polinomijalnu (u funkciji od dubine drveta), naziva se fazni prelaz.
U ovom radu se prezentira epsilon-transformacija kao metod primene faznog prelaza, gde pretragu eksponencijalne složenosti malom promenom transformišemo u slučaj pretrage polinomijalne složenosti. Međutim, optimalno rešenje pretrage transformisanog drveta, nije i optimalno rešenje pretrage polaznog drveta, ali je blisko optimalnom (suboptimalno rešenje).
Ključne reči: Epsilon-transformacija; Pretraga drveta; Fazni prelaz; Kombinatorna optimizacija