Интервью: Найти кратчайший путь к нескольким элементам

Question

Существует музей, организованный как комната NxN. Некоторые номера запираются и недоступны. Другие номера открыты, а в некоторых номерах есть охрана. Охранники могут двигаться только на север, юг, восток и запад, только через открытые комнаты и только внутри музея. Для каждой комнаты найдите кратчайшее расстояние до охранника. Какова временная сложность вашего алгоритма?

Answer 1

В начале, рассмотрим относительно наивный подход.

С каждым охранник G как вершина в наборе номера, R = N * N, и возможных путей между смежными комнатами (ребер) Е.

Если все комнаты минимальные расстояния должны быть известны, BFS друг от охранять каждую комнату.

Это должно занять время G * (R+E) или что-то вроде G*(N*N+E), или G*(N*N).

Это, безусловно, может быть оптимизировано с помощью memoization, так как каждая BFS будет повторно обрабатывать поддеревья, которые уже были завершены. В зависимости от конфигурации помещения это может значительно снизить значение G по сравнению с вышеуказанной временной сложностью. Однако я уверен, что должно быть что-то лучше этого.

Answer 2

Вам просто нужно посмотреть на этот музей как на один график и использовать алгоритм Диджикстра.

wiki link

У вас есть обсуждение сложности на данной странице.

Answer 3

Вы можете найти кратчайший путь алгоритм Дейкстры реализован в этой серии постов:

Breadth and depth first search

Answer 4

Графическое решение Каждый номер представляет собой узел Есть края только между комнатами, где дверь открыта использовать алгоритм Флойд-Воршалл, а затем проверить минимальное расстояние между каждой комнатой и каждым защитным

количества комнаты - R = N^2

количество охранников - G

временная сложность представляет собой о (R^3 + R * G) = O (R^3) = O (N^6)

R^3 для Floyd-Warshall

Answer 5

Я предполагаю функцию edgeCost (i, j), которая возвращает стоимость перехода из комнаты i в комнату j (бесконечная, если ее нет, 1 в противном случае). Также edgeCost (i, i) = 0 и отрицательных циклов нет. Пусть R- количество комнат (R = N^2 в вашем случае):

int path[R][R]; 
/* 
* Each path[i][j] is initialized to 
* edgeCost(i,j) or infinity if there is no 
* edge between i and j. 
*/ 

function play(): 
for k = 1 to R: 
    for i = 1 to R: 
    for j = 1 to R: 
    path[i][j] = min(path[i][j], path[i][k] + path[k][j]); 

Или, как вы знаете это, алгоритм Флойда-Воршалла (все пары кратчайших путей), с O (| R |^3) временная сложность.

Answer 6

Если мы дополняем музейный граф искусственным источником и краями нулевой длины от источника до каждого охранника, то дерево кратчайших путей с одним источником, вычисляемое через BFS (невзвешенный)/Dijkstra (взвешенный) во времени Õ (n + g), дает расстояние от каждой комнаты до ближайшего охранника.

Answer 7

Имейте очередь, чьи записи содержат адрес одного квадрата вместе с целым числом. Поместите места всех охранников в очередь, каждая из которых помечена целым числом «0». Каждый квадрат должен иметь номер для номера, и все они должны быть изначально пустыми.

Затем, пока в очереди есть что-то, вытащите запись из очереди и проверьте, имеет ли значение квадрат, о котором идет речь, с заметным значением. Если это так, просто игнорируйте эту запись в очереди и переходите к следующей. В противном случае отметьте квадрат значением из очереди и поместите все соседние квадраты с прямой доступностью в очередь со значением, большим, чем значение текущей настоящей записи (так как каждая из первой партии квадратов вытягивается из очереди, они получат значение «1»). Каждый квадрат будет посещаться только один раз, когда он будет пустым, и каждый посещенный квадрат приведет к постановке в очередь не более четырех квадратов, поэтому общее количество элементов, проходящих через очередь, будет в четыре раза больше числа квадратов плюс количество охранников , Это значение можно легко уменьшить с помощью постоянного коэффициента, проверив каждый квадрат, чтобы увидеть, если он пуст, прежде чем добавлять его в очередь; это не устранит все избыточные очереди, но устранит их.

Answer 8

Вот краткое изложение оптимального решения (O (N^2)), упоминается IVlad и throwawayacct. По какой-то причине их голос не слышен :)

Рассмотрите сетку NxN как график с узлами, представляющими комнаты и края, представляющие двери между смежными комнатами. Все ребра имеют вес 1. Набор узлов U обозначается как «охраняемые комнаты».

Идея состоит в использовании обхода BFS, который начинается с нового узла, подключенного ко всем охраняемым комнатам, и сканирует комнаты в порядке увеличения расстояния от v0. Каждый раз, когда узел посещается, количество шагов, которые были сделаны для достижения этого представляет собой расстояние от охраняемого помещения, и гарантированно будут минимальными из-за порядка расширения пути:

Add an artificial node v0 and connect it to all nodes in U 
Create a simple queue Q, that stores pairs <node, dist> 
Q.enqueue(<v0, -1>) 
Create a hash set S, that contains all visited nodes 
S.add(v0) 
while not Q.isEmpty() { 
    pathTail := Q.dequeue() 
    output distance pathTail.dist for node pathTail.node 
    for all neighbours v of pathTail.node 
     if not S.contains(v) 
      Q.add(<v, pathTail.dist + 1>) 

    S.add(pathTail.node) 

} 

анализ Сложности

Обратите внимание, что график плоский, поэтому мы имеем | V | + | E | = O (| V |). Следовательно, эта BFS работает в O (| V |) = O (N^2) времени.

Тот факт, что мы имеем единый вес для краев, делает вещи простыми; в очереди гарантировано однообразное значение расстояния. Например, с помощью dijkstra края могут отличаться по своему весу, поэтому необходима очередь приоритетов, и это влияет на временную сложность. Та же проблема, представленная здесь, с разным весом между комнатами, потребовала бы O (N N log N) времени.