* Против деревьев в самой длинной дорожке
Пусть T будет деревом, в котором каждый узел представляет состояние. Корень представляет начальное состояние. Ребро, идущее от родителя к потомку, определяет действие, которое можно выполнить над родителем для изменения состояния (новое состояние будет дочерним). Каждое ребро связано с усилением, т.е. я получаю что-то, переходя из родительского состояния в дочернее состояние.
Кроме того, предположим, что каждый путь от корневого до конечного узла имеет длину Q.
Моя цель состоит в том, чтобы найти наиболее многообещающий путь длины Q, то есть путь, который гарантирует наибольшее усиление (где усиление пути определяется как сумма усилений, присоединенных к краям в пути).
Очевидно, что я хотел бы сделать это, не исследуя все дерево, так как T может быть очень большим.
Таким образом, я подумал о применении A*. Я знаю, что A * можно использовать для поиска кратчайшего пути в графе, но:
- У меня нет затрат, у меня есть прибыль
- Я хочу найти самый длинный путь (на самом деле не самый длинный путь от начального узла, но тот, вес которого, если его суммировать, дает самое высокое значение)
- У меня есть дерево, а не график (без циклов!)
В конце концов, у меня возник ряд вопросов, которые я хотел бы задать вам:
- Подходит ли A * для этого типа проблемы? Я найду оптимальное решение, применяя это?
- Поскольку A * требует использования (заниженной) оценки стоимости от текущего узла к цели в случае кратчайшего пути, я должен искать (сверх) оценку усиления от текущего узла к цели и использовать это как эвристика?
- Учитывая узел n в T, моя идея состояла в том, чтобы вычислить эвристику h(n) как сумму выигрышей, достигнутых дочерними элементами n, что может быть не так уж сложно. Как вы думаете, может быть лучшее решение?
РЕДАКТИРОВАНИЕ: учитывая узел n в дереве, усиление, приложенное к ребру, исходящему из n, не может быть больше, чем величина U(n). Кроме того, U(n) становится все меньше и меньше с увеличением глубины n.
2 ответа
Анализ
Причина в следующем. Предположим, вы утверждаете, что путь P является оптимальным, и не рассмотрены края e, Я могу без потери общности установить усиление для e до значения, превышающего сумму всех других выгод в дереве. Тогда ваш путь P не оптимально.
Таким образом, любое утверждение оптимальности, сделанное до проверки усиления всех ребер, является ложным.
Заключение
Если никакой дополнительной информации об усилениях на ребрах не предоставлено, вы не сможете найти оптимальный путь, не исследуя все дерево.
Если бы у вас была, например, верхняя граница значений усиления, вы могли бы использовать A*, чтобы более эффективно находить оптимальный путь, а не проверять каждое ребро.
Ответы на изменения, которые вы внесли в вопрос после написания этого ответа, приведены в комментариях ниже. Обязательно ознакомьтесь с ними.
Чтобы ответить на вопрос, A* обычно не является правильным подходом к исследованию деревьев. Это для взвешенных графиков, а не деревьев. Если вы исследуете дерево, вы используете возврат. Вы можете сделать возврат более интеллектуальным, используя эвристику или обрезку.