Comment faire pour trouver le plus court chemin dans un Arbre dans un temps linéaire?

Ici est un problème à partir d'Algorithmes livre par Vazirani

L'entrée de ce problème est un arbre T entier avec des poids sur les arêtes. Le poids peut être négatif,
zéro ou positif. Donner un temps linéaire de l'algorithme pour trouver le plus court chemin simple en T. La longueur d'un
le chemin est la somme des poids des arêtes dans le chemin. Un chemin est simple, si pas de sommet est répété. Note
que les points de terminaison de la voie sont sans contrainte.

INDICE: C'est très similaire au problème de trouver le plus grand ensemble indépendant dans un arbre.

Comment puis-je résoudre ce problème en temps linéaire?

Voici mon algorithme, mais je suis me demande si c'est linéaire dans le temps, car il n'est rien d'autre que de la profondeur d'abord:

  1. Traverse l'arbre (profondeur d'abord)
  2. Garder l'index (nœuds)
  3. ajouter les valeurs
  4. faire (1) jusqu'à la fin de l'arbre
  5. comparer la somme et imprimer le chemin d'accès et le montant

ce problème est similaire à ce sujet mais il n'y a pas de réponse certaine.

  • Vazirani rapprochement livre? Je ne peut pas comprendre le problème, chaque arête de l'arbre est le chemin, et le plus petit bord est le chemin le plus court, voulez-vous me préciser par la présente, ou de dire le nom exact de problème aussi google? avez-vous trouver le plus court chemin de l'arbre? ou de la racine de l'arbre?
  • la plus petite arête n'est pas nécessairement le chemin le plus court, parce que vous pouvez avoir le poids est négatif.
  • oui j'avais oublié 🙂
  • ce vide est le chemin - c'est le plus court, n'est-ce pas? Vous n'avez pas mis une seule exigence de ce que tha chemin d'accès doit contenir. Il ne fait pas de sens.
  • Vide chemin a poids égal à zéro. Un chemin constitué d'un seul poids négatif de bord est plus courte.
  • L'INDICE dit que ce problème est lié à la découverte de la plus grande indépendant situé dans un arbre. Toute réflexion sur ce que cela signifie?

InformationsquelleAutor | 2011-02-12
  1. 6

    Ce problème est à peu près équivalent à la montant minimum sous-suite problème, et peut être résolu d'une manière similaire par la programmation dynamique.

    Nous allons calculer les tableaux suivants en utilisant DF recherches:

    dw1[i] = minimum sum achievable by only using node i and its descendants.
pw1[i] = predecessor of node i in the path found for dw1[i].
dw2[i] = second minimum sum achevable by only using node i and its descendants,
         a path that is edge-disjoint relative to the path found for dw1[i].

    Si vous pouvez calculer ces, prendre min(dw1[k], dw1[k] + dw2[k]) sur tous les k. C'est parce que votre chemin sera de prendre l'une de ces formes de base:

      k              k
  |     or     /  \
  |           /    \
  |

    Qui sont toutes couvertes par les sommes d'argent que nous prenons.

    Calcul dw1

    Exécution d'un DFS du nœud racine. Dans le DFS, de garder trace de l'actuel nœud et son père. À chaque nœud, assumer ses enfants sont d1, d2, ... dk. Puis dw1[i] = min(min{dw1[d1] + cost[i, d1], dw1[d2] + cost[i, d2], ..., dw1[dk] + cost[i, dk]}, min{cost[i, dk]}). Ensemble dw1[i] = 0 pour les nœuds feuilles. N'oubliez pas de mettre à jour pw1[i] avec le prédécesseur.

    Calcul dw2

    Exécution d'un DFS du nœud racine. Faire la même chose que vous avez fait pour dw1, sauf lorsqu'on passe d'un nœud i pour l'un de ses enfants k, mettre à jour uniquement dw2[i] si pw1[i] != k. Vous appelez la fonction récursive pour tous les enfants toutefois. Il ressemblerait à quelque chose comme ça en pseudo-code:

    df(node, father)
    dw2[node] = inf
    for all children k of node
        df(k, node)

        if pw1[node] != k
            dw2[node] = min(dw2[node], dw1[k] + cost[node, k], cost[node, k])
    • L'air prometteur, mais j'ai quelques suggestions: (1) dans la rubrique "Calcul de dw1" quand vous dites que "les descendants", je crois que tu veux dire "les enfants" ("descendants" signifie généralement que tous les enfants et petits-enfants, de manière récursive); (2) Le calcul de chacune des dw1[i], dw2[i] et up[i] devrait inclure des 0 dans la min{...} pour permettre le chemin pour y mettre fin (de sorte que, par exemple, un arbre contenant pas de longueur négative bords de retour d'un score de 0); (3) Je crois que votre calcul de dw2[i] devrait exclure l'optimal bord...
    • ... à partir du sommet i seulement, mais à des niveaux inférieurs doivent inclure optimale des bords (vous demander si vous avez besoin de précisions); (4) up[i] calculs peuvent être simplifiés en notant que chaque parcours est de 1 de 2 types: soit il est "directement vers le bas" ou qu'il contient un "coin supérieur" (un sommet v tel que le parent de v n'est pas dans le path) -- un chemin contenant un coin supérieur à un certain sommet v sera trouvée en considérant dw1[v] + dw2[v], donc up[i] seulement besoin de calculer les coûts droite un chemin de retour vers la racine (c'est à dire up[i] sera le coût minimum d'un "droit-vers le bas" chemin se terminant à i).
    • d'accord, sera mise à jour. (2) tu veux dire qu'un nul chemin? Je le considère comme un chemin d'accès contient au moins une arête, c'est pourquoi je n'ai pas ajouter de 0. Il est assez facile de le modifier si l'OP veut accepter null chemins. (3) n'est-ce pas ce qui se passe? Nous avons affaire à un arbre, donc si vous excluez le optimal bord de i, vous automatiquement exclure le reste ainsi. (4) je ne suis pas sûr de ce que vous voulez dire ici. Dans ma solution, up ne stocke pas seulement des voies droites de i à la racine. Si vous le faites, comment obtiendrez-vous votre réponse? Becase le minimum ne doit pas nécessairement être un chemin droit.
    • Plus sur (3) - si vous voulez dire que la case ne devrait pas être fait sur les niveaux inférieurs, je pense que c'est faux, car alors vous aurez chevauchement min-coût et la deuxième min-coût chemins pour certains descendants. Ils doivent être arête-disjoints pour chaque nœud, sinon vous aurez de mauvaises réponses lors dw1[k] + dw2[k], parce que les deux chemins ont en commun les bords.
    • En effet, y compris un 0 en vertu de la min() permettra null chemins, mais en le laissant complètement forcera tous les chemins pour mettre fin à une feuille -- certainement pas ce qui est voulu. Si vous voulez autoriser les chemins qui se terminent avant les feuilles, mais interdire null chemins, c'est certainement possible, mais nécessite de garder plus des scores pour chaque nœud, je pense. (3) Pas vrai -- rappelez-vous que c'est un arbre, donc si vous avez 2 à la baisse des chemins de départ à v dont la première bords sont différents, ils auront forcément pas de sommets communs (sauf pour v). ...
    • ... Afin d'avoir dw2[i] éviter optimal à bas-bord au niveau i est suffisante pour garantir que les chemins représenté par dw1[i] et dw2[i] sont sommet-disjoints en dehors de i; éviter optimale de bas bords pour dw2[i] à chaque niveau tout à fait dw2[i] pire que ce qu'elle doit être.
    • (4) je me suis dit, on peut (et devrait, à mon avis) laissez up magasin seulement straight-up chemins de i, parce que le cas où vous êtes inquiet au sujet (quand vous dites que le minimum ne doit pas nécessairement être un chemin droit) seront traitées comme suit: Supposons que le chemin d'accès minimal par le sommet u passe par le bord de u est parent, mais n'est pas "straight up". Dans ce cas, il y a quelques vertex v ci-dessus (plus proche de la racine de) u "qui est le coin supérieur" de ce chemin, et quand nous les parcourir tous les sommets à la recherche pour le meilleur chemin à travers chaque, nous allons trouver ce chemin lorsque nous regardons vertex v. Clair?
    • En fait, maintenant que j'y pense, up n'est pas du tout nécessaire, si la valeur est null chemins sont autorisés, depuis tout "straight-down" chemin d'accès est équivalent à un chemin d'accès avec un "coin supérieur", dans lequel l'un des 2 "rayons" de ce coin vertex est un null chemin. 🙂
    • le vrai sujet (2). Je pense que nous pouvons éviter null chemins aussi d'envisager de prendre le seul min-coût de bord de seul. Fondamentalement exécuter un montant minimum sous-suite sur les bords. De cette façon, les chemins ne sont pas nécessairement de début et de fin à une feuille. Comme pour (3), pouvez-vous poster quelques pseudo-code? La fonction s'appelle elle-même de manière récursive pour chaque enfant, et les chemins se terminant à l'enfant doit également être arête-disjoints. dw2[i] ne sera pas pire que ce qu'elle devrait l'être, parce que vous allez être en utilisant le dw1 de i s 'enfants de la calculer.
    • "parce que vous allez être en utilisant le dw1 de i 's d'enfants pour le calculer" -- OK on dirait que vous vous êtes déjà à faire ce que je dis alors. La description de votre poste pourrait être lu comme disant que dw2 est calculée de manière récursive à l'aide de dw2, qui donne à l'suboptimality j'étais inquiet au sujet. Peut-être que vous pourriez mentionner que le calcul dw2[i] revient à l'utilisation de dw1[i] sur les enfants dans le post?
    • fait. Mise à jour (5) trop. Merci pour votre aide!
    • À la recherche de bonnes, +1 à la dernière 😛 Mais ne voyez-vous que up peuvent être éliminés par la modification de la réponse globale pour un nœud k à min(dw1[k], dw2[k], dw1[k] + dw2[k])? Cela modifie l'interprétation globale de la requête sur un nœud q de "Quel est le plus court chemin d'accès contenant q?" à "qu'est-Ce que le chemin le plus court dont la plus élevée est q?" - mais c'est OK, parce que chaque chemin d'accès a un plus haut de nœud. 🙂
    • Je viens de réaliser que si vous avez écrit votre commentaire et de s'en débarrasser :). Est de mettre dw2[k] dans le minimum nécessaire? Il ne sera jamais plus petit que dw1[k]. Il y a quelques temps, j'ai résolu un problème qui a demandé à des requêtes telles que what's the shortest path containing q?, j'ai donc été mis sur l'utilisation de up. Rends compte qu'il n'est pas nécessaire ici.
    • Bon point, dw2[k] n'est pas nécessaire, au minimum, car il ne peut pas être inférieure à dw1[k]. De plus en plus simple!
    • Toute réflexion sur ce qu'est la relation entre ce problème et de trouver le plus grand ensemble indépendant dans un arbre, comme annoncé dans l'indice?
    • Je n'ai pas vraiment voir beaucoup de connexion, j'ai peur... je ne sais que indépendant situé dans un arbre peut être résolu dans un large façon similaire, en calculant les 2 valeurs pour chaque nœud avec un DFS: la taille du plus grand ensemble indépendant dans le sous-arbre enraciné au noeud i qui utilise nœud i, ainsi que la taille du plus grand ensemble indépendant dans le sous-arbre enraciné au nœud i qui ne l'est pas. Appeler ces x(i) et y(i) respectivement. Ensuite, vous pouvez calculer la valeur de x(i) en prenant 1 + somme(y(j)) pour chaque enfant de j de i, et vous pouvez calculer y(i) en prenant la somme(x(j)) pour chaque enfant de j.i.
    • Merci. Peut-être que c'est la connexion. Nice algorithme, par la manière.
    • Vous êtes les bienvenus! Je suppose qu'ils sont similaires.
    • Viens de remarquer un bug! y(i) somme(max(x(j), y(j))) pour chaque enfant de j de i, car nous ne voulons permettre, pas besoin, que les enfants sont inclus dans l'ensemble indépendant.

    InformationsquelleAutor IVlad