Как найти весь путь: Простое объяснение алгоритмов поиска пути и A* / Хабр

Простое объяснение алгоритмов поиска пути и A* / Хабр

Часть 1. Общий алгоритм поиска

Введение

Поиск пути — это одна из тех тем, которые обычно представляют самые большие сложности для разработчиков игр. Особенно плохо люди понимают алгоритм A*, и многим кажется, что это какая-то непостижимая магия.

Цель данной статьи — объяснить поиск пути в целом и A* в частности очень понятным и доступным образом, положив таким образом конец распространённому заблуждению о том, что эта тема сложна. При правильном объяснении всё достаточно просто.

Учтите, что в статье мы будем рассматривать поиск пути для игр; в отличие от более академических статей, мы опустим такие алгоритмы поиска, как поиск в глубину (Depth-First) или поиск в ширину (Breadth-First). Вместо этого мы постараемся как можно быстрее дойти от нуля до A*.

В первой части мы объясним простейшие концепции поиска пути. Разобравшись с этими базовыми концепциями, вы поймёте, что A* на удивление очевиден.

Простая схема

Хотя вы сможете применять эти концепции и к произвольным сложным 3D-средам, давайте всё-таки начнём с чрезвычайно простой схемы: квадратной сетки размером 5 x 5. Для удобства я пометил каждую ячейку заглавной буквой.
Простая сетка.

Самое первое, что мы сделаем — это представим эту среду в виде графа. Я не буду подробно объяснять, что такое граф; если говорить просто, то это набор кружков, соединённых стрелками. Кружки называются «узлами», а стрелки — «рёбрами».

Каждый узел представляет собой «состояние», в котором может находиться персонаж. В нашем случае состояние персонажа — это его позиция, поэтому мы создаём по одному узлу для каждой ячейки сетки:

Узлы, обозначающие ячейки сетки.

Теперь добавим рёбра. Они обозначают состояния, которых можно «достичь» из каждого заданного состояния; в нашем случае мы можем пройти из любой ячейки в соседнюю, за исключением заблокированных:

Дуги обозначают допустимые перемещения между ячейками сетки.

Если мы можем добраться из A в B, то говорим, что B является «соседним» с A узлом.

Стоит заметить, что рёбра имеют направление; нам нужны рёбра и из A в B, и из B в A. Это может показаться излишним, но не тогда, когда могут возникать более сложные «состояния». Например, персонаж может упасть с крыши на пол, но не способен допрыгнуть с пола на крышу. Можно перейти из состояния «жив» в состояние «мёртв», но не наоборот. И так далее.

Пример

Допустим, мы хотим переместиться из A в T. Мы начинаем с A. Можно сделать ровно два действия: пройти в B или пройти в F.

Допустим, мы переместились в B. Теперь мы можем сделать два действия: вернуться в A или перейти в C. Мы помним, что уже были в A и рассматривали варианты выбора там, так что нет смысла делать это снова (иначе мы можем потратить весь день на перемещения A → B → A → B…). Поэтому мы пойдём в C.

Находясь в C, двигаться нам некуда. Возвращаться в B бессмысленно, то есть это тупик. Выбор перехода в B, когда мы находились в A, был плохой идеей; возможно, стоит попробовать вместо него F?

Мы просто продолжаем повторять этот процесс, пока не окажемся в T. В этот момент мы просто воссоздадим путь из A, вернувшись по своим шагам. Мы находимся в T; как мы туда добрались? Из O? То есть конец пути имеет вид O → T. Как мы добрались в O? И так далее.

Учтите, что на самом деле мы не движемся; всё это было лишь мысленным процессом. Мы продолжаем стоять в A, и не сдвинемся из неё, пока не найдём путь целиком. Когда я говорю «переместились в B», то имею в виду «представьте, что мы переместились в B».

Общий алгоритм

Этот раздел — самая важная часть всей статьи. Вам абсолютно необходимо понять его, чтобы уметь реализовывать поиск пути; остальное (в том числе и A*) — это просто детали. В этом разделе вы будете разбираться, пока не поймёте смысл.

К тому же этот раздел невероятно прост.

Давайте попробуем формализовать наш пример, превратив его в псевдокод.

Нам нужно отслеживать узлы, которых мы знаем как достичь из начального узла. В начале это только начальный узел, но в процессе «исследования» сетки мы будем узнавать, как добираться до других узлов. Давайте назовём этот список узлов reachable:

reachable = [start_node]

Также нам нужно отслеживать уже рассмотренные узлы, чтобы не рассматривать их снова. Назовём их explored:

explored = []

Дальше я изложу ядро алгоритма: на каждом шаге поиска мы выбираем один из узлов, который мы знаем, как достичь, и смотрим, до каких новых узлов можем добраться из него. Если мы определим, как достичь конечного (целевого) узла, то задача решена! В противном случае мы продолжаем поиск.

Так просто, что даже разочаровывает? И это верно. Но из этого и состоит весь алгоритм. Давайте запишем его пошагово псевдокодом.

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

while reachable is not empty:

Мы выбираем один из узлов, до которого знаем, как добраться, и который пока не исследован:

    node = choose_node(reachable)

Если мы только что узнали, как добраться до конечного узла, то задача выполнена! Нам просто нужно построить путь, следуя по ссылкам previous обратно к начальному узлу:

    if node == goal_node:
       path = []
       while node != None:
            path.add(node)
            node = node.previous
        
        return path

Нет смысла рассматривать узел больше одного раза, поэтому мы будем это отслеживать:

    reachable.remove(node)
    explored.add(node)

Мы определяем узлы, до которых не можем добраться отсюда. Начинаем со списка узлов, соседних с текущим, и удаляем те, которые мы уже исследовали:

    new_reachable = get_adjacent_nodes(node) - explored

Мы берём каждый из них:

    for adjacent in new_reachable:

Если мы уже знаем, как достичь узла, то игнорируем его. В противном случае добавляем его в список reachable, отслеживая, как в него попали:

        if adjacent not in reachable:
            adjacent.previous = node  # Remember how we got there.
            reachable.add(adjacent)

Нахождение конечного узла — это один из способов выхода из цикла. Второй — это когда reachable становится пустым: у нас закончились узлы, которые можно исследовать, и мы не достигли конечного узла, то есть из начального в конечный узел пути нет:

return None

И… на этом всё. Это весь алгоритм, а код построения пути выделен в отдельный метод:

function find_path (start_node, end_node):
    reachable = [start_node]
    explored = []

    while reachable is not empty:
        # Choose some node we know how to reach.
        node = choose_node(reachable)

        # If we just got to the goal node, build and return the path.
        if node == goal_node:
            return build_path(goal_node)

        # Don't repeat ourselves.
        reachable.remove(node)
        explored.add(node)

        # Where can we get from here?
        new_reachable = get_adjacent_nodes(node) - explored
        for adjacent in new_reachable:
            if adjacent not in reachable
                adjacent.previous = node  # Remember how we got there.
                reachable.add(adjacent)

    # If we get here, no path was found :(
    return None

Вот функция, которая строит путь, следуя по ссылкам previous обратно к начальному узлу:

function build_path (to_node):
    path = []
    while to_node != None:
        path.add(to_node)
        to_node = to_node.previous
    return path

Вот и всё. Это псевдокод каждого алгоритма поиска пути, в том числе и A*.

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

Интерактивное демо

Вот демо и пример реализации показанного выше алгоритма (запустить его можно на странице оригинала статьи). choose_node просто выбирает случайный узел. Можете запустить алгоритм пошагово и посмотреть на список узлов reachable и explored, а также на то, куда указывают ссылки previous.
Заметьте, что поиск завершается, как только обнаруживается путь; может случиться так, что некоторые узлы даже не будут рассмотрены.

Заключение

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

Но что же отличает каждый алгоритм от другого, почему A* — это A*?

Вот подсказка: если запустить поиск в демо несколько раз, то вы увидите, что алгоритм на самом деле не всегда находит один и тот же путь. Он находит какой-то путь, и этот путь необязательно является кратчайшим. Почему?

Часть 2. Стратегии поиска

Если вы не полностью поняли описанный в предыдущем разделе алгоритм, то вернитесь к нему и прочтите заново, потому что он необходим для понимания дальнейшей информации. Когда вы в нём разберётесь, A* покажется вам совершенно естественным и логичным.

Секретный ингредиент

В конце предыдущей части я оставил открытыми два вопроса: если каждый алгоритм поиска использует один и тот же код, почему A* ведёт себя как A*? И почему демо иногда находит разные пути?

Ответы на оба вопроса связаны друг с другом. Хоть алгоритм и хорошо задан, я оставил нераскрытым один аспект, и как оказывается, он является ключевым для объяснения поведения алгоритмов поиска:

node = choose_node(reachable)

Именно эта невинно выглядящая строка отличает все алгоритмы поиска друг от друга. От способа реализации choose_node зависит всё.

Так почему же демо находит разные пути? Потому что его метод choose_node выбирает узел случайным образом.

Длина имеет значение

Прежде чем погружаться в различия поведений функции choose_node, нам нужно исправить в описанном выше алгоритме небольшой недосмотр.

Когда мы рассматривали узлы, соседние с текущим, то игнорировали те, которые уже знаем, как достичь:

if adjacent not in reachable:
    adjacent.previous = node  # Remember how we got there.
    reachable.add(adjacent)

Это ошибка: что если мы только что обнаружили лучший способ добраться до него? В таком случае необходимо изменить ссылку previous узла, чтобы отразить этот более короткий путь.

Чтобы это сделать, нам нужно знать длину пути от начального узла до любого достижимого узла. Мы назовём это стоимостью (cost) пути. Пока примем, что перемещение из узла в один из соседних узлов имеет постоянную стоимость, равную 1.

Прежде чем начинать поиск, мы присвоим значению cost каждого узла значение infinity; благодаря этому любой путь будет короче этого. Также мы присвоим cost узла start_node значение 0.

Тогда вот как будет выглядеть код:

if adjacent not in reachable:
    reachable.add(adjacent)

# If this is a new path, or a shorter path than what we have, keep it.
if node.cost + 1 < adjacent.cost:
    adjacent.previous = node
    adjacent.cost = node.cost + 1

Одинаковая стоимость поиска

Давайте теперь рассмотрим метод choose_node. Если мы стремимся найти кратчайший возможный путь, то выбирать узел случайным образом — не самая лучшая идея.

Лучше выбирать узел, которого мы можем достичь из начального узла по кратчайшему пути; благодаря этому мы в общем случае будем предпочитать длинным путям более короткие. Это не значит, что более длинные пути не будут рассматриваться вовсе, это значит, что более короткие пути будут рассматриваться первыми. Так как алгоритм завершает работу сразу после нахождения подходящего пути, это должно позволить нам находить короткие пути.

Вот возможный пример функции choose_node:

function choose_node (reachable):
    best_node = None

    for node in reachable:
        if best_node == None or best_node.cost > node.cost:
            best_node = node
    
    return best_node

Интуитивно понятно, что поиск этого алгоритма расширяется «радиально» от начального узла, пока не достигнет конечного. Вот интерактивное демо такого поведения:

Заключение

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

Но этот алгоритм всё равно в какой-то степени остаётся «глупым». Он продолжает искать повсюду, пока не наткнётся на конечный узел. Например, какой смысл в показанном выше примере выполнять поиск в направлении A, если очевидно, что мы отдаляемся от конечного узла?

Можно ли сделать choose_node умнее? Можем ли мы сделать так, чтобы он направлял поиск в сторону конечного узла, даже не зная заранее правильного пути?

Оказывается, что можем — в следующей части мы наконец-то дойдём до choose_node, позволяющей превратить общий алгоритм поиска пути в A*.

Часть 3. Снимаем завесу тайны с A*

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

Волшебный алгоритм

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

function choose_node (reachable):
    return magic(reachable, "любой узел, являющийся следующим на кратчайшем пути")

Звучит соблазнительно, но магическим чипам всё равно требуется какой-то низкоуровневый код. Вот какой может быть хорошая аппроксимация:

function choose_node (reachable):
    min_cost = infinity
    best_node = None

    for node in reachable:
        cost_start_to_node = node.cost
        cost_node_to_goal = magic(node, "кратчайший путь к цели")
        total_cost = cost_start_to_node + cost_node_to_goal

        if min_cost > total_cost:
            min_cost = total_cost
            best_node = node

    return best_node

Это отличный способ выбора следующего узла: вы выбираем узел, дающий нам кратчайший путь от начального до конечного узла, что нам и нужно.

Также мы минимизировали количество используемой магии: мы точно знаем, какова стоимость перемещения от начального узла к каждому узлу (это node.cost), и используем магию только для предсказания стоимости перемещения от узла к конечному узлу.

Не магический, но довольно потрясающий A*

К сожалению, магические чипы — это новинка, а нам нужна поддержка и устаревшего оборудования. БОльшая часть кода нас устраивает, за исключением этой строки:

# Throws MuggleProcessorException
cost_node_to_goal = magic(node, "кратчайший путь к цели")

То есть мы не можем использовать магию, чтобы узнать стоимость ещё не исследованного пути. Ну ладно, тогда давайте сделаем прогноз. Будем оптимистичными и предположим, что между текущим и конечным узлами нет ничего, и мы можем просто двигаться напрямик:

cost_node_to_goal = distance(node, goal_node)

Заметьте, что кратчайший путь и минимальное расстояние разные: минимальное расстояние подразумевает, что между текущим и конечным узлами нет совершенно никаких препятствий.

Эту оценку получить достаточно просто. В наших примерах с сетками это расстояние городских кварталов между двумя узлами (то есть abs(Ax - Bx) + abs(Ay - By)). Если бы мы могли двигаться по диагонали, то значение было бы равно sqrt( (Ax - Bx)^2 + (Ay - By)^2 ), и так далее. Самое важное то, что мы никогда не получаем слишком высокую оценку стоимости.

Итак, вот немагическая версия choose_node:

function choose_node (reachable):
    min_cost = infinity
    best_node = None

    for node in reachable:
        cost_start_to_node = node.cost
        cost_node_to_goal = estimate_distance(node, goal_node)
        total_cost = cost_start_to_node + cost_node_to_goal

        if min_cost > total_cost:
            min_cost = total_cost
            best_node = node

    return best_node

Функция, оценивающая расстояние от текущего до конечного узла, называется эвристикой, и этот алгоритм поиска, леди и джентльмены, называется … A*.

Интерактивное демо

Пока вы оправляетесь от шока, вызванного осознанием того, что загадочный A* на самом деле настолько прост, можете посмотреть на демо (или запустить его в оригинале статьи). Вы заметите, что в отличие от предыдущего примера, поиск тратит очень мало времени на движение в неверном направлении.

Заключение

Наконец-то мы дошли до алгоритма A*, который является не чем иным, как описанным в первой части статьи общим алгоритмом поиска с некоторыми усовершенствованиями, описанными во второй части, и использующим функцию choose_node, которая выбирает узел, который по нашей оценке приближает нас к конечному узлу. Вот и всё.

Вот вам для справки полный псевдокод основного метода:

function find_path (start_node, end_node):
    reachable = [start_node]
    explored = []

    while reachable is not empty:
        # Choose some node we know how to reach.
        node = choose_node(reachable)

        # If we just got to the goal node, build and return the path.
        if node == goal_node:
            return build_path(goal_node)

        # Don't repeat ourselves.
        reachable.remove(node)
        explored.add(node)

        # Where can we get from here that we haven't explored before?
        new_reachable = get_adjacent_nodes(node) - explored
        for adjacent in new_reachable:
            # First time we see this node?
            if adjacent not in reachable:
                reachable.add(adjacent)
        
            # If this is a new path, or a shorter path than what we have, keep it.
            if node.cost + 1 < adjacent.cost:
                adjacent.previous = node
                adjacent.cost = node.cost + 1

    # If we get here, no path was found :(
    return None

Метод build_path:

function build_path (to_node):
    path = []
    while to_node != None:
        path.add(to_node)
        to_node = to_node.previous
    return path

А вот метод choose_node, который превращает его в A*:

function choose_node (reachable):
    min_cost = infinity
    best_node = None

    for node in reachable:
        cost_start_to_node = node.cost
        cost_node_to_goal = estimate_distance(node, goal_node)
        total_cost = cost_start_to_node + cost_node_to_goal

        if min_cost > total_cost:
            min_cost = total_cost
            best_node = node

    return best_node

Вот и всё.

А зачем же нужна часть 4?

Теперь, когда вы поняли, как работает A*, я хочу рассказать о некоторых потрясающих областях его применения, которые далеко не ограничиваются поиском путей в сетке ячеек.

Часть 4. A* на практике

Первые три части статьи начинаются с самых основ алгоритмов поиска путей и заканчиваются чётким описанием алгоритма A*. Всё это здорово в теории, но понимание того, как это применимо на практике — совершенно другая тема.

Например, что будет, если наш мир не является сеткой?

Что если персонаж не может мгновенно поворачиваться на 90 градусов?

Как построить граф, если мир бесконечен?

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

Как найти кратчайший путь к любому из двух конечных узлов?

Функция стоимости

В первых примерах мы искали кратчайший путь между начальным и конечным узлами. Однако вместо того, чтобы хранить частичные длины путей в переменной length, мы назвали её cost. Почему?

Мы можем заставить A* искать не только кратчайший, но и лучший путь, причём определение «лучшего» можно выбирать, исходя из наших целей. Когда нам нужен кратчайший путь, стоимостью является длина пути, но если мы хотим минимизировать, например, потребление топлива, то нужно использовать в качестве стоимости именно его. Если мы хотим по максимуму увеличить «время, проводимое под солнцем», то затраты — это время, проведённое без солнца. И так далее.

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

Функция критерия

Допустим, наш объект — это автомобиль, и ему нужно добраться до заправки. Нас устроит любая заправка. Требуется кратчайший путь до ближайшей АЗС.

Наивный подход будет заключаться в вычислении кратчайшего пути до каждой заправки по очереди и выборе самого короткого. Это сработает, но будет довольно затратным процессом.

Что если бы мы могли заменить один goal_node на метод, который по заданному узлу может сообщить, является ли тот конечным или нет. Благодаря этому мы сможем искать несколько целей одновременно. Также нам нужно изменить эвристику, чтобы она возвращала минимальную оцениваемую стоимость всех возможных конечных узлов.

В зависимости от специфики ситуации мы можем и не иметь возможности достичь цели идеально, или это будет слишком много стоить (если мы отправляем персонажа через половину огромной карты, так ли важна разница в один дюйм?), поэтому метод is_goal_node может возвращать true, когда мы находимся «достаточно близко».

Полная определённость не обязательна

Представление мира в виде дискретной сетки может быть недостаточным для многих игр. Возьмём, например, шутер от первого лица или гоночную игру. Мир дискретен, но его нельзя представить в виде сетки.

Но есть проблема и посерьёзней: что если мир бесконечен? В таком случае, даже если мы сможем представить его в виде сетки, то у нас просто не будет возможности построить соответствующий сетке граф, потому что он должен быть бесконечным.

Однако не всё потеряно. Разумеется, для алгоритма поиска по графам нам определённо нужен граф. Но никто не говорил, что граф должен быть исчерпывающим!

Если внимательно посмотреть на алгоритм, то можно заметить, что мы ничего не делаем с графом, как целым; мы исследуем граф локально, получая узлы, которых можем достичь из рассматриваемого узла. Как видно из демо A*, некоторые узлы графа вообще не исследуются.

Так почему бы нам просто не строить граф в процессе исследования?

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

За пределами трёх измерений

Даже если ваш мир действительно является 2D-сеткой, нужно учитывать и другие аспекты. Например, что если персонаж не может мгновенно поворачиваться на 90 или 180 градусов, как это обычно и бывает?

Состояние, представляемое каждым узлом поиска, не обязательно должно быть только позицией; напротив, оно может включать в себя произвольно сложное множество значений. Например, если повороты на 90 градусов занимают столько же времени, сколько переход из одной ячейки в другую, то состояние персонажа может задаваться как [position, heading]. Каждый узел может представлять не только позицию персонажа, но и направление его взгляда; и новые рёбра графа (явные или косвенные) отражают это.

Если вернуться к исходной сетке 5×5, то начальной позицией поиска теперь может быть [A, East]. Соседними узлами теперь являются [B, East] и [A, South] — если мы хотим достичь F, то сначала нужно скорректировать направление, чтобы путь обрёл вид [A, East], [A, South], [F, South].

Шутер от первого лица? Как минимум четыре измерения: [X, Y, Z, Heading]. Возможно, даже [X, Y, Z, Heading, Health, Ammo].

Учтите, что чем сложнее состояние, тем более сложной должна быть эвристическая функция. Сам по себе A* прост; искусство часто возникает благодаря хорошей эвристике.

Заключение

Цель этой статьи — раз и навсегда развеять миф о том, что A* — это некий мистический, не поддающийся расшифровке алгоритм. Напротив, я показал, что в нём нет ничего загадочного, и на самом деле его можно довольно просто вывести, начав с самого нуля.

Дальнейшее чтение

У Амита Патела есть превосходное «Введение в алгоритм A*» [перевод на Хабре] (и другие его статьи на разные темы тоже великолепны!).

Базовые алгоритмы нахождения кратчайших путей во взвешенных графах / Хабр

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

Сформулируем определения и задачу.

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

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

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

Считаем, что в графе n вершин и m рёбер.

Пойдём от простого к сложному.

Алгоритм Флойда-Уоршелла

Находит расстояние от каждой вершины до каждой за количество операций порядка n^3. Веса могут быть отрицательными, но у нас не может быть циклов с отрицательной суммой весов рёбер (иначе мы можем ходить по нему сколько душе угодно и каждый раз уменьшать сумму, так не интересно).
В массиве d[0… n — 1][0… n — 1] на i-ой итерации будем хранить ответ на исходную задачу с ограничением на то, что в качестве «пересадочных» в пути мы будем использовать вершины с номером строго меньше i — 1 (вершины нумеруем с нуля). Пусть идёт i-ая итерация, и мы хотим обновить массив до i + 1-ой. Для этого для каждой пары вершин просто попытаемся взять в качестве пересадочной i — 1-ую вершину, и если это улучшает ответ, то так и оставим. Всего сделаем n + 1 итерацию, после её завершения в качестве «пересадочных» мы сможем использовать любую, и массив d будет являться ответом.
n итераций по n итераций по n итераций, итого порядка n^3 операций.
Псевдокод:

прочитать g // g[0 ... n - 1][0 ... n - 1] - массив, в котором хранятся веса рёбер, g[i][j] = 2000000000, если ребра между i и j нет
d = g
for i = 1 ... n + 1
     for j = 0 ... n - 1
          for k = 0 ... n - 1
              if d[j][k] > d[j][i - 1] + d[i - 1][k]
                  d[j][k] = d[j][i - 1] + d[i - 1][k]
вывести d

Алгоритм Форда-Беллмана

Находит расстояние от одной вершины (дадим ей номер 0) до всех остальных за количество операций порядка n * m. Аналогично предыдущему алгоритму, веса могут быть отрицательными, но у нас не может быть циклов с отрицательной суммой весов рёбер.
Заведём массив d[0… n — 1], в котором на i-ой итерации будем хранить ответ на исходную задачу с ограничением на то, что в путь должно входить строго меньше i рёбер. Если таких путей до вершины j нет, то d[j] = 2000000000 (это должна быть какая-то недостижимая константа, «бесконечность»). В самом начале d заполнен 2000000000. Чтобы обновлять на i-ой итерации массив, надо просто пройти по каждому ребру и попробовать улучшить расстояние до вершин, которые оно соединяет. Кратчайшие пути не содержат циклов, так как все циклы неотрицательны, и мы можем убрать цикл из путя, при этом длина пути не ухудшится (хочется также отметить, что именно так можно найти отрицательные циклы в графе: надо сделать ещё одну итерацию и посмотреть, не улучшилось ли расстояние до какой-нибудь вершины). Поэтому длина кратчайшего пути не больше n — 1, значит, после n-ой итерации d будет ответом на задачу.
n итераций по m итераций, итого порядка n * m операций.
Псевдокод:

прочитать e // e[0 ... m - 1] - массив, в котором хранятся рёбра и их веса (first, second - вершины, соединяемые ребром, value - вес ребра)
for i = 0 ... n - 1
    d[i] = 2000000000
d[0] = 0
for i = 1 ... n
    for j = 0 ... m - 1
        if d[e[j].second] > d[e[j].first] + e[j].value
            d[e[j].second] = d[e[j].first] + e[j].value
        if d[e[j].first] > d[e[j].second] + e[j].value
            d[e[j].first] = d[e[j].second] + e[j].value
вывести d

Алгоритм Дейкстры

Находит расстояние от одной вершины (дадим ей номер 0) до всех остальных за количество операций порядка n^2. Все веса неотрицательны.
На каждой итерации какие-то вершины будут помечены, а какие-то нет. Заведём два массива: mark[0… n — 1] — True, если вершина помечена, False иначе, d[0… n — 1] — для каждой вершины будет храниться длина кратчайшего пути, проходящего только по помеченным вершинам в качестве «пересадочных». Также поддерживается инвариант того, что для помеченных вершин длина, указанная в d, и есть ответ. Сначала помечена только вершина 0, а g[i] равно x, если 0 и i соединяет ребро весом x, равно 2000000000, если их не соединяет ребро, и равно 0, если i = 0.
На каждой итерации мы находим вершину, с наименьшим значением в d среди непомеченных, пусть это вершина v. Тогда значение d[v] является ответом для v. Докажем. Пусть, кратчайший путь до v из 0 проходит не только по помеченным вершинам в качестве «пересадочных», и при этом он короче d[v]. Возьмём первую встретившуюся непомеченную вершину на этом пути, назовём её u. Длина пройденной части пути (от 0 до u) — d[u]. len >= d[u], где len — длина кратчайшего пути из 0 до v (т. к. отрицательных рёбер нет), но по нашему предположению len меньше d[v]. Значит, d[v] > len >= d[u]. Но тогда v не подходит под своё описание — у неё не наименьшее значение d[v] среди непомеченных. Противоречие.
Теперь смело помечаем вершину v и пересчитываем d. Так делаем, пока все вершины не станут помеченными, и d не станет ответом на задачу.
n итераций по n итераций (на поиск вершины v), итого порядка n^2 операций.
Псевдокод:

прочитать g // g[0 ... n - 1][0 ... n - 1] - массив, в котором хранятся веса рёбер, g[i][j] = 2000000000, если ребра между i и j нет
d = g
d[0] = 0
mark[0] = True
for i = 1 ... n - 1
    mark[i] = False
for i = 1 ... n - 1
    v = -1
    for i = 0 ... n - 1
        if (not mark[i]) and ((v == -1) or (d[v] > d[i]))
            v = i
    mark[v] = True
    for i = 0 ... n - 1
        if d[i] > d[v] + g[v][i]
            d[i] = d[v] + g[v][i]
вывести d

Алгоритм Дейкстры для разреженных графов

Делает то же самое, что и алгоритм Дейкстры, но за количество операций порядка m * log(n). Следует заметить, что m может быть порядка n^2, то есть эта вариация алгоритма Дейкстры не всегда быстрее классической, а только при маленьких m.
Что нам нужно в алгоритме Дейкстры? Нам нужно уметь находить по значению d минимальную вершину и уметь обновлять значение d в какой-то вершине. В классической реализации мы пользуемся простым массивом, находить минимальную по d вершину мы можем за порядка n операций, а обновлять — за 1 операцию. Воспользуемся двоичной кучей (во многих объектно-ориентированных языках она встроена). Куча поддерживает операции: добавить в кучу элемент (за порядка log(n) операций), найти минимальный элемент (за 1 операцию), удалить минимальный элемент (за порядка log(n) операций), где n — количество элементов в куче.
Создадим массив d[0… n — 1] (его значение то же самое, что и раньше) и кучу q. В куче будем хранить пары из номера вершины v и d[v] (сравниваться пары должны по d[v]). Также в куче могут быть фиктивные элементы. Так происходит, потому что значение d[v] обновляется, но мы не можем изменить его в куче. Поэтому в куче могут быть несколько элементов с одинаковым номером вершины, но с разным значением d (но всего вершин в куче будет не более m, я гарантирую это). Когда мы берём минимальное значение в куче, надо проверить, является ли этот элемент фиктивным. Для этого достаточно сравнить значение d в куче и реальное его значение. А ещё для записи графа вместо двоичного массива используем массив списков.
m раз добавляем элемент в кучу, получаем порядка m * log(n) операций.
Псевдокод:

прочитать g // g[0 ... n - 1] - массив списков, в i-ом списке хранятся пары: first - вершина, соединённая с i-ой вершиной ребром, second - вес этого ребра
d[0] = 0
for i = 0 ... n - 1
    d[i] = 2000000000
for i in g[0] // python style
    d[i.first] = i.second
    q.add(pair(i.second, i.first))
for i = 1 ... n - 1
    v = -1
    while (v = -1) or (d[v] != val)
        v = q.top.second
        val = q.top.first
    q.removeTop
    mark[v] = true
    for i in g[v]
        if d[i.first] > d[v] + i.second
            d[i.first] = d[v] + i.second
            q.add(pair(d[i.first], i.first))
вывести d

Алгоритм Дейкстры. Поиск оптимальных маршрутов на графе / Хабр

Из многих алгоритмов поиска кратчайших маршрутов на графе, на Хабре я нашел только описание алгоритма Флойда-Уоршалла. Этот алгоритм находит кратчайшие пути между всеми вершинами графа и их длину. В этой статье я опишу принцип работы алгоритма Дейкстры, который находит оптимальные маршруты и их длину между одной конкретной вершиной (источником) и всеми остальными вершинами графа. Недостаток данного алгоритма в том, что он будет некорректно работать если граф имеет дуги отрицательного веса.

Для примера возьмем такой ориентированный граф G:

Этот граф мы можем представить в виде матрицы С:

Возьмем в качестве источника вершину 1. Это значит что мы будем искать кратчайшие маршруты из вершины 1 в вершины 2, 3, 4 и 5.

Данный алгоритм пошагово перебирает все вершины графа и назначает им метки, которые являются известным минимальным расстоянием от вершины источника до конкретной вершины. Рассмотрим этот алгоритм на примере.

Присвоим 1-й вершине метку равную 0, потому как эта вершина — источник. Остальным вершинам присвоим метки равные бесконечности.

Далее выберем такую вершину W, которая имеет минимальную метку (сейчас это вершина 1) и рассмотрим все вершины в которые из вершины W есть путь, не содержащий вершин посредников. Каждой из рассмотренных вершин назначим метку равную сумме метки W и длинны пути из W в рассматриваемую вершину, но только в том случае, если полученная сумма будет меньше предыдущего значения метки. Если же сумма не будет меньше, то оставляем предыдущую метку без изменений.

После того как мы рассмотрели все вершины, в которые есть прямой путь из W, вершину W мы отмечаем как посещённую, и выбираем из ещё не посещенных такую, которая имеет минимальное значение метки, она и будет следующей вершиной W. В данном случае это вершина 2 или 5. Если есть несколько вершин с одинаковыми метками, то не имеет значения какую из них мы выберем как W.

Мы выберем вершину 2. Но из нее нет ни одного исходящего пути, поэтому мы сразу отмечаем эту вершину как посещенную и переходим к следующей вершине с минимальной меткой. На этот раз только вершина 5 имеет минимальную метку. Рассмотрим все вершины в которые есть прямые пути из 5, но которые ещё не помечены как посещенные. Снова находим сумму метки вершины W и веса ребра из W в текущую вершину, и если эта сумма будет меньше предыдущей метки, то заменяем значение метки на полученную сумму.

Исходя из картинки мы можем увидеть, что метки 3-ей и 4-ой вершин стали меньше, тоесть был найден более короткий маршрут в эти вершины из вершины источника. Далее отмечаем 5-ю вершину как посещенную и выбираем следующую вершину, которая имеет минимальную метку. Повторяем все перечисленные выше действия до тех пор, пока есть непосещенные вершины.

Выполнив все действия получим такой результат:

Также есть вектор Р, исходя из которого можно построить кратчайшие маршруты. По количеству элементов этот вектор равен количеству вершин в графе, Каждый элемент содержит последнюю промежуточную вершину на кратчайшем пути между вершиной-источником и конечной вершиной. В начале алгоритма все элементы вектора Р равны вершине источнику (в нашем случае Р = {1, 1, 1, 1, 1}). Далее на этапе пересчета значения метки для рассматриваемой вершины, в случае если метка рассматриваемой вершины меняется на меньшую, в массив Р мы записываем значение текущей вершины W. Например: у 3-ей вершины была метка со значением «30», при W=1. Далее при W=5, метка 3-ей вершины изменилась на «20», следовательно мы запишем значение в вектор Р — Р[3]=5. Также при W=5 изменилось значение метки у 4-й вершины (было «50», стало «40»), значит нужно присвоить 4-му элементу вектора Р значение W — P[4]=5. В результате получим вектор Р = {1, 1, 5, 5, 1}.

Зная что в каждом элементе вектора Р записана последняя промежуточная вершина на пути между источником и конечной вершиной, мы можем получить и сам кратчайший маршрут.

Как найти путь к файлу, который запускает программу. Урок 29

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

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

Существует несколько способов определения пути к файлу или папке программы. Сейчас мы их рассмотрим.

Находим путь к файлу или папке по ярлыку на рабочем столе

Это самый легкий и быстрый способ. Если ярлык программы находится на рабочем столе, то кликаем по нему правой кнопкой мыши и выбираем в самом низу выпадающего списка, который называется контекстным меню, пункт «Свойства».

В открывшемся окне «Свойства» в поле «Объект» вы увидите путь к запускающему файлу программы (с расширением .exe), а ниже, в поле «Рабочая папка»  показан путь к папке программы.

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

Как узнать путь, если ярлыка программы нет на рабочем столе

Если ярлыка программы нет на рабочем столе, то он наверняка имеется в меню «Пуск».  В Windows XP или Windows 7 можно так же кликнуть по значку программы правой кнопкой мыши и выбрать в контекстном меню пункт «Свойства».

А вот в Windows 10 такой номер не прокатит. Там надо сначала открыть меню «Пуск» найти папку программы, открыть её, кликнуть правой кнопкой мыши по иконке программы, выбрать в самом верху открывшегося списка по строке «Дополнительно», а в следующем списке кликнуть по строке «Перейти к расположению файла».

В открывшемся окне программы наверху в адресной строке будет показан путь к этому файлу.

Его можно скопировать. Для этого необходимо кликнуть правой кнопкой мыши по адресу и выбрать в выпадающем меню пункт  «Копировать адрес».

Потом можно открыть любой текстовый редактор (блокнот или ворд) и вставить этот адрес в него , кликнув правой кнопкой мыши по пустому месту и выбрать вставить, или установить курсор и нажать на клавиатуре одновременно клавиши Ctrl + V

Эти методы особенно актуальны, если у вас нет доступа к скрытым файлам и папкам.

_____________________________________________________________________________________________________

Понравилась статья — нажмите на кнопки:

Как найти свой путь? или 5 шагов правильного пути

Есть такой тип характера людей, который возникает в современной культуре. Я их называю “бесхарактерный” тип. То есть это те люди, которые подверглись определенному давлению по жизни.

Что происходит с теми, кто теряет себя и свои желания? В процессе взросления дети, которые долгое время подвергались давлению взрослых, в последствии не знают, чем хотят заниматься, очень страдают и не видят цели в жизни. Основные свои усилия эти дети направляют на поиски своего “Я”, но так как границы размытые и нет четкой ясности, приходит ощущение тумана.

Единственное, что остаётся, пробираться через дебри и прилагать огромные усилия для пробуждения спящего сознания.

Чужое место

Бог обращается к человеку шепотом Любви, а если он не услышан — то голосом Совести. Если человек не слышит голоса совести — то Бог обращается через рупор страданий.
Клайв Льюис

Можно достигнуть успеха и при этом не испытывать счастье. Успех, сделанный не по своей природе, будет вынуждать компенсировать неудовлетворенность. Следовательно, всё что не естественно, требует сверх усилий.

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

Своё место

Блаженство заразительно, как любая болезнь. Если ты помогаешь другим быть счастливыми, по большому счету ты помогаешь быть счастливым самому себе.
Ошо

Древние ведические тексты говорят, что лучше несовершенно делать свои обязанности и быть счастливым, чем блестяще чужие. Почему? Потому что делать то, что не соответствует природе, опасно и разрушает.

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

Интересная работа начинается тогда, когда человек вкладывает элемент творчества и энтузиазма в любое дело. Энтузиазм — это своего рода божественное призвание. Важно принять это призвание и двигаться в этом потоке, тогда и наступит безграничное счастье. Но это уже удел целеустремленных людей.

Внутри нас есть инструкция по применению — это та самая карта, которая поможет нам не сбиться с пути, ориентиры к этой карте — эмоции.

Раскрывайте себя, экспериментируйте, пробуйте что-то новое в жизни. Вы всегда больше того, что вы о себе знаете!

Есть 5 шагов, которые стоит делать регулярно, для того чтобы найти свой путь

Шаг 1. Молитва

Обращайтесь за помощью к высшему началу, с просьбой понять свое значение. Задавайте в небо правильный вопрос: Какую роль я должен исполнить? Какая моя уникальность? Какое мое место в этом мире?

Неправильный вопрос: Какую профессию выбрать? Какая моя деятельность?

Шаг 2. Чистота

Предназначение родится в чистом сознании, которое беспристрастно и не осквернено. Чистая пища и деятельность по душе пробуждает осмысление себя.

Шаг 3. Активный поиск

Исходя из того, что мы постоянно развиваемся и наш потенциал обновляется, наша ответственность — постоянно искать истину. Мысль, которая поможет зацепиться: “Я точно хочу продолжать это делать?”

Страхи: “А вдруг мне это не понравится? А если я не захочу это сделать?” Страх — это защитная реакция, пока что не от чего защищать. Скажите ему, пусть подождёт. Когда найдёте своё, уже не будет дороги назад и придется соответствовать.

Шаг 4. Доверять своим желаниям

Не сомневайтесь в желаниях. В вас уже заложен путь к реализации себя, и ваши желания укажут дорогу.

Шаг 5. Идти только своей дорогой

У каждого свой путь и определенная роль, от того не оглядывайтесь по сторонам. В мире все места заняты, кроме вашего, от того, смело шагайте занимать своё место!

Читайте также

Не пропускай самые интересные публикации для личностного роста.
Подписывайся на нас в той социальной сети, которую любишь больше всего: Instagram, Facebook, Telegram.

Как найти свой Путь?

Люди часто меня просят посмотреть их путь Души, их миссию на Земле. Конечно, эту информацию можно просто спросить, поговорив с Высшим Я человека, его Душой.

Но если человек не готов вступить на свой Путь, то эти знания ему ничего не дадут, это будет информация лишь для ума, чтобы он и дальше строил свой ограниченный план и волновался за то, что не всё получается так, как запланировано им, как он хотел.

Если бы мне три года назад сказали, что у меня появятся самые разнообразные способности и я буду вести свой сайт и помогать людям, то я бы ответила, что это просто невозможно — так я была далека. Моя жизнь изменилась на все 180 градусов, когда я стала жить Душой.

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

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

Я начинала разговаривать с тонкими мирами и принимать послания, когда ум говорил, что это невозможно, нельзя разговаривать с кем-то, у кого нет физического тела. Некоторые люди твердили, что я не имею право принимать послания, так как для этого должна быть специальная миссия, это может делать лишь избранник, а ты обычный и простой человек. Но все мы — Великие Избранники, каждый человек.

Я сама создала свой первый сайт, когда Душа позвала (это неумолкаемый тихий зов, как некий «зуд» внутри) делиться всем. Ум говорил, что невозможно создать сайт без навыков программирования, у тебя никогда этого не получится, но сайт появился и работал. Когда идёшь своим путём, то помощь летит со всех сторон. Главное — идти терпеливо и спокойно, не раздражаясь по мелочам, и всё обязательно придёт.

Душа так и живёт… Она свободна и легка, она просто делает то, что ей нравится больше всего, что её радует, не боясь провала и безгранично наслаждаясь самим моментом творения, даже не ожидая результата.

Путь Души человека на Земле всегда неповторим и невероятен, что ум никогда даже близко не может подойти и понять его суть, ум не может догадаться — зачем вы сюда пришли, для чего воплотились.

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

Бог — это великий Творец. Зачем ему создавать дубликаты, когда он может создать уникальность и неповторимость всего, вложить свою бесценную «изюминку» во всё? Он развивается и расширяется через нас — свои чудесные творения.

Все прекрасные творения Бога, как огромный «пазл», в котором все частички — это каждый из нас. И если не хватает хотя бы одного, то полная чудесная картина никогда не сложится, не будет полной красоты и великолепия творения.

Каждый из нас очень важен, так как является бесценным кусочком «пазла» Творца, он создаёт Единую картину жизни, очень увлекательный опыт для каждого из нас.

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

Каждый из нас пришёл, чтобы раскрыться в своём уникальном и неповторимом творчестве Души, каждый обладает своим чудесным Божественным потенциалом и мир каждый день ждёт этого раскрытия.

Каждый из нас пришёл, чтобы стать прекрасной и чудесной частью великого Творения, чтобы зажечься изнутри Светом Творца и стать его подобием на земле, проявить его в своих делах, творчестве Души.

И только от нас зависит: захотим ли мы стать этим Светом, захотим ли открыться изнутри, своим уникальным и неповторимым качествам, чтобы подарить Себя миру, стать Единым со всем.

Пока человек живёт лишь для себя, пока сравнивает себя с другими людьми, пока завидует чужому опыту, пока не верит в себя, как бесценную духовно одарённую частичку Творца, пока спрашивает у всех: как ему жить, правильно ли он делает и как ему поступить… — он никогда не станет Собой, не раскроется в своей уникальности, в бесценном творчестве своей Души.

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

Не нужно думать: какова ваша миссия, зачем вы воплотились на Земле, какой ваш путь Души и чем вы должны заниматься, чтобы принести всем наивысшее Великое Благо… Это всё — жизнь ограниченным умом!

Необходимо просто радоваться жизни, любить её и жить так, как просит ваше сердце, даже если ум, ваши близкие, все люди вокруг, весь мир скажет вам, что вы делаете всё не так. Они все позже увидят и почувствуют ваш уникальный путь. Путеводная звезда всегда внутри!

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

Сердце всегда ведёт спокойно и легко, тихо и ласково… Оно зовёт делать то, что доставляет наивысшую радость и счастье. Сердце не нацелено на результат, а наслаждается самим творчеством, самой жизнью, самим бытием.

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

Именно они, в итоге, неожиданно приводят нас к полному проявлению Бога на земле, к великому Творению, к важному и нужному Пути, к жизни во благо всех…

Живите сердцем, чувствуйте его ведение внутри, доверяйте ему, так как именно через него с нами разговаривает наша Душа, Бог внутри нас.

Желаю всем почувствовать свой путь и найти своё уникальное и неповторимое предназначение!

С любовью,

Магда.

M* — алгоритм поиска кратчайшего пути, через весь мир, на смартфоне

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

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

Итак, наша задача — построение кратчайшего пути по графу из точки в точку. При этом граф достаточно велик, чтобы мы не имели возможности держать его целиком в памяти, а также невозможен предрасчет по сколь-нибудь значительному количеству вершин. Отличный образец — дорожный граф OSM. На данный момент число вершин в OSM превысило 4.6 млрд, общее число объектов — 400 млн.

Понятно, что в таких условиях поиск более-менее протяженного маршрута чистым алгоритмом Дейкстры или Левита невозможен в силу того, что мы не располагаем количеством памяти, необходимым для хранения промежуточных данных.

Как поступает алгоритм Дейкстры?

1. Заносим в приоритетную очередь стартовую точку с нулевой стоимостью.
2. Пока в очереди что-то есть — пусть вершина V, для каждого исходящего ребра (E), которое мы до сих пор не просматривали:
   1. проверяем что это не искомое ребро, если да, то конец;
   2. подсчитываем стоимость прохода E;
   3. и заносим конечную вершину ребра E в очередь со стоимостью её достижения — стоимость достижения V + стоимость E.

В результате для разреженных (например, геометрических) графов получаем стоимость O(n*log(n) + m*log(n)), где n-число просмотренных вершин, m-число просмотренных ребер.

Фиг.1 Здесь мы видим найденный маршрут и просмотренные при этом ребра.

Проблема в том, что алгоритм Дейкстры не использует никакой информации о свойствах графа и искомого маршрута и при его работе (распространении т.н. «волны») периметр этой «волны» движется от искомой точки во всех направлениях без какой-либо дискриминации.

С другой стороны, на геометрических графах, например, развитой дорожной сети, есть смысл стимулировать распространение «волны» по направлению к цели и штрафовать за остальные направления. Эта идея реализована в алгоритме A*, который является обобщением алгоритма Дейкстры.

В A* стоимость вершины при помещении её в приоритетную очередь не просто равна пройденному пути, а включает еще и оценку пути оставшегося. Как нам получить эту оценку?

Стоит отметить, что это должны быть достаточно вычислительно-дешевая оценка т.к. выполняется она большое число раз. Первое что приходит в голову — вычислить геометрическое расстояние от текущей точки до финиша и исходить из этого, например: осталось 10 км — средняя скорость при движении по городу 20 км/ч, значит наша оценка — полчаса.

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

Для ребер, ведущих от цели, эта оценка станет расти, в результате такие точки попадут в очередь с большим весом и вполне вероятно, что до них дело так и не дойдёт.

Примерно такого же эффекта можно достичь, кстати, с помощью техники Beam Search, где принудительно ограничивается размер приоритетной очереди и «недостойные» с точки зрения эвристики кандидаты просто отбрасываются.

Фиг.2 Здесь мы видим поиск того же маршрута с использованием описанной эвристики, почувствуйте разницу.

A* превращается в алгоритм Дейкстры если оценка стоимости возвращает 0, как если бы мы считали, что остаток пути промчимся с бесконечной скоростью.

A* относится т.н. информированным алгоритмам т.к. в эвристике мы используем предположение, что движение в направлении цели скорее приведёт нас к успеху.

Каковы должны быть свойства функции оценки? Она должна быть правдоподобной. Как мы уже выяснили, слишком оптимистичная оценка сводит на нет наши попытки уменьшить просматриваемую часть графа. С другой стороны, слишком пессимистичная оценка заставит алгоритм построить путь строго по направлению, невзирая ни на что. Вряд ли это нас устроит.

Реалистичная оценка должна опираться на свойства графа а лучше на модель данных. Например, вычисляться из уровня загруженности дорог в это время суток и уровня транспортной связности графа. Например, в городе без рек хорошо работает Манхэттенское расстояние.

Но тут сразу возникает масса нюансов:

• Как определить что мы в городе? Это не так уж и дешево.
• А ничего, что большая часть городов построена на реках?
• В городе разные участки дорог могут быть загружены сильно по разному.
• А если мы должны проехать через множество городов и рек?

Можно использовать и разные эвристики в духе метода ветвей и границ:

1. Находим путь с очень пессимистичной эвристикой, из чего следует, что, предположительно, есть и более эффективные маршруты.
2. Теперь мы будем использовать стоимость найденного маршрута как оценку сверху, просто не включая в приоритетную очередь претендентов, которые заведомо не могут дать нам маршрут более эффективный, чем уже найденный.
3. Делаем оценку менее пессимистичной и вновь строим маршрут с верхней границей стоимости.
4. Получаем новую оценку.
5. Продолжаем так до тех пор, пока не получим удовлетворительное решение.

Есть еще одна проблема с оценкой стоимости, о которой нельзя не упомянуть.

В жизни геометрически близкие объекты могут быть достаточно удаленными с точки зрения дорожного графа. Например, находиться на разных сторонах реки, горной гряды, моря… В таком случае оценка, основанная на геометрической близости начнёт усугублять ситуацию, упорно направляя «волну» в неправильном направлении.

Фиг.3 Вот так выглядит просмотренная A* часть графа OSM для поиска пути из Италии в Албанию.

Впрочем, это всё равно лучше чем алгоритмом Дейкстры. Хорошо видно как заполнив всю Италию, «волна» начала переливаться через край, набрала скорость и быстро достигла цели.

Фиг.4 А вот так выглядит просмотренная часть графа для алгоритма Дейкстры. По сравнению с ней всё не так уж и мрачно.

А можно ли еще как-то улучшить алгоритм, что по этому поводу говорит Сomputer Sience?

Двунаправленный поиск

Можно пустить две A* волны навстречу друг другу. Это называется bidirectional search и на первый взгляд кажется очень привлекательной идеей. В самом деле, при хорошей транспортной связности “волна” представляет собой эллипсоид, две малых волны, пущенные навстречу, заметут меньшую площадь по сравнению с одной большой. С другой стороны, возникает проблема обнаружения встречи «волн», точек в их периметрах может быть довольно много и проверять на каждом шагу наличие ребра в чужом периметре не так уж и дешево.

Фиг.5 встречные волны Дейкстры

Возможно, с этим можно было бы и смириться при реальном выигрыше в объеме просмотренной части графа. Но вот если мы рассмотрим вышеописанный пример поиска проезда из Италии в Албанию, то обнаружим, что двунаправленный поиск нам ничем не поможет, а только усугубит ситуацию т.к. кроме заливки всей Италии мы вынуждены будем просмотреть и всю Грецию с половиной Балкан, прежде чем волны встретятся. Ибо вместо одной «волны», упёршейся в препятствие, будем иметь две таковых.

Иерархические подходы

Использование иерархии дорог

Некоторые коммерческие системы, например StreetMap USA, используют для роутинга тот факт, что хорошо спланированная дорожная сеть имеет двухуровневую природу — есть сеть местных дорог и (значительно меньшая) сеть шоссе для поездок на дальние расстояния. Представляется естественным использовать этот факт. Вводятся шлюзы (transit nodes) — вершины, на которых происходит переход из одного уровня в другой. Нахождение “достаточно длинного” пути сводится к нахождению путей от:

• исходной точки до нескольких ближайших шлюзов;
• нескольких ближайших шлюзов до финальной точки;
• кратчайшего маршрута от любого из начальных шлюзов до любого из финальных, это, конечно, делается за один сеанс.

Фиг.6 Кусочек StreetMap

Выгоды такого подхода очевидны. Минусы таковы:

• Не везде дорожная сеть хорошо спланирована, кое-где она выросла стихийно, следовательно, исходный посыл не работает.
• Верхнеуровневая сеть должна быть связной и выверенной. Из OSM, например, невозможно получить такую сеть (лёгким движением руки) просто отфильтровав дороги по классам.
• Институт шлюзов также требует много ручной работы.

Построение иерархии графа

Если нет возможности и/или желания выверять граф, остаётся возможность построить иерархию автоматически.

Так или иначе, эксплуатируется идея, что хоть граф и не выверен, тем не менее, атрибуты рёбер позволяют строить маршруты приемлемого качества. Но в силу размеров графа, построение тем же A* в рабочем режиме непозволительно дорого.

Например, это может выглядеть так:

• на этапе предрасчета выбирается множество (пусть даже случайных) вершин;
• для пар пространственно удаленных вершин обычным A* строятся кратчайшие маршруты;
• на основе построенных маршрутов ведётся статистика пройденных рёбер;
• после того, как набралось достаточное количество данных, посещенные рёбра объявляются следующим уровнем иерархии;
• последовательно идущие рёбра без ветвлений сливаются в «макрорёбра» с сохранением стоимости проезда;

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

Маршрутизация в таком иерархическом графе осуществляется двунаправленным поиском (A* или алгоритмом Дейкстры).

Сепараторы

Основной идеей метода является попытка разделения графа на компоненты путём удаления небольшой части ребер — сепараторов. Эти сепараторы и предварительно вычисленные пути между ними образуют следующую иерархию. Утверждается [1], что затратив O(n*log(n)**3) времени и пространства на диске для предварительного расчета, можно выполнять запросы за O(sqrt(n)*log(n))

Grid Based Transit Nodes

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

Таблицы расстояний

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

Фиг.7 [1]

Reach [3]

Идея метода такова — замечено, что при построении длинных оптимальных маршрутов, «локальные» рёбра посещаются только в самом начале или конце маршрута. Следовательно, построив некоторое количество «обучающих» длинных маршрутов, можно понять, насколько близко расположено то или иное ребро к любому из концов маршрута.

Для некоторого обучающего маршрута P(s…..u.v……t) вводится показатель reach — минимальное расстояние до концов reach(uv) = min(dist(s…..u), dist(v…..t)).

На всём обучающем множестве reach(uv) — максимальное значение на всех маршрутах, где встретилось ребро (uv).

При «боевом» поиске мы вдали от старта и финиша просто будем стараться избегать рёбер с маленьким значением reach.

Фиг.8 [21]

Идея метода очень красивая, вопросы вызывает лишь качество обучающей выборки, её достаточность и ресурсы, потраченные на обучение.

Целеустремленные алгоритмы

Arc-Flags [4]

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

Таким образом для каждого ребра мы храним маску флагов, в какие фрагменты графа можно через это ребро добраться кратчайшим путём.

Специфические недостатки этого метода видны невооруженным взглядом:

• Количество фрагментов графа не может быть велико, 8К фрагментов (что не так уж и много) дадут нам (предположительно несжимаемый) килобайт на каждое ребро. Sic!
• Надо быть очень осторожным с нарезкой фрагментов, внутри фрагмента граф должен быть связным.

ALT [5]

Из всех вершин выбирается небольшое количество landmarks: λ. В изначальном варианте для каждой вершины предварительно рассчитывались стоимости до каждого λ. Это требовало колоссального количества дополнительной памяти и в дальнейшем требования смягчились и вершины стали группировать.

Поиск в ALT осуществляется как в A*, но оценка оставшегося пути делается на основе рассчитанных стоимостей. Пусть мы рассматриваем ребро (u,v) на пути к целевой вершине t. Для каждой λ в соответствии с неравенством треугольника мы имеем оценку оставшейся части пути (через λ): dist(λ, t) − dist(λ, v) ≤ dist(v, t) и dist(v, λ) − dist(t, λ) ≤ dist(v, t). Минимум для всех λ и даст искомую оценку.

Фиг.9

Предварительные итоги

Мы видим два основных направления, в которых идёт развитие:

1. Иерархии. Позволяют весьма эффективно строить пути на больших расстояниях в структурированных графах. Но на маленьких расстояниях дешевле пользоваться обычным A* или Дейкстрой. Следовательно существует “серая” область, где оба алгоритма работают посредственно.

   Кроме того, на аморфных графах попытка построить иерархию может лишь привести к проблемам. Представим себе граф в виде прямоугольной решетки из равнозначных дорог. При движении в некотором направлении правильным решением будет поворачивать в случайном направлении с вероятностью, связанной с направлением. Т.е. если азимут к цели составляет 45°, стоит с равной вероятностью поворачивать направо и налево, чтобы не создавать пробок.

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

2. Использование внутренней природы графа для принятия решения о направлении движения к цели. Идея выглядит многообещающей, но вызывает много вопросов. Основная проблема — человеческий фактор. Что lanmark’и, что фрагменты Arc-Flags требуют участия эксперта, если пустить их определение на самотёк, легко можно получить не то, что доктор прописал.

   Кроме того, требуется (нелинейное от размера графа) количество дополнительной памяти.

Вот «если бы губы Никанора Ивановича да приставить к носу Ивана Кузьмича, да взять сколь-нибудь развязности, какая у Балтазара Балтазаровича, да, пожалуй…» ©

Справедливости ради стоит сказать, что таких попыток немало, некоторые из них можно найти в списке источников данной статьи. Но мы, конечно же, не изменим себе и придумаем свой собственный, «не имеющий аналогов» метод. ️

Эвристика

Поставим задачу разработать простую и дешевую (и вычислительно и с точки зрения дополнительно хранимой информации) эвристику оценки стоимости пути из одной точки в другую на основе их географических координат. Прямое расстояние не подходит, оно может ошибаться весьма сильно, достаточно посмотреть на Гибралтар и Танжер.

Идея восходит к этой работе.

• Раз уж мы работаем с OSM, масштаб графа — вся планета.
• Разобьем пространство сеткой в 1°, да, это даёт искажения к полюсам, но мы ведь разрабатываем всего лишь оценку.
• При построении графа будем растеризовать пути на этой сетке, допустим, для 2-го переулка Крупской в Новосибирске мы должны пометить клеточку, соответствующую 55°с.ш. и 82°в.д.
• После растеризации всех известных нам дорог, получим карту населенности с точностью до градуса.

  Фиг.10 — число дорог на квадратный градус в логарифмической шкале

• Будем рассматривать нашу карту как граф, где населенные клеточки — вершины.
• Будем считать, что если соседние клеточки населены, то это ребро, из одной можно проехать в другую, стоимость прямого проезда — 111 км на экваторе, стоимость проезда наискосок умножается на корень из 2.
• Если в этом графе мы запустим волну в соответствии с алгоритмом Дейкстры, запоминая стоимость достижения каждой вершины, это даст нам оценку стоимости пути до финиша в любой достижимой точке. Например, если пустить волну из Новосибирска, это будет выглядеть так:

  Фиг.11 Оценка стоимости проезда из Нск, чем ближе к оранжевому, тем длинней путь.

Итак, для поиска:

• Мы храним только по биту на квадратный градус поверхности.
• Один раз запускаем волну по этой битовой карте для финальной точки.
• Для любой вершины в графе, зная её координаты, мы за константное время получаем оценку стоимости проезда от этой точки до финиша.

Но ведь градус — это довольно грубая сетка, некоторые проливы могут слипнуться, например, «маленький остров» с Нормандией.

Не беда, в OSM есть тип — береговая линия. Мы растеризуем береговые линии и разрешим ходить из клетки, помеченной как прибрежная, только на «материковые» клетки.

Фиг.12 Береговая линия OSM

Но тут выясняется, что:

• береговая линия есть не везде;
• Япония и др. целиком состоит из прибрежных клеток;
• Гибралтар и Танжер оказались в одной клетке;
• …

Ок, придется руками нарисовать разделительные линии в важных проливах, растеризовать их и запрещать пересекать при распространении волны.

Благо, это одноразовая работа, а таких проливов не очень много.

Вот, например, распространение «волны» из Италии, обратим внимание на Гибралтарский пролив.

Фиг.13 Оценка стоимости проезда в Италию, чем ближе к оранжевому, тем длиннее путь.

В целом схема приемлема, но:

1. она требует ручной работы;
2. ручной работы много;
3. надо быть очень осторожным, если на одну клетку легло несколько разделительных линий.

Возможно, здесь хорошо сработает вариант, когда каждая «прибрежная» клетка представлена квадро-деревом, распространение волны следует проводить и по элементам квадродерева.

Но всё же чувствуется во всём этом какая-то натяжка, поэтому в дело вступает План Б.

План Б.

1. Пусть мы имеем вышестоящий уровень иерархию графа, полученный, например, способом, описанным в разделе «построение иерархии графа».
2. Этот уровень достаточно груб для того, чтобы поиск на любые расстояния в нем не представлял проблем.
3. Итак, мы имеем на руках путь, построенный на более высоком уровне иерархии графа.

   Фиг.14 Путь, проложенный по верхнеуровневому графу.

4. Нанесем на этот маршрут опорные точки, например, через каждые 500 км, включая финиш, конечно

   Фиг.15 Опорные точки.

5. Для каждой опорной точки мы знаем остаток пути от неё до финиша. Теперь эвристика остатка пути для A* будет состоять из двух частей:
   1. геометрического расстояния до текущей опорной точки;
   2. остаток пути от текущей опорной точки до финиша.

6. В начале поиска текущей назначается первая опорная точка. Как только ма приближаемся к ней на геометрическое расстояние ближе чем 200 км (условно, конечно), начинаем ориентироваться на следующую опорную точку. И так до самого финиша.
7. Результат таков:

   Фиг. 11 Хорошо видно, как волна начинает расползаться вширь, когда опорный путь резко меняет направление. Тем не менее, общий объем прочитанных данных весьма невелик. Наблюдается также ускорение в ~20 раз.

8. Больше всего эта техника напоминает изображение из шапки к данной статье. Поэтому автор и дал ей название M* («M» значит «морковка»).

Выводы

Итак, на суд читателя представлены два варианта эвристики подсчета стоимости остатка пути для A*.

Для обоих вариантов:

• проверена их работоспособность на практике;
• скорость работы A* примерно одинакова, для указанного пути это 4.5 сек (рядовой десктоп) с чтением и распаковкой данных, 0.5 сек — только проход волны на разогретом кэше;
• количество дополнительно хранимой информации минимально — 0.2% для второго варианта, для первого еще меньше;
• т.к. A* работает с исходным графом, нет никаких препятствий к использованию временных ограничений, например, паромов, разводных мостов, данных о пробках…

Как бы то ни было, это еще один инструмент для работы с графами, весьма полезный в условиях ограниченных ресурсов и/или неограниченных данных. В частности, никто не запрещает использовать эту же технику для двустороннего поиска.Источники[1] Robust, Almost Constant Time Shortest-Path Queries in Road Networks⋆

Peter Sanders and Dominik Schultes

[2] Combining Hierarchical and Goal-Directed Speed-Up Techniques for Dijkstra’s Algorithm

Reinhard Bauer, Daniel Delling, Peter Sanders, Dennis Schieferdecker, Dominik Schultes, and Dorothea Wagner

[3] R. J. Gutman. Reach-Based Routing: A New Approach to Shortest Path Algorithms Optimized for Road Networks. In Proceedings of the 6th Workshop on Algorithm Engineering, 2004

[4] E. Köhler, R. H. Möhring, and H. Schilling. Acceleration of Shortest Path and Constrained

Shortest Path Computation. In Proceedings of the 4th Workshop on Experimental Algorithms

(WEA’05), Lecture Notes in Computer Science, pages 126–138. Springer, 2005.

[5] Goldberg, A.V., Werneck, R.F.: Computing Point-to-Point Shortest Paths from External Memory. In: Proceedings of the 7th Workshop on Algorithm Engineering and Experiments (ALENEX 2005), pp. 26–40. SIAM (2005)

[6] Defining and Computing Alternative Routes in Road Networks

Jonathan Dees, Robert Geisberger, and Peter Sanders

[7] Alternative Routes in Road Networks

Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck

[8] Partitioning Graphs to Speedup Dijkstra’s Algorithm

ROLF H. MOHRING and HEIKO SCHILLING

[9] SHARC: Fast and Robust Unidirectional Routing

Reinhard Bauer Daniel Delling

[10] Cambridge Vehicle Information Technology Ltd. Choice Routing

[11] Combining Hierarchical and Goal-Directed Speed-Up Techniques for Dijkstra’s Algorithm?

Reinhard Bauer, Daniel Delling, Peter Sanders, Dennis Schieferdecker, Dominik Schultes, and Dorothea Wagner

[12] Fast and Exact Shortest Path Queries Using Highway Hierarchies

Dominik Schultes

[13] Engineering Highway Hierarchies

Peter Sanders and Dominik Schultes

[14] Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks

Robert Geisberger, Peter Sanders, Dominik Schultes, and Daniel Delling

[15] Dynamic Highway-Node Routing

Dominik Schultes and Peter Sanders

[16] A FAST AND HIGH QUALITY MULTILEVEL SCHEME FOR PARTITIONING IRREGULAR GRAPHS

GEORGE KARYPIS AND VIPIN KUMAR

[17] Multilevel Algorithms for Partitioning Power-Law Graphs

Amine Abou-rjeili and George Karypis

[18] Impact of Shortcuts on Speedup Techniques?

Reinhard Bauer, Daniel Delling, and Dorothea Wagner

[19] Transit Node Routing based on Highway Hierarchies

Peter Sanders Dominik Schultes

[20] In Transit to Constant Time Shortest-Path Queries in Road Networks∗

Holger Bast Stefan Funke Domagoj Matijevic Peter Sanders Dominik Schultes

[21] Reach for A∗: an Efficient Point-to-Point Shortest Path Algorithm Andrew V. Goldberg

PS: статья по результатам доклада на DUMP 2017

Найди путь — Идиомы по бесплатному словарю

Как понимание того, как разные породы собак связаны через их ДНК, может помочь ученым найти способы улучшить здоровье собак? Как говорит Майерник, иногда вам нужно найти способы отвлечься от боли — «этого тендинита, который есть у всех девочек. такая же лодыжка от бега по кругу «Снежный» в течение 40 выступлений подряд ». Однако она клянется, что каждый год «Щелкунчик» проходит через ее любимый рождественский альбом Мэрайи Кэри.Необходимо стратегическое планирование, чтобы лучше понять, почему это так, и найти способы решения этой проблемы. Это достигается с помощью профилей ученых, инженеров и академиков, которые находят способы предотвратить опасность с помощью различных методов. Комиссия была создана архиепископом Роуэном. Уильямс, чтобы найти способы поддерживать «максимально возможную степень общения» в англиканском сообществе, которое состоит из 38 самоуправляющихся провинций в 164 странах. Он заявил о готовности найти способы использовать все переработанные материалы, включая переработанный бетон в качестве roadbase, и продемонстрировала готовность прислушиваться к новым идеям и находить способы правильно использовать переработанные продукты в дорожных работах.Хутслар показывает, как найти способы понять эти трудности и извлечь из них пользу. Но почему бы не проявить осторожность и не попытаться найти способы прервать беременность наиболее гуманными способами, возможными как для женщины, так и для плода? Она работает с немотивированными, Предприниматели, учителя, медицинские работники, правительственные бюрократы и владельцы малого бизнеса, находящиеся в состоянии стресса или перенапрягаемые на работе, должны найти способы поднять моральный дух, повысить производительность и вернуть немного удовольствия в свою профессиональную жизнь. Исправление этих заблуждений — цель группы. американских преподавателей, которые обратились прямо к источнику, чтобы собрать больше информации о Ближнем Востоке и найти способы включить эту информацию в свое обучение.Часть четвертая, «Обозначая общий курс», ставит перед нашим обществом и управляющими государственными землями задачу найти способы уважать потребности племен, уважая при этом потребности устоявшихся религий, путем управления священными местами для «взаимного согласования межкультурных различий». Они преподавали общественные науки и геометрию и по-прежнему удалось найти способы удержать мимолетное внимание студентов в классе. Поэтому боливийцы — а также бразильцы и аргентинцы — звонят в чилийский порт Арика, чтобы найти способы, чтобы на их товарах было проставлено клеймо «Сделано в Чили».»Мы призываем все церкви, приходы, общины и людей доброй воли найти способы и средства разоблачения и искоренения антисемитизма внутри и в канадском обществе. Но он должен был найти способы сделать это, чтобы непредсказуемые вспышки гомофобии не могли не возникнуть. навредить этим причинам.
.

Как найти Млечный Путь ночью (Путеводитель фотографов)

Один из самых популярных видов ночной фотографии — съемка ночного неба. Сфотографируя яркие звезды, образующие Млечный Путь, вы действительно сможете создать потрясающие фотографии. Но это не всегда просто. Если вы не знаете, как это сделать, поиск Млечного Пути может показаться сложной задачей.

Существует множество заблуждений о том, как найти Млечный Путь в ночном небе.Этот пост призван прояснить это. Читайте дальше, чтобы узнать, как найти Млечный Путь на самом деле намного проще, чем вы думаете!

Где находится Млечный Путь в ночном небе?

Млечный Путь — это галактика, в которой находится Солнечная система. Куда бы мы ни посмотрели, Млечный Путь. Вверх, вниз, влево, вправо — это Млечный Путь.

С Земли его можно увидеть как ‘туманную полосу света, видимую в ночном небе, образованную из звезд, которые невозможно различить невооруженным глазом.’

Вы можете видеть Млечный Путь круглый год, независимо от того, где вы находитесь. Он виден, пока небо чистое и световое загрязнение минимально. Однако кажется, что Млечный Путь движется по небу, когда вращается Земля.

Посмотрите на это изображение ниже, снятое примерно в час ночи:

.

Как представиться, чтобы вы остались незабываемыми (в хорошем смысле!) |

Алекс Жильбо

Если вы сможете выйти за рамки скучных основ, когда вас спросят: «Чем вы занимаетесь?», Вы настроите себя на новые отношения, возможности и открытия, — говорит эксперт по внедрению Джоанна Блур.

Общение на рабочем мероприятии неизбежно означает, что вам задают вопрос: «Чем вы занимаетесь?» снова и снова. После многих лет повторений и условностей большинство из нас отвечает: «Я занимаю должность X в компании Y.И хотя люди ожидают этого ответа, он также может задержаться в сознании вашего нового знакомого только до тех пор, пока не будет заменен тем, что ему скажет следующий человек.

«Отвечать своим титулом и компанией — это культурная норма. Но когда вы это делаете, вы упускаете возможность для другого человека узнать, кто вы на самом деле. Вы не только ваша работа », — говорит Джоанна Блур, генеральный директор Amplify Labs. Она специализируется на том, чтобы помогать людям открывать и формулировать то, что отличает их от других, чтобы они могли установить более глубокие связи с другими.

И все начинается с того, как вы представитесь.

Собственный ответ Блура демонстрирует силу оригинального ответа. Если она ответит: «Я генеральный директор Amplify Labs», ее собеседник, вероятно, продолжит спрашивать, каково быть генеральным директором или что такое Amplify Labs. Но такие разговоры на самом деле не позволяют человеку действительно узнать Блура. Поэтому, когда ее спрашивают: «Чем вы занимаетесь?», Она отвечает: «Нравится ли вам ваш собственный ответ на вопрос« Чем вы занимаетесь? »?» Люди неизменно признают, что нет.Затем она говорит: «Я знаю — все борются с этим, но ответ может иметь огромное влияние. Я работаю с людьми над созданием смелого, убедительного, аутентичного и уникального ответа. Я помогаю тебе рассказывать людям, почему ты такой классный ».

Представиться таким образом — это не просто выделиться в переполненной комнате или избавиться от постороннего жаргона и болтовни. Называя свой особый соус заранее, говорит Блур, вы увеличиваете шансы на то, что другой человек предложит возможность, отношения, бизнес или идею, которые могут вам помочь.Как говорит Блур: «Когда вы правильно представитесь, появится возможность не только по-настоящему общаться с людьми, но и вам будет позволено выполнять ту работу, которую вы действительно хотите делать».

Будьте осторожны: создание вступления требует времени и усилий. Но поскольку мир работы продолжает меняться, чего мы не можем предвидеть, важно знать, что отличает вас от стаи. Вот, Блур, расскажи нам, как ты можешь придумать свой новый ответ на «Чем ты занимаешься?»

1. Выходите за рамки своего титула.

Первое, что вам нужно сделать, это выяснить, кто вы на самом деле. Блур спрашивает своих клиентов: «Чем вы хотели бы прославиться?» Это неудобный вопрос, но она считает, что он выводит людей из зоны комфорта. Вместо того чтобы полагаться на предыдущие достижения, вы вынуждены думать о том, каким вы хотите добиться своего.

Блур применил ко мне эту тактику. Мой типичный ответ на вопрос «Чем вы занимаетесь?» «Я журналист и драматург». Но после того, как она спросила меня, что мне нравится в этих профессиях и чего я надеюсь достичь с их помощью, она помогла мне выработать гораздо более глубокий и убедительный ответ: «Мир может быть огромным местом, поэтому я помогаю людям общаться друг с другом, рассказывать истории как журналист как драматург.”

2. Подумайте о проблемах, которые можете решить только вы.

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

Используйте эту тактику на себе. Какие проблемы вы решаете на работе? И что делает вас особенно эффективным? Представление о себе как о решателе проблем может вызвать мгновенную реакцию, когда вы встречаетесь с кем-то новым.«У меня тоже есть эта проблема!» они могли сказать. Выясните, как выразить свои возможности в одном предложении. Например, вместо того, чтобы сказать: «Я юрист, специализирующийся на праве типа X», вы могли бы сказать: «Я думаю, что самая большая проблема в системе правосудия — это A. Как адвокат, специализирующийся на B, я помогаю найти решения, делая C. »

3. Попросите своих друзей и коллег внести свой вклад.

Людям часто трудно увидеть свои собственные навыки. «То, в чем вы хороши, может быть для вас таким же естественным, как дыхание, поэтому вы не цените это», — говорит Блур.Если вам сложно определить свои таланты, она предлагает вам обратиться к людям, которые хорошо вас знают, и спросить их: «В чем вы видите, что у меня все хорошо и что я не знаю, действительно особенного?» Как правило, в их ответах вы найдете общие темы или язык, говорит Блур, даже если это люди из разных областей вашей жизни.

4. Вернитесь в детство.

Все еще в тупике? Войдите в машину времени и вспомните себя восьмилетнего ребенка.Что у вас было лучше всего в этом возрасте? По словам Блура, этот особый навык может часто применяться к вам в настоящем и в будущем и помогать вам увидеть, чем вы отличаетесь от всех остальных. Например, когда Блур было восемь лет, у нее было отличное чувство направления и она легко запоминала маршруты во время походов с отцом. Этот навык перерос в ее предыдущую карьеру по созданию программного обеспечения для компаний — она ​​могла визуализировать трехмерные карты архитектуры программного обеспечения.

5. Покажи немного уязвимости.

Найти людей, с которыми мы общаемся, бывает трудно, особенно на рабочих мероприятиях. «Я думаю, что беспокойство на рабочем месте и беспокойство друг о друге вызвано тем, что мы не говорим о том, кто мы на самом деле как люди», — говорит Блур. Итак, рискните, откройтесь в своем вступительном слове и раскройте что-нибудь честное о себе. Используйте такие фразы, как «Я действительно увлечен X» или «Что меня больше всего волнует в том, что я делаю, — это Y», которые могут передать ваши эмоции и энтузиазм и побудить других ответить тем же.

6. Соберите отзывы о своем вступлении.

После того, как вы создадите открывалку, потренируйтесь в ней на пяти хорошо известных вам людях. Затем, через несколько дней, спросите их: «Что вам больше всего запомнилось из моего вступления?» Их ответ через несколько дней расскажет вам, что больше всего запомнилось в вашем открытии, что вы могли бы изменить и на что вы могли бы попытаться опереться при знакомстве с новыми людьми.

7. Во всем виноват кто-то другой.

Когда вы впервые начнете пробовать новый способ представиться, вы, вероятно, будете нервничать.Блур предлагает предварять это словами: «Я только что научился новому способу представления себя и экспериментирую с ним. Могу я попробовать это на тебе? » Люди любят, когда их просят дать совет или внести свой вклад.

8. Не возвращайтесь к старому вступлению.

По правде говоря, всегда будет легче сказать высокопарное «Я работаю X в компании Y», споткнуться в светской беседе, а затем перейти к следующему человеку и выпить бокал вина. Вдобавок, когда вы даете нетрадиционное представление, вы неизбежно столкнетесь с некоторыми уравновешенными людьми, которые его не поймут.

Но Блур призывает людей упорствовать. Недавно она тренировала женщину по имени Руми, стандартное вступление которой было «Я копирайтер». После того, как две женщины поработали вместе, Руми осознала, в чем ее секретная сила: в ее способности быть другим человеком в ее письме. Более того, процесс создания нового открывающего механизма заставил Руми понять, что «та часть меня, которой я стыжусь, будучи вечным аутсайдером, — это то самое место, откуда исходит моя пуленепробиваемая сила».

Как и Руми, вы можете обнаружить, что искреннее личное знакомство ведет к более глубоким откровениям в вашей жизни.«Мы все хотим узнать и понять, почему мы важны на этой планете и в этой жизни», — говорит Блур. «И это может начаться с того, что ты сможешь лучше ответить на вопрос« Что ты делаешь? »».

Смотрите выступление Джоанны Блур на TED здесь:

.

iCloud — Найди меня — Apple

Легко находите свои устройства.

Вы всегда носите свои устройства с собой. Значит, вы можете оставить их где угодно. Независимо от того, находятся ли они в конференц-зале или под подушкой дивана, скорее всего, они ненадолго потеряны. Приложение Find My поможет вам найти не только ваш iPhone, но и iPad, iPod touch, Mac, Apple Watch или AirPods.

Посмотрите все свои устройства на карте.

Ваш iPad дома или в офисе? Используйте карту, чтобы получить полное представление о том, где находятся ваши устройства и где они могут быть пропавшими.Некоторые устройства могут также отмечать свое местоположение при критически низком уровне заряда батареи, чтобы помочь вам найти их, даже если они разрядятся.

Включите звук, чтобы
найти свое устройство.

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

Перевести в режим пропажи.

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

Стирайте его с легкостью.

Обеспокоены тем, что ваше устройство попало в чужие руки? Вы можете удалить его удаленно, чтобы удалить свои личные данные и восстановить заводские настройки iPhone, iPad, iPod touch, Mac или Apple Watch. Если вы его восстановите, вы можете восстановить его из резервной копии iCloud.

Заблокировано. Автоматически.

Блокировка активации

предназначена для предотвращения использования или продажи вашего устройства другими лицами.Когда вы включаете «Найти меня» на своем устройстве, блокировка активации включается автоматически. Ваш Apple ID и пароль потребуются, прежде чем кто-либо сможет стереть данные с вашего устройства или повторно активировать его.

.