Tengo una pregunta que es parte de mi programa.Centro de búsqueda del árbol
Para un árbol T = (V, E) necesitamos encontrar el nodo v en el árbol que minimice la longitud de la ruta más larga de v a cualquier otro nodo.
Entonces, ¿cómo encontramos el centro del árbol? ¿Puede haber solo un centro o más?
Si alguien me puede dar un buen algoritmo para esto, así puedo tener la idea de cómo puedo encajar en mi programa.
¿Considera un árbol con dos nodos? ¿Cuál es el centro? Cualquiera de los dos bastará, ergo un árbol puede tener más de un centro.
Ahora, piense en lo que significa ser el centro. Si todas las ramas tienen la misma altura, el centro es la raíz (todas las rutas pasan por la raíz). Si las ramas son de diferentes alturas, entonces el centro debe ser la raíz o la rama con la mayor altura, de lo contrario, la ruta máxima es mayor que la altura de la rama más alta y la raíz sería una mejor opción. Ahora, ¿qué tan abajo tenemos que mirar la rama más alta? La mitad de la diferencia de altura entre la rama más alta (desde la raíz) y la siguiente rama más alta (si la diferencia es como máximo 1, la raíz será suficiente). Porque, a medida que bajamos por la rama más alta en un nivel, estamos alargando el camino hacia el nodo más profundo de la siguiente rama más alta en uno y reduciendo la distancia al nodo más profundo en la rama actual en uno. Eventualmente, serán iguales cuando haya atravesado la mitad de la diferencia en la profundidad. Ahora, cuando bajamos por la rama más alta, simplemente necesitamos elegir en cada nivel la subsección más alta. Si más de uno tiene la misma altura, simplemente elegimos uno arbitrariamente.
Básicamente, lo que está haciendo es encontrar la ruta más larga en el gráfico, que es la distancia entre la rama más alta del árbol y la siguiente rama más alta, y luego encontrar el nodo medio en esa rama. Debido a que puede haber varias rutas de la misma longitud que la ruta más larga y la longitud de la ruta más larga puede ser pareja, tiene múltiples centros posibles.
En lugar de hacer este problema tarea para usted, voy a pedir que a través del proceso de pensamiento que recibe la respuesta ...
1) ¿Qué haría usted con el abc gráfico (tres vértices, dos bordes, y definitivamente acíclico)? Imagina por un momento que tienes que poner algunas etiquetas en algunos de los vértices, sabes que vas a obtener el mínimo de la ruta más larga en el vértice "central". (b, con la etiqueta final "1") Pero hacer eso en un paso requiere poderes psíquicos. Así que pregúntate a qué b está a un paso de distancia. Si el camino más largo hacia b es 1, y hemos dado un paso atrás en ese camino, ¿cuál es la longitud de nuestro camino hasta ahora? (el camino más largo = 1, -1 para el último paso. Aha: 0). Entonces esa debe ser la etiqueta de las hojas.
2) ¿Qué sugiere esto como primer corte para un algoritmo? Marque las hojas "0", marque sus aguas arriba "1", marque sus aguas arriba "2" y así sucesivamente. Marchando desde las hojas y contando la distancia a medida que avanzamos ...
3) Umm ... Tenemos un problema con el gráfico a-b-c-d. (A partir de ahora, un vértice etiquetado será reemplazado por su etiqueta.) Etiquetar las hojas "0" da 0-bc-0 ... No podemos obtener dos centros ... Diablos, ¿qué hacemos de la manera más simple? condición 0-b-1? Queremos etiquetar b con "1" y "2" ... Manejar los que están en orden inverso ...
En 0-b-1, si ampliamos el camino desde la izquierda a la izquierda, obtenemos un ruta de longitud 1. Si ampliamos la ruta desde la derecha de b, obtenemos 2. Queremos rastrear "la longitud de la ruta más larga desde v a cualquier otro nodo", por lo que queremos hacer un seguimiento de la ruta más larga hasta b. Eso significa que marcamos b con un "2".
0-b-1 -> 0-2-1
En 0-b-c-0, el equipo no hace realmente simultáneamente actualización by c. Actualiza uno de ellos, dando 0-1-c-0 o 0-b-1-0, y la próxima actualización da 0-1-2-0 o 0-2-1-0. Tanto byc son "centros" de este gráfico ya que cada uno de ellos cumple con la demanda "del nodo v en el árbol que minimiza la longitud de la ruta más larga desde v a cualquier otro nodo". (Esa longitud es 2.)
Esto lleva a otra observación: El resultado del cálculo no es etiquetar un gráfico, sino encontrar el último vértice que etiquetamos y/o el vértice que termina con la etiqueta más grande. (Es posible que no encontremos una buena manera de pedir etiquetas, por lo que necesitaremos encontrar el máximo al final. O tal vez lo haremos. Quién sabe)
4) Así que ahora tenemos algo así como: haga dos copias del gráfico: la copia etiquetada y la copia grabada. El primero almacenará las etiquetas y será el que tendrá la respuesta final. La copia reducida será cada vez más pequeña a medida que eliminemos los vértices sin etiqueta de ella (para encontrar nuevos vértices labelables). (Hay otras maneras de organizar esto para que sólo se utiliza una copia del gráfico Al llegar al final de la comprensión de esta respuesta, usted debe encontrar una manera de reducir este tipo de residuos..) Esquema:
label = 0
while the burndown graph is nonempty
collect all the leaves in the burndown-graph into the set X
for each leaf in the set X
if the leaf does not have a label
set the leaf's label (to the current value of label)
delete the leaf from the burn-down graph (these leafs are two copies of the same leaf in the input graph)
label = label+1
find the vertex with the largest label and return it
5) Si realmente observas esta carrera, notarás varias oportunidades para atajar. Incluyendo el reemplazo de la búsqueda en la última línea del esquema con un método mucho más rápido para reconocer la respuesta.
Y ahora para la estrategia general, consejos para problemas de algoritmo:
* Haga algunos pequeños ejemplos a mano. Si no entiende cómo resolver los casos pequeños, no hay manera de que pueda saltar directamente y decirle a la computadora cómo hacer los casos más grandes. * Si alguno de los pasos anteriores parece desmotivado o totalmente opaco, deberá estudiar mucho, mucho más para hacerlo bien en Informática. Puede ser la Informática no es para usted ...
Hay dos enfoques para hacer esto (las dos carreras en el mismo tiempo):
Seleccione cualquier vértice v1 en su árbol. Ejecute BFS desde este vértice. El último vértice (v2) que procederá será el vértice más alejado de v1. Ahora ejecute otro BFS, esta vez desde el vértice v2 y obtenga el último vértice v3.
La ruta de v2 a v3 es el diámetro del árbol y su centro se encuentra en alguna parte. Más precisamente, se encuentra en el medio de eso. Si la ruta tiene 2n + 1 puntos, solo habrá 1 centro (en la posición n + 1). Si la ruta tiene 2n puntos, habrá dos centros en las posiciones n y n + 1.
Solo utiliza 2 llamadas BFS que se ejecutan en 2 * O(V) tiempo.
Si el punto medio exacto no existe, ¿cómo podríamos elegir? Quiero decir, si la forma más larga es a-b-c, a-b tiene longitud 1, y b-c tiene longitud 2?¿O un ejemplo más complejo? – cnhk
Elija uno arbitrariamente, si solo necesita un nodo que califica, o construya un conjunto de centros, si necesita todos los que califiquen. – tvanfosson