Búsqueda bidireccional aplicada al 'Another Solution Problem'

Abstract

[ES] El Shortest Path Problem (SPP) es uno de los problemas de búsqueda más estudiados en la literatura, razón por la que han cobrado interés otros problemas relacionados como el Another Solution Problem (ASP). El ASP se enuncia como el problema en el que, dada una solución óptima, el objetivo es encontrar la siguiente solución óptima. En este proyecto se propone abordar el problema mediante la aplicación de técnicas de búsqueda bidireccional de modo que el punto en el que se encuentren los dos procesos de búsqueda, comenzando uno por el vértice inicial y otro por el vértice final, determinará el segundo camino óptimo.

[CA] El Shortest Path Problem és un dels problemes de cerca de camins més estudiats en la literatura, raó per la qual altres problemes com l’Another Solution Problem (ASP) han guanyat interés. L’ASP s’enuncia com el problema en el qual, donada una solució òptima, l’objetiu és trobar la següent solució òptima. En aquest projecte es proposa resoldre el problema mitjançant l’aplicació de tècniques de cerca bidireccional de manera que el punt en el qual s’encontren els dos processos de cerca, començant un pel vèrtex inicial i l’altre pel vèrtex final, determina el segon camí òptim.

[EN] The Shortest Path Problem (SPP) is a well-known and studied problem in the literature. Originated from this problem, other interesting and related problems have emerged like the Another Solution Problem (ASP). Given a problem and its optimal solution the ASP lies in finding the subsequent optimal solution. There exist different techniques to address the ASP but most of them present several limitations due to the exploration of unnecessary paths or an unsucessful search. In this project we propose to address the ASP by using techniques of bidirectional search, which consist in starting two search process, from the initial and final nodes, respectively, such that the node in which both searches find will determine the second best solution.