это лучшая сложность, которую я могу получить?

Question

Проблема заключается в следующем: у вас есть n фигурок домино и два числа на каждой фигурке домино (n фигур), также есть дополнительный набор из m фигурок домино, но вы можете использовать только одну фигурку из этого набора (вMost), чтобы помочь вам сделать следующее: вычислите минимальное количество фигур домино, которое вы можете использовать, чтобы перейти от заданной начальной точки S к конечной точке D. Это означает, что начальная часть должна иметь номер (S) и конечную частьдолжен иметь номер (D).Введите: n и номера фигур домино (n пар).m и номера дополнительных фигур домино (m пар).начальная точка S и пункт назначения D. Вывод: минимальное количество фигур домино.

Я думаю об использовании BFS для этой задачи, где я могу начать с S и найти минимальный путь к D с постоянно удаляющимся узлом m(i) из графа и добавление узла m (i + 1), но при этом сложность времени будет O (n * m).но не только это, может быть несколько начальных точек S, поэтому сложность будет O (| S | * n * m).это может быть решено лучше?Учитель сказал, что это можно решить за линейное время, но я просто очень растерялся.

Answer 1

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

Нахождение кратчайших путей от одного S до D за линейное время

Давайте строить идею постепенно. Во-первых, давайте попробуем решить более простую версию проблемы, где нам просто нужно выяснить, можно ли вообще перейти от одного S к одному D, используя не более одного домино из набора дополнительных M домино.

Я предлагаю подойти к этому следующим образом: выполнить некоторую предварительную обработку для N домино, которая позволит вам (для каждого из M дополнительных домино) быстро (в постоянное время) ответить, существует ли путь из S в D, который проходит через это домино. (И, конечно, нам нужно помнить крайний случай, когда нам вообще не нужно лишнее домино, но его легко охватить за линейное время.)

Какая информация позволяет вам ответить на этот вопрос? Допустим, вы смотрите на домино с номерами A и B на концах. Если вы знали, что можете добраться от S до A и от B до D, вы используете это домино, чтобы добраться от S до D, верно? Альтернативно, если бы был путь от S до B и от A до D, это также сработало бы. Если ни то, ни другое не верно, то это домино никак не может помочь вам добраться от S до D.

Это замечательно, но если мы будем запускать BFS из всех возможных B, мы не достигнем линейной сложности времени. Тем не менее, обратите внимание, что вы можете обратить вспять вторую проблему (обнаружение, существует ли путь от B до D) и обозначить ее как «могу ли я добраться от D до каждого возможного B»? На это легко ответить с помощью одной BFS.

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

Нахождение кратчайших путей из множества S в D за линейное время

Давайте обратимся к проблеме и скажем, что мы хотим найти кратчайшие пути от D до нескольких S. Вы можете создать ориентированный граф с вдвое большим количеством узлов, чем было написано уникальных чисел на домино. То есть для каждого номера есть узлы V и V ', и если вы находитесь в V, это означает, что вы еще не использовали лишнее домино, но если вы находитесь в V', это означает, что вы уже использовали один. Каждому ядру (то есть одному из исходных N) домино (A, B) соответствует 4 ребра в этом графе: (A -> B), (B -> A), (A '-> B'), ( B '-> A'). Каждому дополнительному домино соответствует 2 ребра: (A -> B '), (B -> A'). Обратите внимание, что как только мы попадем в узел с ', мы никогда не сможем выбраться из него, поэтому мы будем использовать не более одного дополнительного домино. Один BFS из D на этом графике ответит на проблему.