Échantillonnage efficace et aléatoire des chemins

14

Laissez G un graphe, et que s et t deux sommets de G . Pouvons-nous échantillonner efficacement un chemin s - plus court de tmanière uniforme et indépendante au hasard dans l'ensemble de tous les chemins les plus courts entre s et t ? Pour simplifier, nous pouvons supposer que G est simple, non orienté et non pondéré.

Même dans de nombreux graphiques restreints, le nombre de chemins les plus courts entre et t peut être exponentielle de la taille de G . Par conséquent, nous aimerions naturellement éviter de calculer réellement tous les chemins s - t les plus courts. Je ne connais pas le cas général, mais il me semble que nous pouvons y parvenir pour certaines classes de graphes spéciales.stGst

Cela ressemble à quelque chose que quelqu'un a dû considérer auparavant. Existe-t-il des recherches à ce sujet, ou est-ce en fait simple à faire, même pour les graphiques généraux?

Juho
la source
Bonne question Juho. En réfléchissant à une réponse, qu'entendez-vous précisément par «échantillonner un premier chemin uniformément au hasard»? S'il suffit que s et t soient choisis au hasard, la question est triviale, donc je suppose que vous voulez dire que tous les nœuds du chemin le plus court apparaissent avec une fréquence (c'est-à-dire une probabilité) qui suit une distribution uniforme. Ou existe-t-il une autre définition? En particulier, pour les graphiques bipartites, votre question semble très simple, n'est-ce pas?
Carlos Linares López
1
@ CarlosLinaresLópez Considérez par exemple le graphe en losange , et dites que est sur le côté droit du "bord vertical", et t est sur le côté gauche. Il y a maintenant 2 chemins les plus courts entre s et t . L'algorithme doit retourner avec une probabilité égale l'un ou l'autre de ces deux chemins. Donc, s et t ne sont pas "ramassés au hasard", mais ils sont donnés en entrée. Est-ce que cela est clair? En ce sens, je ne sais pas si le problème est vraiment facile pour les graphiques bipartites. ststst
Juho
1
@ CarlosLinaresLópez En d'autres termes, on nous donne un graphe , et deux sommets s , t V ( G ) . Soit S l'ensemble de tous les chemins les plus courts entre s et t . Génère un élément de S uniformément au hasard. Gs,tV(G)SstS
Juho

Réponses:

6

Je ne suis pas sûr à 100% que cette réponse est correcte, mais voici:

Je pense que vous pouvez réduire cela à n'importe quel chemin uniformément aléatoire, de , dans un DAG avec une seule source et un seul puits.st

Étant donné un graphique G

  1. Faites un nouveau digraphe vide, .H
  2. Premièrement: exécutez la partie BFS du chemin le plus court de Dijkstra, à partir de , marquez tous les nœuds avec leur distance la plus courte à partir de s .ss
  3. Soit la distance minimale de s - v ; que nous connaissons de l'étape BFS de l'algorithme de chemin le plus court de Dijkstra.d(s,v)sv
  4. Ensuite, effectuez l'étape suivante de l'algorithme de chemin le plus court de Dijkstra, obtenez le chemin le plus court, stockez-le dans (en reculant de t à s ).pts
  5. Maintenant, lancez la boucle suivante; explication dans les commentaires, et ci-dessous:
    • q0={t}
    • Alors que q0
      • q1=
      • Pour uq0
        • Nous voulons donc trouver tous les prochains nœuds possibles pour ce sous-chemin le plus court de tu
        • Pour toute telle que d ( s , v ) < d ( s , u )edge(u,v)Gd(s,v)<d(s,u)
          • est un nœud voisin, avec moins de d ( s , ) (ce sera 1 de moins)vd(s,)1
          • Par conséquent, est un sous-chemin possible dans un chemin le plus court.tuv
          • Mettez vH,di-edge(u,v)H
          • Maintenant, nous devons vérifier v les petits voisins de prochain tour.
          • Mettez vq1
      • Réglez à q 1 : q0q1
        • q0q1

Essentiellement, je collectionne tous les nœuds possibles qui peuvent être utilisés dans le plus court chemin, et en les plaçant dans .H

En savoir plus sur le fonctionnement:

L'algorithme de chemin le plus court de Dijkstra fonctionne en exécutant d'abord un BFS et en marquant tous les nœuds avec leurs chemins les plus courts de s - v . L'étape suivante consiste à revenir de t - s et à suivre les nœuds les moins voisins en arrière.vGsvts

Le fait est que vous pouvez choisir ici l' un des nœuds les moins voisins. Ce que je fais ici est de collecter tous les nœuds les moins voisins à chaque étape, ce qui signifie que je prends en compte tous les chemins les plus courts.

Maintenant vous pensez rapidement, mais bon, pourquoi les énumérer est -il exponentiel, mais ma façon de faire ne l'est pas?

La réponse est, parce que j'utilise un ensemble pour éviter d'ajouter deux fois les mêmes nœuds, j'évite de recalculer cela pour chaque chemin possible.

Nous avons maintenant un DAG que nous pouvons parcourir de n'importe quelle manière à partir de , et obtenir un chemin inversé le plus court à partir de s - t . Le graphique doit avoir t comme seule source et s comme seul puits.tsstts


Si ce qui précède est correct, je pense que nous pouvons aller plus loin et résoudre le problème comme suit.

Donnez à chaque nœud du DAG un poids de nœud; le poids du nœud sera le nombre de chemins allant de ce nœud à . Appelons cela w ( v ) .sw(v)

Vous pouvez calculer ces rapidement, voir l' algorithme qui trouve le nombre de chemins simples de s à t dans G .

Une fois que nous avons le poids du nœud, nous pouvons choisir uniformément un chemin en:

  • Disposition du DAG en tant que structure de niveau (pour la visualisation)
  • À chaque niveau, choisissez un ordre arbitraire entre les nœuds, c'est-à-dire. une notion de "gauche à droite".
  • Traversée du DAG: à chaque étape , i [ 1 , | p | ] (où || signifie la taille de, dans ce cas, la longueur du chemin le plus court): ii[1,|p|]||
    • Soit le nœud courant (à partir de t )uit
    • Additionnez tous les poids des enfants de , et en utilisant un RNG, choisissez un nœud enfant, v i , uniformément entre les enfants pondérés.uivi
    • Définissez et passez à l'étape suivanteui+1=vi
Realz Slaw
la source
La structure de niveau et la notion de gauche à droite faisaient partie de ma tentative initiale de générer simplement , et de choisir un chemin de cette façon, mais je ne l'ai pas compris, donc vous pouvez les ignorer en toute sécurité. r[0,w(t))
Realz Slaw
1
Cette réponse est superbe! J'adore les idées! J'ai essayé de l'écrire d'une manière légèrement différente (dans ma réponse), comme un test de ma compréhension. En tout cas, je voulais juste partager mon appréciation pour cette jolie réponse!
DW
5

Voici une solution basée sur les idées de la réponse de Realz Slaw. Il s'agit essentiellement d'une ré-exposition de ses idées qui pourrait être plus claire ou plus facile à suivre. Le plan est que nous allons procéder en deux étapes:

  1. Tout d' abord, nous allons construire un graphique avec la propriété suivante: tout chemin de s à t dans S est un plus court chemin de s à t dans G , et chaque chemin le plus court de s à t dans G est également présent dans S . Ainsi, S contient exactement les chemins les plus courts dans G : tous les chemins les plus courts, et rien de plus. En l'occurrence, S sera un DAG.SstSstGstGSSGS

  2. Ensuite, nous allons prélever uniformément au hasard dans tous les chemins de à t dans S .stS

This approaches generalizes to an arbitrary directed graph G, as long as all edges have positive weight, so I'll explain my algorithm in those terms. Let w(u,v) denote the weight on the edge uv. (This generalizes the problem statement you gave. If you have an unweighted graph, just assume every edge has weight 1. If you have an undirected graph, treat each undirected edge (u,v) as the two directed edges uv and vu.)


Step 1: extract S. Run a single-source shortest-paths algorithm (e.g., Dijkstra's algorithm) on G, starting from source s. For each vertex v in G, let d(s,v) denote the distance from s to v.

Now define the graph S as follows. It consists of every edge uv such that (1) uv is an edge in G, and (2) d(s,v)=d(s,u)+w(u,v).

The graph S has some convenient properties:

  • Every shortest path from s to t in G exists as a path in S: a shortest path s=v0,v1,v2,,vk=t in G has the property that d(s,vi+1)=d(s,vi)+w(vi,vi+1)vivi+1 is present in S.

  • Every path in S from s to t is a shortest path in G. In particular, consider any path in S from s to t, say s=v0,v1,v2,,vk=t. Its length is given by the sum of the weights of its edges, namely i=1kw(vi1,vi), but by the definition of S, this sum is i=1k(d(s,vi)d(s,vi1), which telescopes to d(s,t)d(s,s)=d(s,t). Therefore, this path is a shortest path from s to t in G.

  • Finally, the absence of zero-weight edges in G implies that S is a dag.

Step 2: sample a random path. Now we can throw away the weights on the edges in S, and sample a random path from s to t in S.

To help with this, we will do a precomputation to compute n(v) for each vertex v in S, where n(v) counts the number of distinct paths from v to t. This precomputation can be done in linear time by scanning the vertices of S in topologically sorted order, using the following recurrence relation:

n(v)=wsucc(v)n(w)

where succ(v) denotes the successors of v, i.e., succ(v)={w:vw is an edge in S}, and where we have the base case n(t)=1.

Next, we use the n() annotation to sample a random path. We first visit node s. Then, we randomly choose one of the successors of s, with successor w weighted by n(w). In other words:

choosesuccessor(v):
    n = 0
    for each w in succ(w):
        n = n + n(w)
    r = a random integer between 0 and n-1
    n = 0
    for each w in succ(w):
        n = n + n(w)
        if r < n:
            return w

To choose a random path, we repeatedly iterate this process: i.e., v0=s, and vi+1= choosesuccessor(vi). The resulting path is the desired path, and it will be sampled uniformly at random from all shortest paths from s to t.

Hopefully this helps you understand Realz Slaw's solution more easily. All credit to Realz Slaw for the beautiful and clean solution to this problem!


The one case this doesn't handle is the case where some edges have weight 0 or negative weight. However, the problem is potentially not well-defined in that case, as you can have infinitely many shortest paths.

D.W.
la source
Glad you took the time to fully get my answer; I wasn't sure it is correct. Now I am vindicated :D.
Realz Slaw