Algoritmo para encontrar dois pontos mais distantes umas das outras

StackOverflow https://stackoverflow.com/questions/477591

Pergunta

Eu estou procurando um algoritmo para ser usado em uma Im tomada de jogo de corrida. O mapa / nível / faixa é gerada aleatoriamente assim que eu preciso para encontrar dois locais, início e objetivo, que faz uso da maior parte do mapa.

  • O algoritmo é o trabalho dentro de um espaço bidimensional
  • De cada ponto, só se pode atravessar para o próximo ponto em quatro direções; cima, baixo, esquerda, direita
  • Pontos só podem ser bloqueados ou não bloqueado, apenas os pontos não bloqueada pode ser percorrido

Em relação ao cálculo da distância, não deve ser o "caminho pássaro" por falta de uma palavra melhor. O caminho entre A e B deve ser mais longo, se há uma parede (ou outra área de bloqueio) entre eles.

Im não tem certeza sobre onde começar, os comentários são muito bem-vindo e soluções propostas são preferidas em pseudo-código.

Editar: Direito. Depois de olhar através de código I deu-lhe outro tiro. Em vez de python, eu desta vez escrevi em C ++. Mas ainda assim, mesmo depois de ler sobre Dijkstras algoritmo , a floodfill e solução Hosam Alys , não consigo detectar qualquer diferença crucial. Meu código ainda funciona, mas não tão rápido quanto você parece estar recebendo seu para ser executado. fonte completo está no pastie . As linhas só é interessante (eu acho) é a própria variante Dijkstra em linhas 78-118.

Mas a velocidade não é o principal problema aqui. Eu realmente gostaria de receber a ajuda se alguém seria gentil o suficiente para apontar as diferenças nos algoritmos.

  • algoritmo Em Hosam Alys, é a única diferença que ele faz a varredura das fronteiras, em vez de cada nó?
  • Em Dijkstras-lo a acompanhar e substituir a distância percorrida, mas não em floodfill, mas é sobre ele?
Foi útil?

Solução

Assumindo que o mapa é retangular, você pode loop sobre todos os pontos de fronteira e iniciar um preenchimento para encontrar o ponto mais distante do ponto de partida: 

bestSolution = { start: (0,0), end: (0,0), distance: 0 };
for each point p on the border
    flood-fill all points in the map to find the most distant point
    if newDistance > bestSolution.distance
        bestSolution = { p, distantP, newDistance }
    end if
end loop

Eu acho que isso seria em O(n^2). Se não me engano, é (L+W) * 2 * (L*W) * 4, onde L é o comprimento e W é a largura do mapa, (L+W) * 2 representa o número de pontos de fronteira ao longo do perímetro, (L*W) é o número de pontos, e 4 é a suposição de que a inundação-fill poderia acessar um ponto um máximo de 4 vezes (de todas as direções). Desde n é equivalente ao número de pontos, isso é equivalente a (L + W) * 8 * n, que deve ser melhor do que O(n 2 ). (Se o mapa é quadrado, a ordem seria O(16n 1,5 ).)

Update: de acordo com os comentários, uma vez que o mapa é mais de um labirinto (do que um com obstáculos simples como eu pensava inicialmente), você poderia fazer a mesma lógica acima, mas verificando todos os pontos no mapa (em oposição aos pontos de apenas a borda). Esta deve ser a fim de O(4n 2 ), que ainda é melhor do que ambos F-W e de Dijkstra.

Nota: Flood enchendo é mais adequado para este problema , uma vez que todos os vértices estão diretamente ligados através de apenas 4 fronteiras. Uma primeira passagem de amplitude do mapa pode produzir resultados relativamente rapidamente (em apenas O(n)). Estou assumindo que cada ponto pode ser verificado no preenchimento inundação de cada um dos seus 4 vizinhos, assim, o coeficiente nas fórmulas acima.

Update 2: Sou grato por todo o feedback positivo que recebi em relação a este algoritmo. Um agradecimento especial a @Georg para sua revisão .

P.S. Quaisquer comentários ou correções são bem-vindos.

Outras dicas

Seguimento da pergunta sobre Floyd-Warshall ou o simples algoritmo de Hosam Aly :

Eu criei um programa de teste que pode usar ambos os métodos. Esses são os arquivos:

Em todos os casos de teste Floyd-Warshall foi de grande magnitude mais lenta, provavelmente isso é por causa da quantidade muito limitada de arestas que ajuda este algoritmo para alcançar este objectivo.

Estas foram as vezes, cada vez que o campo foi quádruplo e 3 de 10 campos eram um obstáculo. 

Size         Hosam Aly      Floyd-Warshall
(10x10)      0m0.002s       0m0.007s     
(20x20)      0m0.009s       0m0.307s
(40x40)      0m0.166s       0m22.052s
(80x80)      0m2.753s       -
(160x160)    0m48.028s      -

O tempo de Hosam Aly parece ser quadrática, portanto, eu recomendo usar esse algoritmo. Além disso, o consumo de memória por Floyd-Warshall é n 2 , claramente mais do que o necessário. Se você tem alguma idéia de por Floyd-Warshall é tão lento, por favor deixe um comentário ou editar este post.

PS: eu não tenho escrito C ou C ++ em um longo tempo, eu espero não ter feito muitos erros

.

Eu apaguei o meu post original recomendando o algoritmo de Floyd-Warshall. : (

gs fez um benchmark realista e adivinhem, FW é substancialmente mais lento do que o algoritmo "flood fill" de Hosam Aly para tamanhos típicos mapa! Assim, mesmo que F-W é um algoritmo fresco e muito mais rápido do Dijkstra para grafos densos, eu não posso recomendar-lo mais para o problema do OP, que envolve gráficos muito esparsos (cada vértice tem apenas 4 bordas).

Para o registro:

  • Uma execução eficiente de algoritmo de Dijkstra leva O (Elog V) tempo para uma e gráfico com arestas e vértices V.
  • "preenchimento inundação" de Hosam Aly é um amplitude primeira pesquisa , que é O (V). Isso pode ser pensado como um caso especial do algoritmo de Dijkstra em que nenhum vértice pode ter a sua distância estimativa revista.
  • O Floyd-Warshall algoritmo leva O (V ^ 3 ) tempo, é muito fácil de código, e ainda é o mais rápido para gráficos densas (aqueles gráficos onde os vértices são normalmente ligados a muitos outros vértices). Mas é não a escolha certa para a tarefa do OP, que envolve gráficos muito esparsas.

Parece que o que você quer é os pontos finais separadas pela gráfico diâmetro . Um bastante bom e fácil de aproximação de computação é escolher um ponto aleatório, encontrar o ponto mais distante do que, em seguida, encontrar o ponto mais distante de lá. Estes dois últimos pontos deve ser perto de maximamente separados.

Para um labirinto rectangular, isto significa que dois abastecimentos de inundação deve obter um bom par bonito de pontos inicial e final.

Raimund Seidel dá um método simples usando multiplicação de matrizes para calcular a matriz de todos os pares de distância em um gráfico não ponderado, sem direção (que é exatamente o que você quer) na primeira seção do seu papel On The All-Pairs-Shortest-Path Problem em não ponderada sem direção Gráficos [Pdf] .

A entrada é a matriz de adjacência e a saída é a matriz de distância do caminho mais curto todos os pares. O tempo de execução é O (M (n) * log (n)) para n pontos onde M (n) é o tempo de execução do seu algoritmo de multiplicação de matrizes.

O documento também dá ao método para calcular os caminhos reais (no mesmo run-time) se você precisa disso também.

O algoritmo de Seidel é legal porque o tempo de execução é independente do número de arestas, mas nós realmente não se importam aqui porque nosso gráfico é escassa. No entanto, isso ainda pode ser uma boa escolha (apesar do pouco-pior que n ^ 2 run-time) a matriz se você quiser todos os pares de distância, e isso também pode ser mais fácil de implementar e depurar do que floodfill em um labirinto.

Aqui está o pseudocódigo: 

Let A be the nxn (0-1) adjacency matrix of an unweighted, undirected graph, G

All-Pairs-Distances(A)
    Z = A * A
    Let B be the nxn matrix s.t. b_ij = 1 iff i != j and (a_ij = 1 or z_ij > 0)
    if b_ij = 1 for all i != j return 2B - A //base case
    T = All-Pairs-Distances(B)
    X = T * A
    Let D be the nxn matrix s.t. d_ij = 2t_ij if x_ij >= t_ij * degree(j), otherwise d_ij = 2t_ij - 1
    return D

Para obter o par de pontos com a maior distância que acabamos de voltar argmax_ij (d_ij)

Terminado mockup um python da solução de Dijkstra para o problema. Código obtido um pouco longo para que eu postei isso em outro lugar: http://refactormycode.com/codes/717-dijkstra-to-find-two-points-furthest-away-from-each-other

No conjunto de tamanho que, leva cerca de 1,5 segundos para executar o algoritmo para um nó. Executá-lo para cada nó leva alguns minutos.

Não parece trabalho, porém, ele sempre exibe a topleft e bottomright canto como o caminho mais longo; 58 telhas. Que, naturalmente, é verdade, quando você não tem obstáculos. Mas, mesmo adicionando um par de queridos colocadas aleatoriamente, o programa ainda acha que um a mais longa. Talvez seja ainda verdade, difícil de teste sem formas mais avançadas.

Mas talvez ele possa, pelo menos, mostrar a minha ambição.

Ok "o algoritmo de Hosam" é uma busca em largura com uma pré-selecção nos nós. o algoritmo de Dijkstra não deve ser aplicado aqui, porque suas bordas não têm pesos.

A diferença é crucial, porque se os pesos das bordas variam, você precisa manter um monte de opções (rotas alternativas) aberta e verificá-los a cada passo. Isso faz com que o algoritmo mais complexo. Com a busca em largura, você simplesmente explorar todas as bordas uma vez de uma forma que garantuees que você encontrar o caminho mais curto para cada nó. ou seja, explorando as bordas na ordem que você encontrá-los.

Então, basicamente, a diferença é Dijkstra tem que 'voltar atrás' e olhar para as bordas tem exploradas antes de se certificar de que está a seguir o caminho mais curto, enquanto a amplitude primeira pesquisa sempre sabe que está seguindo o caminho mais curto.

Além disso, em um labirinto os pontos na borda externa não são garantidos para ser parte da rota mais longa. Por exemplo, se você tem um labirinto na forma de uma espiral gigante, mas com a extremidade externa voltando para o meio, você poderia ter dois pontos, um no centro da espiral e outra no final da espiral, tanto no meio!

Assim, uma boa maneira de fazer isso é usar uma busca em largura de todos os pontos, mas remover o ponto de partida depois de uma pesquisa (você já sabe todas as rotas de e para ele). Complexidade de amplitude primeiro é O (n), onde n = | V | + | E |. Fazemos isso uma vez para cada nó em V, por isso se torna O (n ^ 2).

A sua descrição soa para mim como um href="http://foghorn.cadlab.lafayette.edu/cadapplets/MazeRouter.html" rel="nofollow noreferrer"> labirinto roteamento problema Lee Algoritmo . Livros sobre problemas local e rota no projeto VLSI pode ajudá-lo - de Sherwani "Algoritmos para VLSI física design Automation " é bom, e você pode encontrar VLSI Física design Automation por Sait e Youssef útil (e mais barato em sua versão Google ...)

Se seus objetos (pontos) não se movem com freqüência você pode realizar esse cálculo em um muito menor do que O (n ^ 3) tempo.

Tudo que você precisa é quebrar o espaço em grandes redes e pré-calcular a distância inter-grade. Em seguida, selecionando pares de pontos que ocupam a maioria das grades distantes é uma questão de simples consulta à tabela. No caso médio terá de verificação por pares apenas um pequeno conjunto de objetos.

Esta solução funciona se as métricas de distância são contínuas. Assim, se, por exemplo, existem muitas barreiras no mapa (como em labirintos), este método pode falhar.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top