Está claro que este problema suena como un problema de árbol de expansión mínimo. Sin embargo, no necesitamos tener un árbol conectado, podemos tener árboles disjuntos [matemáticos] W [/ matemáticos] que tengan cada uno de los módems.
El algoritmo de Prim no es adecuado porque siempre expande el árbol de expansión actual. Sin embargo, el algoritmo de Kruskal suena bien, comienza con todos los vértices desconectados y los conecta usando los bordes más baratos para tener un MST.
El problema es qué vértices deberían obtener los módems [math] W [/ math]. Necesitamos conectar todas las ciudades a uno de los módems, por lo que usar los bordes más baratos como en Kruskal es el camino a seguir.
Por lo tanto, ejecutamos el algoritmo de Kruskal hasta que tengamos componentes [matemáticos] W [/ matemáticos] conectados. Luego, cada componente obtiene uno de los módems.
- ¿Cuáles son las mejores prácticas para acelerar el pensamiento de mi algoritmo?
- ¿Cuántas veces aparece el número 1 en una serie de números del 1 al N? Necesito una explicación lógica, no una usando la computadora.
- ¿Cómo diseñaría un algoritmo para clasificar 100 millones de libros y encontrar duplicados funcionales?
- Cómo resolver UVa 1449 usando hashing
- ¿Qué significa: = significa en algoritmos?
Tuve un problema de rendimiento al ordenar todos los bordes [matemáticos] 10 ^ 6 [/ matemáticos], pero lo optimicé usando cubos, por ejemplo, coloque los bordes con un costo <40000 en el primer cubo, 40000 a 80000 en el segundo cubo, y así en.
De esta manera, procesamos los bordes más baratos y solo miramos los otros si es necesario. En un gráfico con 1000 vértices, es poco probable que los bordes que conectan los nodos más lejanos sean relevantes.
