Вам нужно подумать о решетке подмножеств букв, упорядоченных по включению . По сути, у вас есть значение f (S), заданное для каждого подмножества S размера 2 (то есть каждого недиагонального элемента матрицы - кажется, что диагональные элементы не встречаются в вашей задаче), и проблема состоит в том, чтобы найти для каждого подмножества T размера больше двух минимальное значение f (S) для всех S размера 2, содержащихся в T. (И тогда вас интересуют только множества T, которые содержат определенный элемент «A» - но мы не обращайте на это внимания на данный момент.)
Прежде всего, обратите внимание, что если у вас есть n букв, это равносильно тому, что вы задаете Omega (2 ^ n) вопросов, примерно по одному на каждое подмножество. (Исключая подмножества с нулевым и одноэлементным и те, которые не включают «A», экономит вам n + 1 наборов и коэффициент два, соответственно, что допускается для большой Омега .) Так что если Вы хотите хранить все эти ответы даже для среднего размера, вам потребуется много памяти. Если 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 элемента, и в этом случае вы просто копируете значение из матрицы.)