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

Question

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

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

Редактировать:

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

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

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

Спасибо за ваши ответы и комментарии, теперь у меня в голове становится немного яснее.

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 понимаются как "веса") вовсе не является "непрофессиональной", по крайней мере, если вы понятия не имеете, какой могла бы быть более подходящая функция затрат.

Редактировать:

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

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

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

Answer 2

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

Answer 3

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

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

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