algorithm - puede - raiz pivotante ejemplos

Distancia más corta de la hoja a la raíz de un árbol dirigido

Question

Aquí hay un problema muy interesante que he encontrado: hay un árbol dirigido en el que el peso de cada nodo cambia con el tiempo y tengo que encontrar la distancia desde la raíz a algún nodo.

Planteamiento del problema:

• Hay una larga cola frente a un mostrador de boletos. Aquí están las consideraciones de la cola.
• Puede haber un máximo de 2 colas entrantes que se fusionan en un punto de unión
• Solo puede haber una cola de salida desde cualquier punto de unión
• Puede haber múltiples puntos de unión y las colas se mueven unidireccionalmente
• Sólo habrá un punto final de contador de tickets al que conducen todas las colas.
• Hay múltiples puntos de entrada para que los fanáticos lleguen al mostrador.
• Necesito diseñar un sistema que pueda sugerir a los fanáticos el "Camino óptimo" y su "Tiempo esperado" para llegar al mostrador.

El tiempo esperado para llegar al contador desde una cola depende de la cantidad de personas en esa cola más la cantidad de personas en las otras colas.

• El tiempo necesario para cruzar el mostrador de boletos y recibir el boleto es 1 unidad de tiempo.
• Supongamos que hay un policía parado en cada punto de unión cuyo trabajo es abrir la puerta de la unión para enviar a las personas de la cola (s) a la cola de salida. Si hay varias colas de entrada para un cruce, el policía enviará a los fans de cada cola uno por uno, alternativamente

Por ejemplo, si hay 2 colas de espera que contienen 3 seguidores cada una, la primera persona de la cola1 se enviará primero, seguida de la primera persona de la cola2, seguida de la siguiente persona de la cola1 y así sucesivamente. Es una selección alternativa entre las colas entrantes.

Declaración completa del problema

Para una entrada dada

• La primera línea contiene el número de uniones.
• La segunda línea contiene el número de colas.
• Las siguientes líneas ''e'' contienen tres valores: la unión inicial, la unión final y el número de personas en esta cola. (Este es también el número máximo de personas que pueden estar en esta cola).

Calcule el tiempo mínimo para que una persona llegue al mostrador de boletos que está a punto de ingresar en cualquier cola. Además, indique el camino que debe seguir para alcanzar el contador en el tiempo mínimo en el peor de los casos (en cada punto de unión, el policía comienza a elegir personas de la cola diferente a la hora para la que calculamos el tiempo mínimo).

¿Cómo se puede resolver este tipo de problema que varía con el tiempo?

Por ejemplo:

7
6
1 5 9
2 5 5 
3 6 1
4 6 3 
5 7 7 
6 7 4

El gráfico se ve así:

Punto de venta de entradas: 7

Puntos de entrada: 1, 2, 3, 4.

• Tiempo requerido para una persona que acaba de ingresar a la cola desde el punto de entrada 3: 1 persona de la cola (3,6) + 2 personas de la cola (4,6) + 4 personas de la cola (6,7) + 7 personas de la cola (5,7) + 1 persona de la cola (1,5) irá antes que esta persona.
  
  

Tiempo óptimo = 15

El camino es 3 -> 6 -> 7

Answer 1

Este problema se puede resolver encontrando la ruta más corta de cada nodo de entrada (hojas) al nodo de salida (raíz).

En mi implementación a continuación, utilicé una matriz de adyacencia para representar ese tipo de gráfico (dirigido), pero puedes considerarlo como un árbol binario (porque el problema definió un máximo de 2 colas de entrada para cada cruce).

Pseudocódigo

int shortestPath(root)
    if (both childs exists)
        return min(shortestPath(node->left),shortestPath(node->right))*2+1
    if (left child exists)
        return shortestPath(node->left)
    if (right child exists)
        return shortestPath(node->right)
    return 0; //no childs

La única diferencia entre una ruta más corta normal y este problema es que cada vez que tenemos dos colas entrantes, el policía envía a los fans de cada cola, uno por uno, alternativamente. Lo que significa que para pasar esa cola tomará el doble del tiempo +1 . El +1 se debe a que asumimos que comienza desde la ruta de la cola más larga.

Código C ++

Aquí hay un código C ++ en funcionamiento que devuelve un par tanto con el tiempo óptimo como con su ruta. En caso de que haya más de una ruta óptima, solo se devolverá una de ellas.

const pair<int,vector<int>>& min(const pair<int,vector<int>>& a, const pair<int,vector<int>>& b) {
  return (a.first < b.first) ? a : b;
}

pair<int,vector<int>> findShortestPath(vector<vector<int>>& graph, int v){
    vector<pair<int,vector<int>>> childs;
    for (int i=0; i<v; i++){
        if (graph[i][v] != -1){
            pair<int,vector<int>> path = findShortestPath(graph,i);
            path.second.push_back(v+1);
            childs.push_back(make_pair(path.first + graph[i][v], path.second));
        }
    }
    if (childs.size() == 2){
        pair<int,vector<int>> path = min(childs[0],childs[1]);
        return make_pair(path.first*2+1, path.second);
    }
    if (childs.size() == 1){
        return make_pair(childs[0].first,childs[0].second);
    }
    else{
        vector<int> start = {v+1};
        return make_pair(0,start);
    }
}

La complejidad de tiempo de este código es O(n^2) donde n es el número de vértices. También puede implementarlo en O(n) utilizando la representación de lista de adyacencia (= árbol binario).

Para completar, aquí está también el main para crear el gráfico a partir de la entrada dada e imprimir el tiempo y la ruta óptimos. Vea esta prueba en vivo de la entrada de su ejemplo

int main()
{
    int n, e;
    cin >> n; //num of vertices
    cin >> e; //num of queues
    vector<vector<int>> graph;

    //initialize graph matrix cells to -1
    graph.resize(n);
    for (int i=0;i<n;i++){
        graph[i].resize(n);
        for (int j=0;j<n;j++)
            graph[i][j] = -1;
    }

    //add edges and their weights
    for (int i=0;i<e;i++){
        int s,d,val;
        cin >> s >> d >> val;
        graph[s-1][d-1] = val;
    }

    //run algorithm
    pair<int,vector<int>> path = findShortestPath(graph, n-1);

    //print results
    cout << path.first << endl;
    for (int i=0;i<path.second.size()-1;i++)
        cout << path.second[i] << " -> ";
    cout << path.second[path.second.size()-1] << endl;

    return 0;
}

Answer 2

Esto debe resolverse mediante programación dinámica.
Sea P (j) la posición de la persona, si se necesita el ventilador óptimo, para pasar por el punto de unión j. Por ejemplo, P (6) = 4 en su caso, porque alguien que llegue al punto de unión 3 será el cuarto en pasar por el punto de unión 6 (después de P27, P26 y P28).
Las siguientes tres proposiciones son obvias y resuelven el problema.
Si un "punto de unión" j es un ventilador, P (j) = 1 (caso base)
Si un "punto de unión" j es un punto de unión adecuado con los niños l y r, y hay x personas en la cola entre l y j y y personas en la cola entre r y j, tenemos P (j) = 2 * min (P (l) + x, P (r) + y)
Si alguien si es el número uno en pasar por el mostrador, se necesita un tiempo n-1 para llegar allí.
Puede obtener el tiempo fácilmente usando DP y con un poco de contabilidad (si se alcanza el mínimo en la izquierda o en la derecha) puede obtener cuál es el ventilador óptimo.