Aplicación de herramientas de negociación automática al problema del ajuste del Voronoi inverso

Abstract

Este trabajo de investigación basa su acción en el estudio del guiado eficiente del ajuste del Voronoi inverso, es decir, partiendo de una teselación en el plano se busca colocar un nodo en cada región de manera que las regiones de influencia de estos nodos se ajusten lo mejor posible a la teselación de Voronoi inicial. Se trata de un problema NP-duro y para el tratamiento del mismo se ha empleado una herramienta heurística conocida como “simulated annealing” o re cocido simulado, modulada con la capacidad de aceptar configuraciones de nodos que empeo ren el resultado con el objetivo de escapar del estancamiento de mínimos y máximos locales. Se ha tratado también de buscar la innovación y aplicar técnicas de negociación entre no dos con el objetivo de mejorar los resultados de las ejecuciones del clásico recocido simulado.

This research work bases its action on the study of efficient guiding of the adjustment of the reverse Voronoi, that is, starting from a tessellation in the plane, it is sought to place a node so that the regions of influence of these nodes adjust as best as possible to the initial Voronoi tessellation. Its an NP-hard problem and an heuristic tool known as si mulated annealing has been used to treat it, modulated with the ability to accept node configurations that worse the result in order to escape of local minimums and maximums. An attempt has also been made to seek innovation and apply negotiation techniques bet ween nodes in order to improve the results of executions of the classic simulated annealing.