Algoritmo de búsqueda de rutas con preferencias

Abstract

En este artículo se introduce un algoritmo de búsqueda que combina características de Métodos de Búsqueda en Haz y Búsqueda Voraz, juntamente con métodos de Decisión Multicriterio con el propósito de resolver problemas de búsqueda de rutas con restricciones de preferencias, donde los puntos se organizan en un multigrafo masivamente conectado, tal que esta representación resulta adecuada para modelar situaciones reales (o en su defecto, aproximaciones a la realidad). Además, en el enfoque propuesto se intenta dar una respuesta a situaciones en las cuales no es posible hallar una forma de conexión entre el nodo origen y el nodo destino respetando las preferencias introducidas por un usuario; al efecto, se emplean técnicas de determinación de proximidad denominadas K-ésimo Vecino Más Cercano para hallar una locación lo más cercana posible que satisfaga los requerimientos impuestos por las preferencias de usuario.

This article introduces a search algorithm that combines characteristics of Beam-Search and Voraqcious-Search methods, together with Multicriteria Decision methods with the purpose of solving search problems constrained routing preferences, where the points are arranged in a massively connected multigraph, such that this representation is suitable for modeling real situations (or failing that, approximations of reality). Furthermore, the proposed approach tries to respond to situations in which it is possible to find a form of connection between the source node and the destination node respecting the preferences introduced by a user, the purpose, techniques used for determining proximity called K-th nearest Neighbor to find a location as close as possible to meet the requirements imposed by the user preferences.