Эффективная выборка самых коротких

14

Пусть G граф, и пусть s и t две вершины G . Можем ли мы эффективно выбрать равномерно и независимо случайным образом кратчайший путь s - t из множества всех кратчайших путей между s и t ? Для простоты можно предположить, что G простая, ненаправленная и невзвешенная.

Даже во многих ограниченных графах, число кратчайших путей между s и t может быть экспоненциальным в размере G . Поэтому мы, естественно, хотели бы избежать вычисления всех кратчайших s - t путей. Я не знаю об общем случае, но мне кажется, что мы можем достичь этого для некоторых специальных классов графов.

Это похоже на то, что кто-то должен был рассмотреть раньше. Есть ли какие-либо исследования в этом направлении, или это на самом деле просто сделать даже для общих графиков?

Юхо
источник
Хороший вопрос, Юхо. Принимая во внимание ответ, что вы точно понимаете под "выборкой одинакового случайного пути"? Если для случайного выбора s и t достаточно, вопрос тривиален, поэтому я предполагаю, что вы имеете в виду, что все узлы в кратчайшем пути появляются с частотой (т.е. вероятностью), которая следует за равномерным распределением. Или есть другое определение? В частности, для двудольных графов ваш вопрос кажется очень простым, не так ли?
Карлос Линарес Лопес
1
@ CarlosLinaresLópez Рассмотрим, скажем, алмазный график , и скажем, что находится справа от «вертикального края», а t слева. Теперь есть 2 кратчайших пути между s и t . Алгоритм должен возвращать с равной вероятностью один из этих двух путей. Таким образом, s и t не «выбираются случайным образом», но они даются в качестве входных данных. Это ясно? В этом смысле я не уверен, является ли проблема действительно простой для двудольных графов. ststst
Juho
1
@ CarlosLinaresLópez Другими словами, нам дан граф и две вершины s , t V ( G ) . Пусть S будет множеством всех кратчайших путей между s и t . Выведите элемент S равномерно наугад. Gs,tV(G)SstS
Juho

Ответы:

6

Я не уверен на 100%, что этот ответ правильный, но здесь идет:

Я думаю, что вы можете уменьшить это до равномерно случайных произвольных путей, от , в группе DAG с одним источником и одним приемником.st

Дан график G

  1. Создайте новый пустой орграф, .H
  2. Сначала: запустите часть BFS кратчайшего пути Дейкстры, начиная с , отметьте все узлы их кратчайшим расстоянием от s .ss
  3. Пусть минимальное расстояние от s - v ; что мы знаем из шага BFS алгоритма кратчайшего пути Дейкстры.d(s,v)sv
  4. Затем выполните следующий шаг алгоритма Дейкстры по кратчайшему пути, получите кратчайший путь, сохраните его в (перейдя назад от t к s ).pts
  5. Теперь запустите следующий цикл; Расширение в комментариях и ниже:
    • q0={t}
    • В то время как q0
      • q1=
      • Для uq0
        • Поэтому мы хотим найти все возможные следующие узлы для этого кратчайшего подпути из tu
        • Для всех таких, что d (edge(u,v)Gd(s,v)<d(s,u)
          • v соседний узел с меньшим (будет на 1 меньше)d(s,)1
          • Следовательно, - возможный подпуть в кратчайшем пути.tuv
          • Положить vH,di-edge(u,v)H
          • Теперь нам нужно проверить младших соседей следующем ходу.v
          • Положить vq1
      • Устанавливать в q 1 : q0q1
        • q0q1

По существу, я собирать все возможные узлы , которые могут быть использованы в кратчайшем пути, и размещение их в .H

Подробнее о том, как это работает:

Алгоритм кратчайшего пути Дейкстры работает, сначала запустив BFS и пометив все узлы их кратчайшими путями из svG . Следующий шаг - вернуться из t - s и проследовать за наименее соседними узлами.svts

Дело в том, что здесь вы можете выбрать любой из наименее соседних узлов. Здесь я собираю все наименее соседние узлы на каждом шаге, что означает, что я учитываю все кратчайшие пути.

Теперь вы быстро думаете, но, эй, почему перечисление их экспоненциально, а у меня нет?

Ответ таков: поскольку я использую набор, чтобы избежать добавления одних и тех же узлов дважды, я избегаю пересчета этого для каждого возможного пути.

Теперь у нас есть DAG, который мы можем пройти любым способом из и получить кратчайший обратный путь из s - t . График должен иметьtsst как единственный источник и s как единственный сток.ts


Если вышеприведенное верно, то я думаю, что мы можем сделать еще один шаг и решить проблему следующим образом.

Дайте каждому узлу в DAG вес узла; Вес узла будет количеством путей от этого узла до . Давайте называть этоs .w(v)

Вы можете вычислить это быстро, см алгоритма , который находит ряд простых путей от й до т в G .

Когда у нас есть вес узла, мы можем выбрать путь следующим образом:

  • Макет DAG как структура уровня (для визуализации)
  • На каждом уровне выберите произвольный порядок между узлами, т.е. понятие «слева направо».
  • Обход DAG: на каждом шаге , i [ 1 , | р | ] (где |ii[1,|p|] означает размер, в данном случае длину кратчайшего пути): ||
    • Пусть будет текущим узлом (начиная сui )t
    • Сложите все веса дочерних элементов и, используя RNG, выберите один дочерний узел, vui равномерно между взвешенными.vi
    • Установите и перейдите к следующему шагуui+1=vi
Реал Слав
источник
Структура уровня и понятие слева направо были частью моей первоначальной попытки просто сгенерировать и выбрать путь таким образом, но я не понял этого, поэтому Вы можете спокойно их игнорировать. r[0,w(t))
Реал Слав
1
Этот ответ выглядит великолепно! Я люблю идеи! Я попытался записать это немного по-другому (в своем ответе), в качестве проверки моего понимания. В любом случае, я просто хотел поделиться своей признательностью за этот прекрасный ответ!
DW
5

Вот решение, основанное на идеях в ответе Realz Slaw. Это в основном переосмысление его идей, которое может быть более ясным или более легким для понимания. План состоит в том, что мы будем действовать в два этапа:

  1. Сначала мы построим граф со следующим свойством: любой путь от s до t в S является кратчайшим путем от s до t в G , и каждый кратчайший путь из sSstSstGs до в G также присутствует в S . Таким образом, S содержит именно кратчайшие пути в G : все кратчайшие пути и ничего более. Как это бывает, S будет DAG.tGSSGS

  2. Далее, мы будем пробовать равномерно случайным образом из всех путей от до т в S .stS

Этот подход обобщает произвольный ориентированный граф , если все ребра имеют положительный вес, поэтому я объясню свой алгоритм в этих терминах. Пусть w ( u , v ) обозначает вес на ребре u vGw(u,v)uv . (Это обобщает постановку задачи, которую вы дали. Если у вас есть невзвешенный граф, просто предположите, что каждое ребро имеет вес 1. Если у вас есть неориентированный граф, обрабатывайте каждое неориентированное ребро как два направленных ребра u v и v у .)(u,v)uvvu


Шаг 1: экстракт . S Запустите алгоритм кратчайших путей из одного источника (например, алгоритм Дейкстры) на , начиная с источника s . Для каждой вершины v в G пусть d ( s , v ) обозначает расстояние от s до vGsvGd(s,v)sv .

Теперь определим граф следующим образом. Он состоит из каждого ребра u v такого, что (1) u v является ребром в G и (2) d (SuvuvG .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 istGSs=v0,v1,v2,,vk=tG. , поэтому ребро v iv i + 1 присутствует в Sd(s,vi+1)=d(s,vi)+w(vi,vi+1)vivi+1S

  • Каждый путь в из S к т является кратчайшим в G . В частности, рассмотрим любой путь в S от s до t , скажем, s = v 0 , v 1 , v 2 , , v k = t . Его длина определяется суммой весов его ребер, а именно: k i = 1 w ( v i - 1 , v iSstGSsts=v0,v1,v2,,vk=ti=1kw(vi1,vi) , но по определению эта сумма равна k i = 1 ( d ( sS , который телескопирует к d ( s , t ) - d ( s , s )i=1k(d(s,vi)d(s,vi1) поэтому этот путь является кратчайшим путем от s до t в.d(s,t)d(s,s)=d(s,t)stG

  • Наконец, отсутствие ребер с нулевым весом в означает, что S dag.GS

Шаг 2: выберите случайный путь.Теперь мы можем отбросить веса на ребрах в и выбрать случайный путь от s до t в SSstS .

Чтобы помочь с этим, мы сделаем предварительное вычисление для вычисления для каждой вершины v в S , где nn(v)vS подсчитывает количество различных путей от v до t . Это предварительное вычисление может быть выполнено за линейное время путем сканирования вершин S в топологически отсортированном порядке, используя следующее рекуррентное соотношение:n(v)vtS

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

где обозначает преемников v , т. е. succ ( v ) = { w : v wsucc(v)v , и где мы имеем базовый случай n ( t ) = 1succ(v)={w:vw is an edge in S}n(t)=1 .

Далее мы используем аннотацию для выборки случайного пути. Мы первый визит узел sn()s . Затем мы случайным образом выбираем одного из преемников с преемником w, взвешенным по n ( w ) . Другими словами:swn(w)

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

Чтобы выбрать случайный путь, мы многократно повторяем этот процесс: т.е. и v i + 1 =v0=svi+1= choosesuccessor . Результирующий путь является желаемым путем, и он будет случайным образом выбран из всех кратчайших путей от s до t.(vi)st .

Надеюсь, это поможет вам легче понять решение Realz Slaw. Вся благодарность Realz Slaw за красивое и чистое решение этой проблемы!


Единственный случай, который не обрабатывается, это случай, когда некоторые ребра имеют вес 0 или отрицательный вес. Тем не менее, в этом случае проблема может быть недостаточно четко определена, поскольку вы можете иметь бесконечно много кратчайших путей.

DW
источник
Рад, что вы нашли время, чтобы полностью получить мой ответ; Я не был уверен, что это правильно. Теперь я оправдан: D.
Реал Слав