Задача с независимым множеством максимального веса для графа путей

Question

Принимая класс Algorithms: Design and Analysis II , один из вопросов касается вопроса о задаче с независимым множеством максимального веса для графа путей.ниже показан (размытый) снимок экрана с описанием проблемы, и соответствующие видео лекции на YouTube:

https://www.youtube.com/watch?v=0awkct8SkxA

https://www.youtube.com/watch?v=pLOkbHGRsv0

https://www.youtube.com/watch?v=Im_zjFkZDCY

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

a[i] = max(a[i - 1], a[i - 2] + w[i])

Вопрос заключается в следующем:

Что из следующего верно для нашего алгоритма динамического программирования для вычисления независимого от максимального веса набора графа путей?(Предположим, что связей нет.)

• Пока входной граф имеет хотя бы две вершины, алгоритм никогда не выбирает вершину с минимальным весом.
• Алгоритм всегда выбираетвершина максимального веса.
• Если вершина исключается из оптимального решения двух последовательных подзадач, то она исключается из оптимальных решений всех больших подзадач.
• Если вершина исключается изоптимальное решение подзадачи, то она исключается из оптимальных решений всех больших подзадач.

Оказывается, правильный ответ # 3, что несколько интуитивно понятно, так как оптимальныйРешение подзадачи зависит только от решений двух предыдущих подзадач.Но мне не понятно, почему варианты 1 и 2 неверны.Поскольку алгоритм просматривает все вершины, кажется, что оба эти параметра также должны быть правильными.

Answer 1

ОП здесь: Вот полный ответ для полноты картины, вдохновленный ответом @ robert-king.

Рассмотрим путь 10-2-1-4.Вершины, выбранные алгоритмом: 10, 1, где 1, минимум, выбран.Таким образом, вариант 1 неверен.

Рассмотрим путь 1-3-10-9.Вершины, выбранные алгоритмом: 3, 9, где максимум 10 не выбран.Таким образом, вариант 2 неверен.

Рассмотрим путь 1-9-7-1-5.Вершины, выбранные алгоритмом: 1, 7, 5.Однако 7 не было включено в оптимальное решение подзадачи 1-9-7.Обратите внимание, что 7 также не был включен в оптимальное решение подзадачи 1-9-7-1, потому что его предыдущая вершина была «тяжелее», и поскольку все веса положительны, сумма следующего веса и более тяжелой вершины, безусловно, равнабольше чем 7.Таким образом, вариант 4 неверен.

Вариант 3 верен.Это следует из индукции, поскольку оптимальное решение подзадачи зависит только от решений двух предыдущих подзадач.

Answer 2

the algorithm never selects the minimum-weight vertex.

Обратите внимание: ** 3-100-4-1-5-100-6 имеет смысл выбрать 1, минимум, так как мы хотим выбрать две 100-х

The algorithm always selects the maximum-weight vertex.

Рассмотрим: 5-99-100-99-7

Имеет смысл исключить максимум в пользу 99-х

. Для обоих этих примеров попробуйте посмотреть, чтоалгоритм будет работать, и почему он работает.

Хороший способ рассуждать об этих типах проблем - попробовать все варианты (0,0,0,1,1,1,2,2,2,3,3,3,99,99,99,100,100,100), и это даст вам большинство возможностей.