Блог

У меня есть симметричная матрица, подобная показанной на изображении, прикрепленном ниже.

Я составил обозначение A.B, которое представляет значение в точке сетки (A, B). Кроме того, написание A.B.C дает мне минимальное значение точки сетки примерно так: MIN((A, B), (A, C), (B, C)).

В качестве другого примера A.B.D дает мне MIN((A, B), (A, D), (B, D)).

Моя цель — найти минимальные значения для ВСЕХ комбинаций букв (не повторяющихся) для одной строки за раз, например, для этого примера мне нужно найти минимальные значения относительно строки A, которые задаются вычислениями:

A.B = 6
A.C = 8
A.D = 4
A.B.C = MIN (6,8,6) = 6
A.B.D = MIN (6, 4, 4) = 4
A.C.D = MIN(8, 4, 2) = 2
A.B.C.D = MIN(6, 8, 4, 6, 4, 2) = 2

Я понимаю, что некоторые вычисления могут быть использованы повторно, что становится все более важным по мере увеличения размера матрицы, но проблема заключается в поиске наиболее эффективного способа реализации этого повторного использования.

Можете указать мне правильное направление для поиска эффективного алгоритма / структуры данных, которые я могу использовать для решения этой проблемы?

Вам нужно подумать о решетке подмножеств букв, упорядоченных по включению. По сути, у вас есть значение f (S), заданное для каждого подмножества S размера 2 (то есть для каждого недиагонального элемента матрицы — диагональные элементы, похоже, не встречаются в вашей задаче), и проблема состоит в том, чтобы найти для каждого подмножества T размером больше двух минимальное значение f (S) для всех S размера 2, содержащихся в T. (И тогда вас интересуют только наборы T, которые содержат определенный элемент «A» — но мы пока не будем обращать на это внимания.)

Прежде всего, обратите внимание, что если у вас n букв, то это равносильно заданию Omega(2 ^ n) вопросов, примерно по одному на каждое подмножество. (Исключение подмножеств с нулевым и одноэлементным значениями, а также тех, которые не включают «A», экономит вам n 1 наборов и коэффициент в два, соответственно, что разрешено для большой омеги.) Итак, если вы хотите сохранить все эти ответы даже для умеренно большого n, вам понадобится много памяти. Если в ваших приложениях n велико, возможно, было бы лучше сохранить некоторую коллекцию предварительно вычисленных данных и выполнять некоторые вычисления всякий раз, когда вам нужна конкретная точка данных; Я не думал о том, что будет работать лучше всего, но, например, вычисление данных только для двоичного дерева, содержащегося в решетке, не обязательно поможет вам что-либо, кроме предварительного вычисления вообще ничего.

Убрав с пути эти вещи, давайте предположим, что вы действительно хотите, чтобы все ответы были вычислены и сохранены в памяти. Вы захотите вычислить их «слой за слоем», то есть, начиная с трехэлементных подмножеств (поскольку двухэлементные подмножества уже заданы вашей матрицей), затем четырехэлементных, затем пятиэлементных и т.д. Таким образом, для данного подмножества S, когда мы вычисляем f (S), мы уже вычислили все f (T) для T, строго содержащиеся в S. Есть несколько способов, которыми вы можете воспользоваться этим, но я думаю, что самым простым может быть использование двух таких подмножеств S: пусть t1 и t2 будут двумя разными элементами T, которые вы можете выбрать, как вам нравится; пусть S будет подмножеством T, которое вы получаете при удалении t1 и t2. Запишите S1 для S плюс t1 и запишите S2 для S плюс t2. Теперь каждая пара букв, содержащихся в T, либо полностью содержится в S1, либо она полностью содержится в S2, либо она равна {t1, t2}. Найдите f (S1) и f (S2) в ранее вычисленных значениях, затем найдите f ({t1, t2}) непосредственно в матрице и сохраните f (T) = минимальное из этих 3 чисел.

Если вы никогда не выбираете «A» для t1 или t2, то действительно вы можете вычислить все, что вас интересует, не вычисляя f для любых наборов T, которые не содержат «A». (Это возможно, потому что описанные выше шаги интересны только тогда, когда T содержит по крайней мере три элемента.) Хорошо! Остается только один вопрос — как сохранить вычисленные значения f (T). Что бы я сделал, так это использовал массив размером 2 ^ (n-1); представлял каждое подмножество вашего алфавита, включающее «A», с помощью (n-1) разрядного номера, где i-й бит равен 1 всякий раз, когда (i 1)-я буква находится в этом наборе (таким образом, 0010110, который имеет набор битов 2, 4 и 5, представляет подмножество {«A», «C», «D», «F»} из алфавита «A» .. «H » — обратите внимание, что я считаю биты, начинающиеся с 0 справа, и буквы, начинающиеся с «A» = 0). Таким образом, вы действительно можете выполнять итерации по наборам в числовом порядке, и вам не нужно думать о том, как выполнять итерации по всем k-элементным подмножествам n-элементного набора. (Вам нужно включить специальный случай, когда рассматриваемый набор содержит 0 или 1 элемент, в этом случае вам ничего не захочется делать, или 2 элемента, в этом случае вы просто копируете значение из матрицы.)

Ну, мне это кажется простым, но, возможно, я неправильно понимаю проблему. Я бы сделал это так:

• пусть P это строка шаблона в вашей системе обозначений, X1.X2. ... .Xn где Xi — столбец в вашей матрице

• сначала вычислите массив CS = [ (X1, X2), (X1, X3), ... (X1, Xn) ] , который содержит все комбинации X1 с любым другим элементом в шаблоне; CS имеет n-1 элементы, и вы можете легко построить его в O (n)

• теперь вы должны вычислить min (CS) , то есть найти минимальное значение элементов матрицы, соответствующих комбинациям в CS ; опять же, вы можете легко найти минимальное значение в O (n)

• Выполнено.

Примечание: поскольку ваша матрица симметрична, учитывая, что P вам просто нужно вычислить CS , объединив первый элемент P со всеми остальными элементами: (X1, Xi) равно (Xi, X1)

Если ваша матрица очень большая, и вы хотите выполнить некоторую оптимизацию, вы можете рассмотреть префиксы P : позвольте мне объяснить на примере

• когда вы решите задачу для P = X1.X2.X3 , сохраните результат в ассоциативной карте, где X1.X2.X3 находится ключ

• позже, когда вы решаете задачу, P' = X1.X2.X3.X7.X9.X10.X11 вы ищете самый длинный префикс P' в вашей карте: вы можете сделать это, начав с P' и удаляя по одному компоненту ( Xi ) за раз с конца, пока не найдете совпадение на вашей карте или в итоге не получите пустую строку

• если вы нашли префикс P' на своей карте, то вы уже знаете решение этой проблемы, поэтому вам просто нужно найти решение проблемы, возникающей в результате объединения первого элемента префикса с суффиксом, а затем сравнить два результата: в нашем примере префиксом является X1.X2.X3 , и поэтому вам просто нужно решить проблему для X1.X7.X9.X10.X11 , а затем сравнить два значения и выбрать минимальное (не забудьте обновить свою карту новым шаблоном P' )

• если вы не нашли ни одного префикса, то вы должны решить всю проблему для P' (и снова не забудьте обновить карту с результатом, чтобы вы могли повторно использовать ее в будущем)

По сути, этот метод является формой запоминания.