рассмотрим, что у нас есть полный граф с n вершинами. Каждая вершина имеет значение. вес края между двумя вершинами i и j равен значению [i] xor value [j].
Вопрос заключается в том, чтобы найти путь от вершины 1 до вершины n, где максимум вложений ребер в пути минимален. Я уже модифицировал алгоритм Дейкстры и нашел алгоритм O (n^2 lg (n)). может ли кто-нибудь помочь мне найти более эффективный алгоритм?найти минимальный путь узких путей на графике
Минимальное значение «узкого места» не может быть меньше числа, определенного самым значимым битом (M) этого значения: value[1] XOR value[n]. Если вы обнаружили два узла A и B, таким образом, что M и высших биты узлов 1 и A равны, а также равно являются M и старшие бит узлов n и B, с минимальным весом ребра между A и B, минимальным путем узкого места будет 1-ABn (или может быть короче, если A = 1 и/или B = n).
Чтобы выбрать A/B пару с минимальным весом края, построить двоичный синтаксического дерева для всех значений узлов с битами высокого порядка (M и выше), совпадающей с узлом 1. Затем для всех значений узла с битами высокого порядка, совпадающих с узлом n, попробуйте выполнить поиск этих значений в этом trie. Если точное совпадение не найдено, выберите наиболее глубокое частичное совпадение.
Сложность времени - O (n * M).
Вы имеете в виду O (n * log n)? Или O (n^(log n))? – templatetypedef
@templatetypedef Я думаю, что он означает O (n * n * logn)? –