Échantillonnage efficace et aléatoire des chemins

Laissez $G$ un graphe, et que $s$ et $t$ deux sommets de $G$ . Pouvons-nous échantillonner efficacement un chemin $s$ - plus court de $t$maniè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.$s$$t$$G$$s$$t$

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?

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.$s-t$

É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 .$s$$s$
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)$$s-v$
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 ).$\mathbf p$$t$$s$
5. Maintenant, lancez la boucle suivante; explication dans les commentaires, et ci-dessous:
   • $q_0=\{t\}$
   • Alors que $q_0 \ne \emptyset$
     • $q_1= \emptyset$
     • Pour $u \in q_0$
       • Nous voulons donc trouver tous les prochains nœuds possibles pour ce sous-chemin le plus court de $t-u$
       • Pour toute telle que d ( s , v ) < d ( s , u $\text{edge}(u,v) \in G$$d(s,v) < d(s,u)$
         • est un nœud voisin, avec moins de d ( s , ⋅ ) (ce sera 1 de moins)$v$$d(s,\cdot)$$1$
         • Par conséquent, est un sous-chemin possible dans un chemin le plus court.$t-u-v$
         • Mettez $v \rightarrow H, \text{di-edge}(u,v)\rightarrow H$
         • Maintenant, nous devons vérifier $v$ les petits voisins de prochain tour.
         • Mettez $v \rightarrow q_1$
     • Réglez à q 1 : $q_0$$q_1$
       • $q_0 \leftarrow q_1$

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.$v\in G$$s-v$$t-s$

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.$t-s$$s-t$$t$$s$

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 ) .$s$$w(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): $i$$i \in \left[1,\left|\mathbf p\right|\right]$$|\cdot|$
  • Soit le nœud courant (à partir de t )$u_i$$t$
  • 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.$u_i$$v_i$
  • Définissez et passez à l'étape suivante$u_{i+1} = v_i$

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.$S$$s$$t$$S$$s$$t$$G$$s$$t$$G$$S$$S$$G$$S$

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

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 $u \to v$. (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 $u\to v$ and $v\to u$.)

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 $u \to v$ such that (1) $u \to v$ 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=v_0,v_1,v_2,\dots,v_k=t$ in $G$ has the property that $d(s,v_{i+1})=d(s,v_i)+w(v_i,v_{i+1})$$v_i \to v_{i+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=v_0,v_1,v_2,\dots,v_k=t$. Its length is given by the sum of the weights of its edges, namely $\sum_{i=1}^k w(v_{i-1},v_i)$, but by the definition of $S$, this sum is $\sum_{i=1}^k (d(s,v_i)-d(s,v_{i-1})$, 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:

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

Next, we use the $n(\cdot)$ 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., $v_0=s$, and $v_{i+1} =$ choosesuccessor$(v_i)$. 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.