Jozef Kratica
Slobodan Radojević
Vladimir Filipović
Ana Šćepanović
It has been shown that in tree search problems exists cases, in which small change of node and edge values, product large change of problem complexity (execution time). That appearance, in which problem complexity transiting from exponential to polynomial (in the search depth), calling phase transition.
In this paper we show epsilon-transformation as method of using phase transition, in which tree search problem of exponential complexity we transforming to search problem of polynomial complexity. However, optimal solution of search on transformed-tree, is not optimal solution of initial problem, but is near to optimal (suboptimal solution).
Keywords: Epsilon-transformation; Tree search; Phase transition; Combinatorial optimization
Back to Jozef's Papers Home Page | Back to Jozef's Home Page