Блог

Человек идет по 1-й горизонтальной линии. На линии существует несколько мигалок. Мигалка-это устройство, которое может мгновенно телепортировать человека из одной конечной точки в другую на одной и той же линии. Этот путь телепортации можно представить в виде дуги над линией. Предположим, индивид хочет идти на восток. Мигалки распределены произвольно по линии. Хотя пути телепортации могут перекрываться, конечные точки не могут. Так, например, путь от a1 до a2 может иметь дугу, которая перекрывается с b1 до b2, но конечные точки не могут начинаться/заканчиваться в одном и том же месте. Вот наглядная схема:

В зависимости от того, какой конечной точки достигает индивид, его можно транспортировать на восток или на запад (например, если индивид каким-то образом попал на конечную точку b2, он будет транспортирован обратно в b1.

Вопрос в том, как мы можем доказать, что независимо от того, как размещены Мигалки, индивид всегда доберется до места назначения t? Я предполагаю, что требуются некоторые знания теории графов, но я в замешательстве, потому что это не похоже на DAG

Прежде всего, превратив эту проблему в график:

• Узлы: S, a1, a2, b1, b2, c1, c2, d1, d2, t
• Края:
  • если это дуга: двунаправленное ребро со стоимостью=0
  • если это «естественный» путь (например, S->a1 или a1 ->> b1): >>направленное ребро со стоимостью=1

Затем ваш пример превращается в:

Чтобы следовать правилам задачи, мы должны пересечь график от S до t, всегда следуя ребру с наименьшей доступной стоимостью (за исключением ребра, только что использованного для прибытия в узел).

Превращение этих линий и мигалок в графики всегда приведет к графу с важным свойством: каждый узел имеет ровно 2 направленных ребра (одно приходящее и одно уходящее) и ровно 1 неориентированное ребро. (кроме S и t).
Теперь единственный способ, чтобы t не был доступен, — это если на графике существует цикл cost=0. Из-за упомянутого имущества это невозможно.

Фактически, каждый узел в графике в конечном итоге будет достигнут, за исключением «параллельных мостов», таких как (d1, d2) , покрытых (c1, c2). Эти узлы (d1, d2) могут быть легко обнаружены и удалены, поскольку до них невозможно добраться. Если внутри одного из этих мостов есть что-то, что не «телепортируется» за пределы моста, вы тоже можете это удалить.

Первое уведомление:

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

Теперь ключевая идея: для каждого используемого ребра (отрезка линии или мигалки) есть ровно одно ребро, которое может предшествовать ему.

• чтобы использовать отрезок линии, путь должен проходить через мигалку на его западном конце
• чтобы использовать мигалку на запад, путь должен проходить через отрезок линии, ведущий к его восточной конечной точке
• чтобы использовать мигалку на восток, путь должен проходить через отрезок линии, ведущий к его западной конечной точке

Таким образом, если на графике есть цикл (например, d1>d2>>c2>>>c1 в вашем примере), он доступен только с ребер, которые являются частью цикла; >>>нет способа войти в цикл, если исходить из начала строки.

(Даже если в самом начале есть мигалка, нет отрезка линии, который можно было бы использовать, чтобы добраться до нее снова, поэтому начало никогда не является частью цикла)

Поэтому любой путь с самого начала не будет бесконечным и приведет к месту назначения.