Resultados 1 al 2 de 2

Tema: Busqueda en un arbol c++

  1. #1 Busqueda en un arbol c++ 
    Iniciado
    Fecha de ingreso
    Sep 2008
    Mensajes
    21
    Descargas
    0
    Uploads
    0
    Hola de nuevo!

    Tengo un problema con un ejercicio sobre árboles, llevo días dándole vueltas pero no se me ocurre como puedo solucionar éste ejercicio.

    Se me presenta un árbol en el que cada nodo representa un servidor. Los nodos de los servidores tienen un identificador (un entero) y estos números van de 1 a n (donde n es el tamaño del árbol) de manera que un árbol podria ser así:

    -------------------10
    ----------------/-------\
    ---------------9-------- 5
    --------------/--\----------\
    -------------3---4----------8
    ------------/--\------------/-\
    -----------1---2----------6---7

    Para hacerlo mas eficiente he hecho un vector de enteros de tamaño n que contiene la información de cada servidor.
    Cada servidor tiene un ancho de banda almacenado en el vector. A grandes rasgos lo que yo quiero es que dada una petición de descarga de un archivo, buscar el servidor o servidores más apropiados para esta descarga (sumando los anchos de banda). El caso es que los servidores deben pertenecer a un mismo camino (puedo coger el servidor 3 y el servidor 2, pero no el 9 y el 1 por ejemplo).

    Sé que igual es un poco complicado pero ya no se que hacer con este ejercicio, no se me ocurre ninguna manera así que agradeceré cualquier idea, gracias por leerlo!
    www.skytablog.blogspot.com
    Citar  
     

  2. #2  
    Avanzado
    Fecha de ingreso
    Jan 2004
    Ubicación
    Argentina
    Mensajes
    427
    Descargas
    1
    Uploads
    0
    Mira todo arbol tambien es un grafo dirigido, podes conciderarlo como un grafo, donde el peso de las aristas es el ancho de banda y aplicar dijkstra O(n log(n)) para tener el camino mas corto partiendo desde uno.

    La otra es dado el arbol aplicar backtraking con branch and bound. LO unico que es mas costoso aunque como es un arbol binario segun veo seria O(2^n)
    Osea, preguntas si es hoja te fijas si no lo es sumas el ancho de banda y vas a recursion por los dos lados, si es hoja lo comparas con la solucion aterior si es menor pasa a ser la nueva solucion y sino lo descartas asi con todo el arbol. El branch and bound lo aplicas ya que si no es hoja pero ya su suma es mayor que la solucion haces poda osea no llamas a la recursion.

    saludos
    Última edición por Markitos1024; 11-05-2012 a las 21:03 Razón: explico mejor el algoritmo, porque me quedo muy tecnico
    <<<<<<<<<<<<<<<<<<<<<>>>>>>>>>>>>>>>>>>>
    No llores porque termino, sonrie porque sucedio-.
    Citar  
     

Temas similares

  1. Árbol caído en la India
    Por hystd en el foro OFF-TOPIC
    Respuestas: 2
    Último mensaje: 16-09-2009, 23:20
  2. Copiar arbol de directorios CMD!!
    Por clinic en el foro WINDOWS
    Respuestas: 7
    Último mensaje: 24-09-2007, 10:26
  3. Árbol de familia de sistemas UNIX
    Por j8k6f4v9j en el foro LINUX - MAC - OTROS
    Respuestas: 8
    Último mensaje: 10-08-2007, 02:55
  4. Duda en un Arbol Binario de Busqueda en C++
    Por Deskicio en el foro PROGRAMACION DESKTOP
    Respuestas: 6
    Último mensaje: 01-04-2006, 22:37
  5. Visualizar Arbol Binario de Busqueda
    Por Deskicio en el foro GENERAL
    Respuestas: 2
    Último mensaje: 11-01-2006, 21:33

Marcadores

Marcadores

Permisos de publicación

  • No puedes crear nuevos temas
  • No puedes responder temas
  • No puedes subir archivos adjuntos
  • No puedes editar tus mensajes
  •