Resumen

El grafo es un modelo de red compleja importante para describir la relación entre varias entidades en aplicaciones reales, incluyendo grafo de conocimiento, red social y red de tráfico. La consulta de camino más corto es un problema importante en los grafos y ha sido ampliamente estudiado. Este artículo estudia un caso especial del problema del camino más corto para encontrar el camino más corto que pase por un conjunto de vértices especificado por el usuario, lo cual es NP-duro. La mayoría de los métodos existentes calculan todas las permutaciones para los vértices dados y luego encuentran la más corta de entre esas permutaciones. Sin embargo, el costo computacional es extremadamente caro cuando el tamaño del grafo o del conjunto de vértices dados es grande. En este artículo, primero proponemos un nuevo algoritmo heurístico exacto en forma de búsqueda de mejor primero y luego damos dos técnicas de optimización para mejorar la eficiencia. Además, proponemos un algoritmo heurístico aproximado en tiempo polinómico para este problema en grafos grandes. Demostramos que el lí

• Materias:Modelo de tráfico Sistemas antifrágiles Sistemas multiagente Componentes complejos
• Subjects:Traffic model Anti-fragile systems Multiagent systems Complex components
• Palabras claves:Modelo de red compleja; Consulta de camino más corto; Vértices; NP-difícil; Algoritmo heurístico; Eficiencia
• Keywords:Complex network model; Shortest path query; Vertices; NP-hard; Heuristic algorithm; Efficiency