Дмитрий Радищев (dibr) wrote,
Дмитрий Радищев
dibr

выбраться откуда угодно

     Вообще оно tl;dr, но любопытно.

     Оказывается, для графа, удовлетворяющего довольно простым условиям (в частности, им удовлетворяют все или почти все "карты дорог на местности"), существует "последовательность ходов", гарантированно выводящая "заблудившегося путника" из произвольной неизвестной точки в любую заданную точку (ещё для этого понадобится метод сопоставления "хода" и реальной местности для неизвестной ни путнику, ни составителю последовательности, текущей точки, но для этого можно использовать например компас - нумеровать дороги "от севера по часовой стрелке", "ходом" является порядковый выбираемой дороги номер).
     Причём, поскольку "последовательность ходов" зависит от графа (карты), ну и конечно от конечной точки, но не зависит от начальной точки (ведь она неизвестна и может быть любой), всё становится совсем интересно: например, можно выбраться из любых городских дебрей, понятия не имея где находишься, но имея заранее заготовленную шпаргалку с "путём домой из любой точки". Или - на вопрос "как до тебя добраться?" - можно давать такую же шпаргалку, не спрашивая "а откуда ты поедешь" :-)

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

     From avva
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 5 comments