Пусть граф, и пусть и две вершины . Можем ли мы эффективно выбрать равномерно и независимо случайным образом кратчайший путь - из множества всех кратчайших путей между и ? Для простоты можно предположить, что простая, ненаправленная и невзвешенная.
Даже во многих ограниченных графах, число кратчайших путей между и может быть экспоненциальным в размере . Поэтому мы, естественно, хотели бы избежать вычисления всех кратчайших - путей. Я не знаю об общем случае, но мне кажется, что мы можем достичь этого для некоторых специальных классов графов.
Это похоже на то, что кто-то должен был рассмотреть раньше. Есть ли какие-либо исследования в этом направлении, или это на самом деле просто сделать даже для общих графиков?
Ответы:
Я не уверен на 100%, что этот ответ правильный, но здесь идет:
Я думаю, что вы можете уменьшить это до равномерно случайных произвольных путей, от , в группе DAG с одним источником и одним приемником.s−t
Дан графикG
По существу, я собирать все возможные узлы , которые могут быть использованы в кратчайшем пути, и размещение их в .H
Подробнее о том, как это работает:
Теперь у нас есть DAG, который мы можем пройти любым способом из и получить кратчайший обратный путь из s - t . График должен иметьt−s s−t как единственный источник и s как единственный сток.t s
Если вышеприведенное верно, то я думаю, что мы можем сделать еще один шаг и решить проблему следующим образом.
Дайте каждому узлу в DAG вес узла; Вес узла будет количеством путей от этого узла до . Давайте называть этоs .w(v)
Вы можете вычислить это быстро, см алгоритма , который находит ряд простых путей от й до т в G .
Когда у нас есть вес узла, мы можем выбрать путь следующим образом:
Макет DAG как структура уровня (для визуализации)На каждом уровне выберите произвольный порядок между узлами, т.е. понятие «слева направо».источник
Вот решение, основанное на идеях в ответе Realz Slaw. Это в основном переосмысление его идей, которое может быть более ясным или более легким для понимания. План состоит в том, что мы будем действовать в два этапа:
Сначала мы построим граф со следующим свойством: любой путь от s до t в S является кратчайшим путем от s до t в G , и каждый кратчайший путь из sS s t S s t G s до в G также присутствует в S . Таким образом, S содержит именно кратчайшие пути в G : все кратчайшие пути и ничего более. Как это бывает, S будет DAG.t G S S G S
Далее, мы будем пробовать равномерно случайным образом из всех путей от до т в S .s t S
Этот подход обобщает произвольный ориентированный граф , если все ребра имеют положительный вес, поэтому я объясню свой алгоритм в этих терминах. Пусть w ( u , v ) обозначает вес на ребре u → vG w(u,v) u→v . (Это обобщает постановку задачи, которую вы дали. Если у вас есть невзвешенный граф, просто предположите, что каждое ребро имеет вес 1. Если у вас есть неориентированный граф, обрабатывайте каждое неориентированное ребро как два направленных ребра u → v и v → у .)(u,v) u→v v→u
Шаг 1: экстракт .S Запустите алгоритм кратчайших путей из одного источника (например, алгоритм Дейкстры) на , начиная с источника s . Для каждой вершины v в G пусть d ( s , v ) обозначает расстояние от s до vG s v G d(s,v) s v .
Теперь определим граф следующим образом. Он состоит из каждого ребра u → v такого, что (1) u → v является ребром в G и (2) d (S u→v u→v G .d(s,v)=d(s,u)+w(u,v)
Граф имеет несколько удобных свойств:S
Каждый кратчайший путь из в t в G существует как путь в S : кратчайший путь s = v 0 , v 1 , v 2 , … , v k = t в G обладает свойством d ( s , v i + 1). ) = d ( s , v i ) + w ( v i , v is t G S s=v0,v1,v2,…,vk=t G . , поэтому ребро v i → v i + 1 присутствует в Sd(s,vi+1)=d(s,vi)+w(vi,vi+1) vi→vi+1 S
Каждый путь в из S к т является кратчайшим в G . В частности, рассмотрим любой путь в S от s до t , скажем, s = v 0 , v 1 , v 2 , … , v k = t . Его длина определяется суммой весов его ребер, а именно: ∑ k i = 1 w ( v i - 1 , v iS s t G S s t s=v0,v1,v2,…,vk=t ∑ki=1w(vi−1,vi) , но по определению эта сумма равна ∑ k i = 1 ( d ( sS , который телескопирует к d ( s , t ) - d ( s , s )∑ki=1(d(s,vi)−d(s,vi−1) поэтому этот путь является кратчайшим путем от s до t в.d(s,t)−d(s,s)=d(s,t) s t G
Наконец, отсутствие ребер с нулевым весом в означает, что S dag.G S
Шаг 2: выберите случайный путь.Теперь мы можем отбросить веса на ребрах в и выбрать случайный путь от s до t в SS s t S .
Чтобы помочь с этим, мы сделаем предварительное вычисление для вычисления для каждой вершины v в S , где nn(v) v S подсчитывает количество различных путей от v до t . Это предварительное вычисление может быть выполнено за линейное время путем сканирования вершин S в топологически отсортированном порядке, используя следующее рекуррентное соотношение:n(v) v t S
где обозначает преемников v , т. е. succ ( v ) = { w : v → wsucc(v) v , и где мы имеем базовый случай n ( t ) = 1succ(v)={w:v→w is an edge in S} n(t)=1 .
Далее мы используем аннотацию для выборки случайного пути. Мы первый визит узел sn(⋅) s . Затем мы случайным образом выбираем одного из преемников с преемником w, взвешенным по n ( w ) . Другими словами:s w n(w)
Чтобы выбрать случайный путь, мы многократно повторяем этот процесс: т.е. и v i + 1 =v0=s vi+1= (vi) s t .
choosesuccessor
. Результирующий путь является желаемым путем, и он будет случайным образом выбран из всех кратчайших путей от s до t.Надеюсь, это поможет вам легче понять решение Realz Slaw. Вся благодарность Realz Slaw за красивое и чистое решение этой проблемы!
Единственный случай, который не обрабатывается, это случай, когда некоторые ребра имеют вес 0 или отрицательный вес. Тем не менее, в этом случае проблема может быть недостаточно четко определена, поскольку вы можете иметь бесконечно много кратчайших путей.
источник