Qual é a maneira mais eficiente de encontrar um caminho através de um gráfico pequeno mundo?

Question

I têm um mar de nodos ponderados com arestas ligando clusters de nós juntos. Este gráfico segue o layout típico pequeno mundo.

Eu gostaria de encontrar um algoritmo de descoberta de caminho, que não é caro em energia do processador, para encontrar um caminho ao longo do melhor caminho possível onde os nós são os mais favoravelmente ponderada, a rota mais rápida não é o fator mais importante. Este algoritmo, também leva em consideração rolamento de carga, e reencaminhamento do tráfego.

(sidenote:? Poderia redes neurais ser usados ??aqui)

Graças

---

Eu estou olhando para ACO . Existe alguma coisa melhor do que ACO para este tipo de problema?

---

direito a A * algoritmo encontra o menor custo ou rota mais rápida, sem balanceamento de carga.

Vamos dizer que a rota mais rápida ou mais curta não é a rota mais importante, o que é mais importante é seguir um caminho onde os nós ponderada tem um determinado valor. no1.

no2. Se estiver usando um * o tráfego nessa rota fica sobrecarregado, de repente, esse caminho é redundante. Então, tão fria como A * é, ele não tem certas características que ACO ou seja inerente balanceamento de carga.

- a menos que im A equivocada e mal compreendido *

Então, o que bate ACO?

---

Ele realmente se parece um show para baixo entre ACO e A *, houve uma conversa muito positiva sobre A *, eu certamente vai olhar mais profundo sobre isso.

Em primeiro lugar, em resposta a David; Eu posso correr simulação ACO no terreno de volta e chegar com o melhor caminho, então sim, há um custo de arranque inicial, mas essencial a inicialização felizmente is not. Então eu posso dar ao luxo de executar uma simulação várias vezes. O único problema real é encontrar nós de origem e de destino conectados. Considerando que se afigura A * será capaz de fazer isso com bastante facilidade. Agora o que acontece quando esta rede ficar terrivelmente grande como em milhões de nós. Will A * ser capaz de escalar facilmente?

Vou pesquisar A * mais. Mas deixo-vos com uma última pergunta!

Will A * ser capaz de escala, bem como Antnet (ACO)?

Answer 1

Notas gerais

algoritmo de Dijkstra e optimizados variante A * encontrar o caminho com "o" custo mínimo através de seu gráfico. As coisas importantes são: a) definir o gráfico corretamente e b) definição de uma função de custo apropriado.

Em face de uma função de custo mudando Dijksta requer que se re-calcular a solução.

Por que eu iria estender Dikstra não só para calcular o melhor caminho, mas usar algum tipo de comportamento inundação-fill para criar um conjunto de possíveis caminhos (ordenadas pelo custo) para encontrar alternativas de balanceamento de carga. Só o conhecimento sobre o problema específico e função de custo pode responder se e como este trabalho poder.

Ant Colony Optimization por outro lado, parece ser muito mais flexível na adaptação a uma mudança função de custo, continuando a iteração após a /, enquanto a função de custo alterações.

Eficiência

Isso depende muito do seu domínio do problema. Se você tem uma boa heurística (veja a href="http://en.wikipedia.org/wiki/A-star_algorithm#Complexity" rel="noreferrer"> seção ) e raramente custo muda então A * 's de tempo de execução polinomial pode favorecer re-cálculos repetidos. ACO, por outro lado tem para percorrer uma e outra vez antes de convergir para uma solução aproximada. Se as mudanças de custos ocorrem com muita freqüência, continuando a iteração a uma taxa constante pode ser mais eficiente do que a atualização do A * -solution, já que a informação é retida no interior do estado do algoritmo. ACO não promete o solução ideal, embora e provavelmente tem mais elevados custos de arranque antes de convergir para uma solução "bom". Mais uma vez que muito depende do seu domínio específico, gráfico e função de custo, bem como suas necessidades de otimização.

Answer 2

Com A *, o custo do caminho não precisa ser constante, para que você possa começar com o seguinte gráfico:

A---1---B---1---C
|               |
\-------1-------/

onde queremos ir de A a C. Inicialmente, o algoritmo constatação caminho vai escolher o caminho A-C desde a A-B-C é de 2 Considerando A-C é 1. Nós podemos adicionar um prazo extra para os caminhos:

A---r---B---r---C
|               |
\-------r-------/

com

r(NM) = k(NM) + users(NM) / 10

onde

r(NM) is the cost for a connection between N and M,
k(NM) is the constant cost for a connection between N and M,
users(NM) is the number of objects using the connection

Como utilizadores são adicionados ao sistema, o AC percurso irá tornar-se mais caro do que ABC em vinte utilizadores (1 + 20/10) = 3, ABC é 2. Como utilizadores são removidos do sistema, o percurso CA ficará a melhor opção novamente.

O poder real do A * é a heurística que você usa para calcular o custo de cada ligação.

Answer 3

O algoritmo mais comumente utilizado para este problema é A * (A Star) , que é um generalizada algoritmo de Dijkstra pesquisar com heurísticas adicionados - o objetivo da heurística é dirigir a busca para a meta pesquisa de modo que pesquisas típicas terminar mais rápido.

Este algoritmo tem muitas variantes, versões derivadas e melhorias, pesquisa do Google ou a página da Wikipedia deve ser um ponto de partida bom.

Answer 4

Definitivamente A *. A * vão quer encontrar o melhor caminho possível ou nenhum caminho em tudo se existe nenhum caminho. Por exemplo. o caminho deste barco foi calculado usando A *

_{(fonte: cokeandcode.com )}

Aqui está um interativa Java Demonstração para brincar. Por favor note que este algoritmo é retardado por dorme, então você vê-lo realizando. Sem essa desaceleração ele iria encontrar o caminho em menos de um segundo.

O algoritmo é simples, mas poderosa. Cada nó tem 3 valores, g é o custo-se a esse nó. h é o custo estimado a partir deste nó para o alvo e f é a soma de ambos (que é um palpite para o caminho completo). A * mantém duas listas, o Aberto ea lista fechada. A lista Abrir contém todos os nós que não foram exploradas até agora. A lista fechada todos os nós que foram exploradas. A contagem dos nós como explorado se o algoritmo já testado cada nó ligado a este nó (ligado só poderia significar horizontalmente e verticalmente, mas também se diagonal diagonal move entre nodos são permitidos).

O algoritmo poderia ser descrito como

1. Seja P o ponto de partida
2. Designar g, h, e F valores para P
3. Adicionar P à lista aberta (neste ponto P é o único nó na lista).
4. Let B ser o melhor nó da lista Open (melhor == menor valor f)
   • Se B é o nó objetivo -> sair, você encontrou o caminho
   • Se a lista Abrir está vazia -> sair, nenhum caminho existe
5. Seja C um nó válido ligado a B
   • Designar g, h, e f a C
   • Verifique se C é na Abrir ou lista fechada
     • Se sim, verifique se o novo caminho é mais eficiente (menor f-value)
       • Se for assim, atualizar o caminho
     • Else add C à lista aberta
   • Repita a etapa 5 para todos os nós conectados a B
6. Adicionar B à lista fechada (nós exploramos todos os vizinhos)
7. Repita a partir do passo 4.

Também dê uma olhada em Wikipedia para detalhes de implementação.

Answer 5

Eu ouvi de uma implementação NN para lidar com esse tipo de problema também. Então, se você quiser usar NNs você acabará por encontrar o seu caminho ;-) mas eles deve ser inferior em comparação com "algoritmos genéticos".

Se o consumo / tempo computacional é um problema, eu sugiro usando algoritmos genéticos. Esta é excactly o tipo de problemas que são excepcionais no.

AGs são baseados em uma função que descreve a sua satisfação para qualquer solução dada. Você pode modificar essa função para atender às suas necessidades (ou seja. Você pode incluir não só custo do caminho, mas qualquer coisa que você quiser).

Answer 6

Será que um de Dijkstra comum não ser suficiente?

http://improve.dk/generic-dijkstras-algorithm/

Answer 7

Dijkstras algoritmo, pequeno exemplo para você

graph = {}

graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2
graph["a"] = {}
graph["a"]["finish"] = 1
graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["finish"] = 5
graph["finish"] = {}

infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["finish"] = infinity
print "The weight of each node is: ", costs

parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["finish"] = None

processed = []

def find_lowest_cost_node(costs):
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node

node = find_lowest_cost_node(costs)
print "Start: the lowest cost node is", node, "with weight",\
    graph["start"]["{}".format(node)]

while node is not None:
    cost = costs[node]
    print "Continue execution ..."
    print "The weight of node {} is".format(node), cost
    neighbors = graph[node]
    if neighbors != {}:
        print "The node {} has neighbors:".format(node), neighbors
    else:
        print "It is finish, we have the answer: {}".format(cost)
    for neighbor in neighbors.keys():
        new_cost = cost + neighbors[neighbor]
        if costs[neighbor] > new_cost:
            costs[neighbor] = new_cost
            parents[neighbor] = node
    processed.append(node)
    print "This nodes we researched:", processed
    node = find_lowest_cost_node(costs)
    if node is not None:
        print "Look at the neighbor:", node

# to draw graph
import networkx
G = networkx.Graph()
G.add_nodes_from(graph)
G.add_edge("start", "a", weight=6)
G.add_edge("b", "a", weight=3)
G.add_edge("start", "b", weight=2)
G.add_edge("a", "finish", weight=1)
G.add_edge("b", "finish", weight=5)

import matplotlib.pyplot as plt
networkx.draw(G, with_labels=True)
plt.show()

print "But the shortest path is:", networkx.shortest_path(G, "start", "finish")