logo móvil

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

Descargar PDF

Acceso abierto

Artículo científico


Categoría

Matemáticas

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 14

Citaciones: Sin citaciones


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.

Documentos Relacionados

Temas Virtualpro