Найти минимальный путь в дереве с многозначными узлами

Question

Мои математические классы далеко позади, и я в настоящее время изо всех сил стараюсь найти достойное решение проблемы, с которой я сталкиваюсь: у меня есть дерево, в котором узлы являются действиями, и «взвешены» в соответствии с несколькими критериями: стоимость указанного действия, время, которое потребуется, необходимые ресурсы, нарушение и т. д.

И я хочу найти в этом дереве путь, который минимизирует оба стоимость И время например, или нарушение И стоимость И время и т. д. Моя проблема заключается в том, что я понятия не имею, как это сделать, за исключением того, что придумывает глобальную функцию стоимости F (стоимость, время, ресурсы. ..) и применить обычный алгоритм обхода дерева, используя результат из F (...) в качестве моего единственного веса. Но тогда, как мне придумать F? Что-то вроде "F (стоимость, время, ресурсы) = а * + стоимость б * время + C * ресурсы" чувствует себя очень "непрофессионально" ...

Edit:

Я хотел бы избежать слова «суммирующий «поскольку я не был уверен, что это действительно способ, но по существу это то, что я делаю: вычисление общей стоимости для каждого« пути »или« ветви », идущего от этого верхнего узла, до одного из листьев и выбора «пути» или «ветви», что минимизирует стоимость. Проблема состоит в том, что каждый узел имеет вес, основанный на времени, необходимом, на финансовых затратах, на использовании ресурсов и т. Д.

Таким образом, кажется неизбежным необходимость придумать формулу, как говорит Стефан, что уменьшит все эти параметры достигают одной глобальной стоимости на каждый узел, который я могу затем суммировать по узлам, когда я перемещаюсь по дереву, и выбираю путь, который минимизирует общую стоимость.

Так что, я думаю, мой вопрос на самом деле есть, есть ли там методология для выбора этой функции?

Благодарим за ответы и комментарии. Теперь это становится немного более ясным в моей голове.

Answer 1

Предположим, что у нас есть четыре пары (x, y), подобные (1, 4), (1, 5), (2, 3), (3, 3). Теперь вы хотите свести к минимуму «как x, так и y». Что вы имеете в виду? Если вы минимизируете первые x, а затем y, вы получаете (1, 4). Если вы минимизируете первый y, а затем x, вы найдете (2, 3).

Если вы не выбрали глобальную функцию стоимости F (x, y), как в вашем наблюдении, я не вижу никакого значения «обоих». (Во всяком случае, как только будет выбрано F, все равно может быть несколько точек минимума.) Кстати, по моему мнению, линейная комбинация (положительные множители a, b, c, понимаемые как «веса»), вообще не «непрофессиональны» , по крайней мере, если вы не знаете, что может быть более подходящей функцией стоимости.

Edit:

Так что, кажется, неизбежно придется придумать формулу, как говорит Стефан, что позволит сократить все эти параметры в одной глобальной стоимости, на узел, который я могу просуммировать по узлам когда я спускаюсь по дереву и выбираю путь, который минимизирует общую стоимость.

Осторожно. Действительно, эта стратегия имеет смысл только в том случае, если F линейна. Разумеется, затраты, время, ресурсы и т. Д. Являются аддитивными функциями в том смысле, что время (node1 -> node2 -> node3) = time (node1) + time (node2) + time (node3), но в целом это не так для F, если он не является линейным. (например, F (стоимость (node1 -> node2)) = F (стоимость (узел1) + стоимость (узел2))! = F (стоимость (узел1)) + F (стоимость (узел2)).)

Если вы выберите нелинейную глобальную функцию затрат, правильная стратегия - вычислить для каждого узла общую стоимость, общее время, общие ресурсы от корня до этого узла и вычислить (затем свести к минимуму) F только для конечных узлов.

Answer 2

Выполнение F - это самое важное. Если я могу дать вам 6 и 5 раз или 5 раз и 6 затрат, что вы предпочитаете? Ваша функция затрат должна учитывать это. К сожалению, нет алгоритма, который поможет решить эту проблему. Я отрицал это за неделю до того, как я сел и написал F для приложения оптимизации, над которым я работал. В худшем случае, оставьте параметры для пользователя, чтобы возиться с.

Answer 3

Почему бы обычный алгоритм поиска графа, как A*, не работал?

Для функции стоимости пути вы можете использовать текущую сумму соответствующих критериев. Дальше до цели сложнее ...

Это может быть расстоянием до ближайшего листа, предварительно вычисленным для всех или некоторых узлов, хотя это звучит ужасно дорого. В зависимости от структуры вашего дерева вы можете придумать более дешевую недооценку - если она идеально сбалансирована, например, это тривиально.