динамического программирования Алгоритм Notation

Question

Из главы 6 алгоритмов, С. Дасгупта, К. Пападимитриу, У. Вазирани, 2006.

Я пытаюсь понять некоторые из psuedocode с алгоритмами в начале этой главы. Первый из них - the topological sort linearization Я понимаю процедуры dist и min. Но я не понимаю обозначения min *subscript* (u, v)∈Edges {dist(u) + l(u, v)}. Кто-нибудь знает, как описать каждую часть этой конкретной нотации. Является ли это циклическим переходом через любой узел u, связанный с v с помощью направленного края?

Мой второй вопрос - это обозначение в Longest Increasing Subsequence algorithm.. Как вы интерпретируете max{L(i):(i, j)∈Edges}. Что означает двоеточие в этом утверждении? И в тексте я вижу L(.) и что это значит?

Answer 1

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

Оба обозначения являются вариантами для определения этого домена. Первый из них в основном говорит: «Учитывая все пары (u, v) в Edges наборе, найти минимальное значение dist(u) + l(u, v)

Второй вариант определяет множество значений:. {L(i) : (i, j) ∈ Edges} это совокупность всех значений L(i), которые могут быть образованы из пары (i, j) в наборе Edges. Тогда максимальный оператор находит максимальное значение из этого набора.

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

На самом деле оба варианта могут использоваться взаимозаменяемо. Вероятно, это просто некоторая несогласованность между авторами в том, что книга использовала и то, и другое.