다수 노드가있는 트리에서 최소 경로를 찾으십시오

Question

내 수학 수업은 훨씬 뒤쳐져 있으며 현재 문제에 대한 괜찮은 해결책을 찾기 위해 고군분투하고 있습니다. 트리가 있고 노드가 동작이며 여러 기준에 따라 "가중"입니다. 행동, 시간, 필요한 자원, 교란 등 ...

그리고 나는이 나무에서 비용과 시간, 예를 들어, 장애와 비용과 시간 등을 최소화하는 길을 찾고 싶습니다. 내 문제는 제외하고는 어떻게 해야할지 전혀 모른다는 것입니다. 글로벌 비용 함수 F (비용, 시간, 자원, ...)를 사용하여 F (...)의 결과를 유일한 무게로 사용하여 일반 트리 트래버스 알고리즘을 적용하십시오. 그런 다음 어떻게 F를 생각해 내나요? "f (비용, 시간, 자원) = a * cost + b * time + c * resources와 같은 것과 같은"비전문가 "느낌 ... ...

편집하다:

나는 그것이 실제로가는 길인지 확신하지 못했기 때문에 "합산"이라는 단어를 피하고 싶었지만 본질적으로 그것이 내가하고있는 일입니다. 각 "경로"또는 "분기"에 대한 총 비용을 계산합니다. 그 상단 노드, Leafs 중 하나에, 비용을 최소화하는 "경로"또는 "분기"를 선택합니다. 문제는 각 노드가 필요한 시간, 재무 비용, 자원 사용 등에 대한 가중치를 가지고 있다는 것입니다.

Stephan이 말했듯이,이 모든 매개 변수를 노드 당 하나의 글로벌 비용으로 줄일 수있는 공식을 생각해내는 것은 불가피한 것 같습니다. 그런 다음 나무 아래로 이동할 때 노드를 가로 질러 합산하고 경로를 선택할 수 있습니다. 총 비용을 최소화합니다.

그래서 내 질문은 실제로 그 기능을 선택하는 방법론이 있습니까?

귀하의 답변과 의견에 감사드립니다. 이제 내 머리가 조금 더 분명해지기 시작했습니다.

Answer 1

Let's say we have four pairs (x, y) like (1, 4), (1, 5), (2, 3), (3, 3). Now you want to minimize "both x and y". What do you mean? If you minimize first x and then y you end up with (1, 4). If you minimize first y and then x you find (2, 3).

Unless you choose a global cost function F(x, y), like in your observation, I can't see any meaning of "both". (Anyway, once F is chosen, there may still be multiple minimum points.) By the way, in my opinion a linear combination (the positive multipliers a,b,c being understood as "weights") is not "unprofessional" at all, at least if you have no idea of what a more suitable cost function could be.

Edit:

So it seems inevitable to have to come up with a formula, as Stephan says, that will reduce all these parameters to one global cost, per node, which I can then sum across nodes as I travel down the tree, and pick the path that minimizes the total cost.

Caution. Indeed this strategy makes sense only if F is linear. Surely cost, time, resources etc. are additive functions, in the sense that time(node1 -> node2 -> node3) = time(node1) + time(node2) + time(node3), but in general this is not the case for F, unless it is linear. (i.e. F(cost(node1 -> node2)) = F(cost(node1) + cost(node2)) != F(cost(node1)) + F(cost(node2)). )

If you choose a nonlinear global cost function, the right strategy is to compute, for each node, the total cost, total time, total resources from the root to that node, and compute (then minimize) F only for the terminal nodes.

Answer 2

Coming up with F is the most important thing. If I can give you 6 cost and 5 time or 5 time and 6 cost, which do you prefer? Your cost function needs to take that into consideration. There's no algorithm that's going to solve that problem for you, unfortunately. I denied that for a week before I sat down and wrote F for an optimization application I was working on. Worst case, leave parameters for the user to tinker with.

Answer 3

Why wouldn't a normal graph search algorithm like A* work?

For the path-cost function, you could use the running sum of the relevant criteria. The distance to the goal is more difficult...

It could be the distance to the nearest leaf, pre-computed for all or some nodes, although that sounds awfully expensive. Depending on the structure of your tree, you could come up with a cheaper under-estimate - if it's perfectly balanced, for example, it's trivial.