Algoritmo de correspondência

Question

Estranho questão aqui não é realmente código, mas a lógica,a esperança que o seu ok para postar aqui,aqui é

Eu tenho uma estrutura de dados que pode ser pensado como um gráfico.Cada nó pode suportar muitos links, mas é limitada a um valor para cada nó.Todos os links são bidirecionais.e cada ligação tem um custo.o custo depende euclidiana diferença entre o nós e o valor mínimo de dois parâmetros em cada nó.e um modificador.

eu gostaria de encontrar o custo máximo para o gráfico.

querendo saber se havia uma maneira inteligente de encontrar uma correspondência, em vez de percorrer na força bruta ...o que é feio...e eu não tenho certeza de como eu ia mesmo fazer isso sem gastar 7 milhões de anos de executá-lo.

Para esclarecer:

Global variable = T
many nodes N each have E,X,Y,L
L is the max number of links each node can have.
cost of link A,B = Sqrt(  min([a].e | [b].e)  ) x 
     ( 1 + Sqrt( sqrt(sqr([a].x-[b].x)+sqr([a].y-[b].y)))/75 + Sqrt(t)/10 )


total cost =sum all links.....and we wish to maximize this.

os valores médios para nós é de 40-50 pode variar para (20..600) média nó de ligação do fator é de 3 faixa de 0-10.

Answer 1

Se eu entender o problema corretamente, provavelmente não há solução polinomial. Portanto, eu implementaria o seguinte algoritmo:

1. Encontre alguma solução por Beng ambicioso. Para fazer isso, você classifica todas as arestas por custo e depois passa por eles começando com o mais alto, adicionando uma borda ao seu gráfico, o mesmo tempo possível, e pulando quando o nó não pode aceitar mais bordas.
2. Olhe para suas bordas e tente alterá -las para arquivar um custo mais alto usando um heurísticas. O primeiro que me vem à mente: você percorre todos os 4-tuplos de nós (A, B, C, D) e se seu gráfico atual tiver arestas AB, CD, mas AC, BD seria melhor, você fará a alteração.
3. Opcionalmente a mesma coisa com 6-tuplos, ou outro algorítmos genéticos (Eles são chamados dessa maneira porque funcionam por mutações).

Answer 2

Por uma questão de completude para qualquer outra pessoa que analise este artigo, sugiro revisitar os algoritmos da teoria dos gráficos:

• Dijkstra
• Uma estrela
• Ambicioso
• Profundidade / largura primeiro
• Até programação dinâmica (em algumas situações)
• etc. etc.

Lá em algum lugar está a solução correta para o seu problema. Eu sugeriria olhar para Dijkstra primeiro.

Espero que isso ajude alguém.

Answer 3

Isso é equivalente ao problema do vendedor ambulante (e, portanto, é NP-completo), pois se você pudesse resolver esse problema com eficiência, poderá resolver o TSP simplesmente substituindo cada custo por seu recíproco.

Isso significa que você não pode resolver exatamente. Por outro lado, significa que você pode fazer exatamente como eu disse (substitua cada custo por seu recíproco) e, em seguida, use qualquer um dos métodos de aproximação de TSP conhecidos sobre esse problema.

Answer 4

Parece um Problema de fluxo máximo para mim.

Answer 5

É possível que, ao selecionar avidamente a próxima opção mais cara de um determinado ponto de partida (omitindo saltos para os nós visitados) e parando assim que todos os nós forem visitados? Se você chegar a um backtrack sem saída para o local anterior, onde não está em um beco sem saída e seleção avidamente. Isso exigiria algum trabalho e provavelmente algo como uma pilha para manter seus caminhos. Acho que isso funcionaria com bastante eficácia, desde que os custos sejam bem ordenados e não negativos.

Answer 6

Uso De Algoritmos Genéticos.Eles são projetados para resolver o problema do estado rapidamente, reduzindo o tempo de complexidade.Verifique por AI biblioteca no idioma da sua escolha.