Estrutura de dados para caminhos mais curtos

Seja um gráfico não direcionado não ponderado com vértices e arestas. É possível pré-processar e produzir uma estrutura de dados do tamanho para que possa responder a consultas da forma "distância entre e " no tempo O (n)? $G$ $n$ $m$ $G$ $m \cdot \mathrm{polylog}(n)$ $u$ $v$

O problema parece básico demais para ser resolvido.

graph-theory graph-algorithms ds.data-structures ilyaraz
fonte

Em resposta à sua observação final sobre “básico demais para não ser resolvido”: se a consulta deve ser respondida em um tempo constante, ela é realmente bem estudada. Mas o objetivo da sua pergunta é que você permita O (n) tempo para uma consulta (em vez de O (1) ou O (m) trivial). Embora eu pense que é uma pergunta interessante, não acho que seja de fundamental importância.

Tsuyoshi Ito

@TsuyoshiIto - Não vejo por que a pergunta perde sua "importância fundamental" se permite um tempo de consulta super-constante, mas sub-linear. Por exemplo, suponha que eu possa resolver o problema acima com a restrição de que as consultas à distância possam ser respondidas no tempo por alguns , e o tempo de processamento seja no máximo - isso não me daria um algoritmo sub-cúbico para calcular caminhos mais curtos? Pessoalmente, acho que essa é uma pergunta muito interessante.

O (n^{1 - ε})

$O(n^{1-\varepsilon})$

ε > 0

$\varepsilon > 0$

O (n^{3 - ε})

$O(n^{3 - \varepsilon})$

Rachit

Eu não sei se existe uma maneira geral ou não, mas há uma boa maneira nos gráficos de largura da árvore delimitada, consulte Consulta de caminho mais curto nos gráficos de largura da árvore limitada

Saeed

Além disso, se

m = Ω (n^{2})

$m = \Omega(n^2)$ você pode criar uma árvore de caminho mais curto (iniciando em cada nó) e, em seguida, responder à consulta de caminho mais curto (por raiz relacionada) em

O (n)

$O(n)$ , ou de maneira semelhante, você pode construir um dado estrutura com menos tamanho de memória.

Saeed

Respostas:

Esta é uma questão muito interessante. Em um nível alto, você está perguntando se é possível pré-processar um gráfico de forma que as consultas de caminho mais curto se tornem independentes da densidade do gráfico, sem usar muito espaço extra - interessante, mas, como você diz, não resolvido.

Se você estiver satisfeito com as distâncias aproximadas, aqui está uma maneira de obter uma aproximação . Deixe ser um grafo não-dirigido ponderado com nodos e bordas. É mostrado no artigo a seguir que, para consultas de distância aproximada, projetar estruturas de dados para gráficos com arestas não é mais difícil do que gráficos nos quais cada nó tem grau limitado por : $2$ $G$ $n$ $m$ $m$ $m/n$

R. Agarwal, PB Godfrey, S. Har-Peled, consultas de distância aproximada e roteamento compacto em gráficos esparsos, INFOCOM 2011

Portanto, assuma que é um gráfico delimitado por . Amostra nós uniformes aleatoriamente; chame esses nós de referência. Durante a fase de pré-processamento, armazene a distância entre cada nó de referência e o outro nó no gráfico; isso requer espaço . Para cada nó , armazene seu nó de referência mais próximo . Além disso, armazene o gráfico na estrutura de dados, como uma lista de adjacência. $G$ $m/n$ $\alpha = O(m/n)$ $O(m)$ $u$ $\ell(u)$

Quando consultada a distância entre e , aumente as bolas ao redor dos dois nós - a bola do nó é definida como o conjunto de nós que são estritamente mais próximos de do que o nó de referência mais próximo, digamos . Pode-se mostrar que o tamanho de cada bola é , na expectativa. Seja , onde $u$ $v$ $w$ $w$ $\ell(w)$ $O(n^2/m)$ $\Gamma(u) = B(u) \cup N(B(u))$ é a bola do nó e é o conjunto de vizinhos dos nós em . Pode-se mostrar que o tamanho de é , na expectativa. $B(u)$ $u$ $N(B(u))$ $B(u)$ $\Gamma(u)$ $O(n)$

Respondendo à consulta: se , retorne ; caso contrário, se $\Gamma(u) \cap \Gamma(v) \neq \emptyset$ $\min_{x \in \Gamma(u) \cap \Gamma(v)} \{d(u, x) + d(v, x)\}$ , retornar ; caso contrário, retorne . É fácil mostrar que essa é umaaproximação . $d(u, \ell(u)) \leq d(v, \ell(v))$ $d(u, \ell(u)) + d(\ell(u), v)$ $d(v, \ell(v)) + d(\ell(v), u)$ $2$

Em termos de tempo de consulta, observe que o crescimento de bolas leva tempo para um gráfico delimitado em ; construir e dadas as respectivas esferas leva tempo (uma vez que os vizinhos são armazenados na estrutura de dados); e verificar se está vazio ou não também leva tempo . $O(n)$ $m/n$ $\Gamma(u)$ $\Gamma(v)$ $O(n)$ $\Gamma(u) \cap \Gamma(v)$ $O(n)$

Os limites acima estão na expectativa; Eu acho que é fácil derandomizar a construção. Infelizmente, essa técnica não parece permitir uma aproximação melhor que . É uma pergunta muito interessante embora .... $2$

Rachit
fonte

A técnica acima não explora o fato de seu gráfico de entrada não ter peso; pode haver algo interessante que você possa fazer explorando esse fato, mas não consigo pensar em uma maneira de recuperar distâncias exatas. Por exemplo, é possível reduzir o tempo de consulta para

e obter a distância delimitada por

, onde

é a distância exata entre

O (n^{2} / m)

$O(n^2/m)$

2 d + 1

$2d+1$

d

$d$

u

$u$

v

$v$

Rachit

Percebi que não entendo por que é uma aproximação de 2. Thorup-Zwick nas mesmas situações dá 3 aprox.

Ilyaraz

@ilyaraz: Observe que o esquema Thorup-Zwick não precisa verificar

(e, portanto, responde a consultas em tempo quase constante). Veja o artigo que mencionei acima para a prova do trecho

Γ (u) \cap Γ (v)

$\Gamma(u) \cap \Gamma(v)$

2

$2$

Rachit

O que você precisa é chamado de "oráculo à distância". Infelizmente, eu não estou muito familiarizado com oráculos a distância, então só posso encaminhá-lo ao artigo seminal devido a Thorup e Zwick:

Mikkel Thorup e Uri Zwick. Oráculos de distância aproximada. STOC '01, 2001.

Aqui está um trecho do resumo:

Seja um gráfico ponderado não direcionado com e . Seja um número inteiro. Mostramos que pode ser pré-processado em tempo esperado, construindo uma estrutura de dados de tamanho $G = (V, E)$ $|V| = n$ $|E| = m$ $k$ $G = (V, E)$ $O(kmn^{1/k})$ , de modo que qualquer consulta de distância subseqüente possa ser respondida aproximadamente em time. A distância aproximada retornada é de extensão no máximo , ou seja, o quociente obtido dividindo a distância estimada pela distância real fica entre 1 e . O requisito de espaço do nosso algoritmo é [...] essencialmente ideal. $O(kn^{1+1/k})$ $O(k)$ $2k - 1$ $2k - 1$

De acordo com os resultados, o que você solicita é basicamente factível, mesmo para gráficos ponderados: escolher gera um oráculo de distância do tamanho obtido no tempo esperado , que pode responder às consultas de caminho mais curto com -estique em tempo! $k=1$ $O(n^2)$ $O(mn)$ $1$ $O(1)$

Oráculos a distância é um campo muito bem pesquisado, então você poderá cavar mais, acredito.

Gabor Retvari
fonte

Versão da revista: JACM 2005 .

Tsuyoshi Ito

Usando o espaço

, é possível armazenar ingenuamente uma tabela de consulta. Portanto, este artigo (que eu conhecia) é irrelevante aqui.

O (n^{2})

$O(n^2)$

Ilyaraz 23/10

Justo. O resultado mais perto do que você solicitar AFAIK é para gráficos com grau médio

que dá caminhos esticar-2 com

espaço em

Θ (\log n)

$\Theta(\log n)$

O (n^{3 / 2})

$O(n^{3/2})$

tempo de consulta. (R. Agarwal, P. Godfrey e S. Har-Peled, "Consultas de distância aproximada e roteamento compacto em gráficos esparsos", INFOCOM 2011.)

O (\sqrt{n})

$O(\sqrt{n})$

Gabor Retvari

Usando a incorporação de métricas da Bourgain em

, pode-se criar um oráculo com o espaço

, tempo de consulta

e erro multiplicativo

ℓ_{1}

$\ell_1$

O (n \log^{2} n)

$O(n \log^2 n)$

O (\log^{2} n)

$O(\log^2 n)$

O (\log n)

$O(\log n)$

Ilyaraz # 24/11