Amo esa prueba. Para un lego, admito totalmente que es bastante técnico, pero es un excelente ejemplo de una prueba constructiva que utiliza diferentes definiciones de árbol y árboles de expansión. Supongo que estás hablando de la que está en este http://web.stanford.edu/class/ar…. Es muy bueno porque emplea un argumento de intercambio . Si estuviera hablando con alguien que no sabe casi nada, lo explicaría de esta manera (suponiendo que lo haya explicado la terminología y lo que hace el algoritmo de Prim):
- Suponga que tiene un MST que tiene un costo menor que una solución producida por Prim’s. Tenga en cuenta que si son iguales, entonces no hay nada que hacer aquí, así que suponga que los dos árboles son diferentes.
- Guíelos a través de cómo encontrar el borde de menor peso (y asegúrese de que sepan que la propiedad de elección codiciosa tiene y qué es eso). Esto es mediante el uso de algunas definiciones de árbol, como que debe existir una ruta entre cada dos vértices en un árbol de expansión. Esto es eligiendo una arista en la encontrada por el algoritmo de Prim e intercambiándola por otra arista a lo largo del camino en el supuesto mejor MST.
- Observe que al elegir el nuevo borde como parte del MST (se supone que es óptimo), puede mejorar el costo aún más de lo que está en el MST antes mientras conserva el hecho de que es un árbol de expansión.
- Repita hasta que no se puedan realizar más mejoras.
- Vaya, mira, es el mismo que produce el algoritmo de Prim; contradicción.
Tenga en cuenta que, por lo general, es suficiente convencer a alguien después de 1 iteración de que el mejor MST supuesto se transformará en el árbol de expansión que encuentra el algoritmo de Prim.
- ¿Qué algoritmo (s) de aprendizaje automático es el mejor para la regresión no lineal con un número limitado de datos?
- ¿Existe alguna noción del algoritmo más eficiente posible para alguna tarea?
- ¿Cuál es la diferencia entre un gráfico y un árbol en estructuras de datos y algoritmos?
- ¿Qué imprime el siguiente programa: #include int sum, count; vacío principal (vacío) { para (cuenta = 5; suma + = 'cuenta;) printf (% d, suma);}?
- Cómo resolver la recurrencia t (n) = 2t (n / 2) + n / logn
