Фундаментальные различия между проблемами "Самый широкий путь" и "Самый длинный путь"

Question

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

Благодарю.

Answer 1

Основное различие между этими двумя проблемами состоит в том, что самая широкая проблема пути имеет оптимальную подструктуру, а самая длинная проблема пути (насколько известно) не имеет.

В частности, рассмотрим самый широкий путь от узла u к узлу v. Если этот путь проходит через промежуточный узел s, то самый широкий путь от u до v должен состоять из самого широкого пути от u до s, за которым следует самый широкий путь из s к v. Если этого не произошло, то вы можете заменить любую часть пути от u до s или от s до v еще более широким путем, не ухудшая решение.

Однако, это не работает для самой длинной проблемы пути. Если вы берете самый длинный путь (неявно самый длинный простой путь) от u до v и он проходит через некоторые узлы s, у вас не обязательно будет самый длинный путь от u до s, за которым следует самый длинный путь от s до v. пример:

   2
u --- v
1 \ / 3
   s

Самый длинный путь от u до s состоит из пути u - v - s (длина 5), в то время как самый длинный путь от u до v - это u - s - v (длина 4).

Это свойство оптимальной подструктуры позволяет использовать жадные алгоритмы и (эффективное) динамическое программирование для эффективного решения самой широкой проблемы пути, но (насколько известно) не позволяет эффективно решить проблему самого длинного пути. Кстати, вы можете сделать аналогичный аргумент о кратчайших путях (если кратчайший путь от u до v проходит через s, у вас есть конкатенация кратчайших путей от u до s и от s до v), и вы можете использовать аналогичные жадные алгоритмы или DP для определения кратчайших путей.

Надеюсь это поможет!