Un reinicio de búsqueda local para resolver el problema de búsqueda de cliques con peso superior diversificado
Autores: Wu, Jun; Yin, Minghao
Idioma: Inglés
Editor: MDPI
Año: 2021
Acceso abierto
Artículo científico
Categoría
Matemáticas
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 14
Citaciones: Sin citaciones
El problema de búsqueda de cliques de peso superior diversificado (DTKWC) es una generalización importante del problema de búsqueda de cliques de peso superior diversificado (DTKC) con aplicaciones prácticas. El problema de búsqueda de cliques de peso superior diversificado tiene como objetivo buscar cliques máximos que puedan cubrir el peso máximo en un grafo ponderado por vértices. En este trabajo, proponemos un algoritmo de búsqueda local novedoso llamado TOPKWCLQ para el problema de búsqueda de DTKWC que incluye principalmente dos estrategias. En primer lugar, se adopta una estrategia de reinicio, que repite los procesos de construcción y actualización del conjunto de cliques de peso máximo. En segundo lugar, se diseña una heurística de puntuación al dar diferentes prioridades a los cliques de peso máximo en el conjunto de candidatos. Mientras tanto, se construye un modelo de restricciones del problema de búsqueda de DTKWC para que se puedan evaluar las preocupaciones de la investigación. Los resultados experimentales muestran que el algoritmo propuesto TOPKWCLQ supera al algoritmo de comparación en grafos del mundo real a gran escala.
Descripción
El problema de búsqueda de cliques de peso superior diversificado (DTKWC) es una generalización importante del problema de búsqueda de cliques de peso superior diversificado (DTKC) con aplicaciones prácticas. El problema de búsqueda de cliques de peso superior diversificado tiene como objetivo buscar cliques máximos que puedan cubrir el peso máximo en un grafo ponderado por vértices. En este trabajo, proponemos un algoritmo de búsqueda local novedoso llamado TOPKWCLQ para el problema de búsqueda de DTKWC que incluye principalmente dos estrategias. En primer lugar, se adopta una estrategia de reinicio, que repite los procesos de construcción y actualización del conjunto de cliques de peso máximo. En segundo lugar, se diseña una heurística de puntuación al dar diferentes prioridades a los cliques de peso máximo en el conjunto de candidatos. Mientras tanto, se construye un modelo de restricciones del problema de búsqueda de DTKWC para que se puedan evaluar las preocupaciones de la investigación. Los resultados experimentales muestran que el algoritmo propuesto TOPKWCLQ supera al algoritmo de comparación en grafos del mundo real a gran escala.