Caminho mais longo em um tipo particular de gráfico

9

Eu sei que o problema com o caminho mais longo é NP-difícil para um gráfico geral. No entanto, estou considerando um tipo específico de gráfico, consistindo em um ciclo, mais um incidente de borda adicional em cada vértice do ciclo. Por exemplo, para um ciclo de comprimento 7, temos o gráfico:

Todas as arestas são ponderadas (o peso é um número real e pode ser positivo ou negativo). Eu quero encontrar o maior caminho simples neste gráfico, onde o tamanho de um caminho é a soma dos pesos das bordas no caminho.

O algoritmo deve ser linear no tamanho do ciclo. Mas qualquer ideia é apreciada.

    
por becko 09.01.2013 в 03:21
fonte

3 respostas

5

Isso pode ser reduzido para problema de subarray máximo e resolvido em tempo linear.

  1. Desconecte o ciclo (em qualquer nó).
  2. Anexar segunda cópia do gráfico restante ao ponto em que o ciclo foi desconectado (podemos pular o último nó).
  3. Aplique o algoritmo de Kadane modificado à lista de nós resultante.
  4. Se o caminho encontrado não tiver arestas , procure a aresta de maior peso no gráfico. Se essa borda tiver peso não negativo, informe esse caminho de uma única borda. Caso contrário, denuncie esse caminho de borda única de qualquer maneira, se os caminhos vazios não forem permitidos ou informe o caminho vazio se eles forem permitidos.

->

Modificações necessárias do algoritmo de Kadane:

  1. Acompanhe o número de nós no caminho atual (subarray). Aparar os nós da cauda quando o subarray tiver N ou mais nós "ciclo". Para aparar esses nós de maneira eficiente, precisamos de uma fila que possa relatar o valor mínimo de seus elementos. Empurre os elementos para essa fila sempre que o cabeçalho do caminho for avançado (adicione o peso da borda da folha se não for negativo), elementos pop quando a cauda do caminho estiver aparada e redefina a fila onde o caminho atual for redefinido para o caminho vazio. Essa fila contém comprimentos de prefixo (não necessariamente simples), onde o valor mínimo fornece a posição adequada para avançar a cauda do caminho. Essa fila pode ser implementada como um deque contendo apenas valores não decrescentes ou como um par de pilhas, conforme mencionado em esta resposta.
  2. Redefinir o comprimento do caminho para max(0, leaf_edge_weight) sempre que o comprimento do caminho atual estiver abaixo de zero (em vez de redefini-lo para zero como no algoritmo original de Kadane).
  3. Adicione um peso de borda de folha não negativo (correspondente ao nó principal) quando o caminho atual (não vazio) for comparado ao caminho do melhor até agora.
por Evgeny Kluev 09.01.2013 / 12:25
fonte
0

O caminho mais longo é quase certamente entre dois dos vértices externos. Também é quase certamente necessário cobrir todos os vértices do ciclo.

Assim, você deseja usar o DFS para mapear o ciclo em O (N). Em seguida, calcule o comprimento do arranjo atual do ciclo. Adicione a esse comprimento a distância do primeiro ponto do ciclo até o exterior e o último ponto ao exterior. E isso lhe dá o comprimento real do caminho, que você armazena separadamente da duração do ciclo.

Aumente o índice do primeiro ponto e do último ponto (pode ser feito em O (1)), remova o comprimento da borda que agora vai direcionada do primeiro ao último ponto. Em seguida, adicione os comprimentos externos novamente. Repita até cobrir todos os vértices. Desde o seu armazenamento e atualização do comprimento do caminho, em vez de realmente recalculá-lo cada vez (o que exigiria (O (N ^ 2)), isso pode ser feito em O (N).

Isso permite atravessar o ciclo em O (N). No entanto, não é um algoritmo exato. Isso requer verificar se você não deveria ter usado o primeiro + i e / ou o último-j para algum i, j. Para verificar completamente isso requer essencialmente O (N ^ 2).

Embora, você possa estar prestes a fazê-lo em torno de O (N log N), determinando habilmente onde esses casos são possíveis. Eu duvido que um algoritmo linear exato seja possível.

    
por Nuclearman 09.01.2013 / 06:09
fonte
0

Escolha um link no ciclo. O caminho mais longo passa ou não por esse link, então, vamos descobrir a melhor resposta em ambos os casos e escolher qual deles é o melhor.

Se o caminho mais longo não passar pelo link do ciclo, exclua o link para produzir uma árvore. A partir das folhas, elabore, em cada nó, o caminho mais longo sob esse nó e o caminho mais longo desse nó para qualquer descendente. Em cada nó, você pode calcular as respostas observando as respostas de seus filhos. A resposta na raiz te dá o caminho mais longo.

Se o caminho mais longo passar pelo link escolhido, ele deve consistir em uma parte que vai no sentido horário a partir de uma extremidade do link e uma parte que vai no sentido anti-horário a partir da outra extremidade do link. Os comprimentos destes dois somam não mais do que um mais o número de links que compõem o ciclo. Para i = 1, limita-se a calcular o custo dos caminhos no sentido horário e anti-horário de cada lado do link e manter um máximo de execução. O caminho mais longo que passa pelo link tem comprimento a soma, para alguns k, do caminho mais longo indo no sentido horário para até k links e o caminho mais longo indo no sentido anti-horário para até links Nk (possivelmente com algum custo similar de - ve custos de link estão presentes). Então você pode encontrar o caminho mais longo que passa pelo link escolhido com custo também O (n).

Calculando dois casos cada um de custo O (n) e escolhendo o melhor, você tem o custo total O (n)

    
por mcdowella 09.01.2013 / 07:33
fonte