Encontrar o caminho mínimo em uma árvore com nós multivalor

Question

As minhas aulas de matemática estão muito atrás, e atualmente estou lutando para encontrar uma solução decente para um problema que estou tendo: Eu tenho uma árvore, em que os nós são ações, e são "ponderada" de acordo com vários critérios: o custo da referida ação, o tempo que levará, os recursos necessários, a perturbação, etc ...

E eu quero encontrar nesta árvore do caminho que minimiza o custo eo tempo por exemplo, ou a perturbação e de custo e tempo, etc. Meu problema é que eu não tenho nenhuma idéia de como fazê-lo, a não ser por surgir com uma função global custo F (custo, tempo, recursos, ...), e aplicar uma árvore regular de travessia algoritmo utilizando o resultado de F (...) como meu único peso. Mas então, como faço para chegar a F? Algo como "F (custo, tempo, recursos) = a * custo + b * tempo + c * recursos" sente muito "pouco profissional" ...

Editar:

Eu queria evitar a palavra "soma" como eu não tinha certeza que era realmente o caminho a percorrer, mas, na essência, é o que eu estou fazendo: Computação um custo total para cada "caminho" ou "ramo" que vai desde o nó de topo, a uma das folhas, e escolher o "caminho" ou "ramo" que minimiza o custo. O problema é que cada nó tem um peso com base no tempo necessário, no custo financeiro, no uso de recursos, etc.

Assim, parece inevitável ter que vir para cima com uma fórmula, como diz Stephan, que irá reduzir todos esses parâmetros para um custo global, por nó, que pode então resumir em nós de como eu viajo para baixo da árvore, e escolher o caminho que minimiza o custo total.

Então eu acho que a minha pergunta realmente existe, é uma metodologia para escolher essa função?

Obrigado por suas respostas e comentários, que está começando a ser um pouco mais clara na minha cabeça agora.

Answer 1

Vamos dizer que temos quatro pares (x, y) como (1, 4), (1, 5), (2, 3), (3, 3). Agora você quer minimizar "ambos x e y". O que você quer dizer? Se minimizar primeiros x e y, em seguida, que acabam por com (1, 4). Se você minimizar primeira y e, em seguida, x encontrar (2, 3).

A menos que você escolher uma função global custo F (x, y), como em sua observação, eu não posso ver qualquer significado de "ambos". (De qualquer forma, uma vez que F é escolhido, ainda pode haver múltiplos pontos mínimos.) By the way, na minha opinião uma combinação linear (os multiplicadores positivos a, b, c ser entendida como "pesos") não é "pouco profissional" em tudo , pelo menos se você não tem idéia do que uma função de custo mais adequado poderia ser.

Editar:

Assim, parece inevitável ter que vir para cima com uma fórmula, como diz Stephan, que irá reduzir todos esses parâmetros para um custo global, por nó, que pode então resumir em nós de como eu viajo para baixo da árvore, e escolher o caminho que minimiza o custo total.

Cuidado. Na verdade, esta estratégia só faz sentido se F é linear. Certamente custo, tempo, recursos etc. são funções aditivas, no sentido de que o tempo (node1 -> node2 -> node3) = tempo (node1) + tempo (node2) + tempo (node3), mas, em geral, este não é o caso para M, a menos que seja linear. (Ou seja, F (custo (node1 -.> Node2)) = F (custo (node1) + custo (nó 2)) = F (custo (node1)) + F (custo (nó 2)))

Se você escolher uma função de custo global de não-linear, a estratégia certa é calcular, para cada nó, o custo total, tempo total, os recursos totais a partir da raiz para esse nó, e compute (então minimizar) F apenas para o terminal nós.

Answer 2

Chegando-se com F é a coisa mais importante. Se eu posso dar-lhe 6 de custos e 5 de tempo ou 5 tempo e 6 custo, o que você prefere? Sua função de custo precisa levar isso em consideração. Não há nenhum algoritmo que vai resolver esse problema para você, infelizmente. I negou que durante uma semana antes de eu sentei e escrevi F para uma aplicação de otimização que eu estava trabalhando. Pior caso, os parâmetros de licença para o usuário a mexer.

Answer 3

Por que não um algoritmo de busca normais gráfico como A * trabalho ?

Para a função de caminho-de custo, você pode usar a soma parcial dos critérios relevantes. A distância até a meta é mais difícil ...

pode ser a distância para a folha mais próxima, pré-calculado para todos ou alguns nós, embora isso soa terrivelmente caro. Dependendo da estrutura da sua árvore, você poderia vir acima com um mais barato subestimar -. Se ele está perfeitamente equilibrado, por exemplo, é trivial