Если два человека теряются в лабиринте, есть алгоритм , который они оба могут использовать , чтобы найти друг друга , не будучи предварительно договорились , что алгоритм они будут использовать?
Я думаю, что у этого алгоритма есть некоторые характеристики:
- Каждый человек должен иметь возможность вывести его, используя логику, которая не делает никаких предположений о том, что решает другой человек, но, поскольку каждый человек знает, что другой находится в той же позиции, он может сделать выводы о том, что должен решать другой .
- Один и тот же алгоритм должен быть выведен обоими людьми, поскольку в их ситуациях существует полная симметрия (ни один из них не знает о начальной позиции другого, а лабиринт имеет фиксированный размер и полностью отображается обоими). Обратите внимание, что алгоритм не обязан быть детерминированным: его можно рандомизировать.
Ответы:
Это называется проблемой свиданий .
Как упоминалось в статье «Мобильный агент Рандеву: опрос» , эта проблема является оригинальной, предложенной Алперн: «Задача поиска Рандеву» :
В обзоре выше,
Он охватывает как «Асимметричное свидание» (в разделе 4), так и «Симметричное свидание» (в разделе 5).
Для симметричного рандеву статья Альперна показывает:
источник
На самом деле подойдет любая согласованная заранее подготовленная схема.
Например:
Или даже проще
Эта схема гарантирует, что люди встретятся в конечном итоге (но это может занять некоторое время)
Зачем? Потому что схема согласована для обоих и не ведет ни в тупик. Так как лабиринт конечен и связан, через конечное время они встретятся.
Если схема не согласована, нет гарантии, что они встретятся, так как они могут привести к замкнутым циклам.
Если они имеют одинаковую скорость, то в зависимости от архитектуры лабиринта, например, циклического лабиринта, возможно, что они всегда могут находиться в антидиаметрических точках лабиринта и, следовательно, никогда не встречаются, даже если схема последовательна.
Из вышесказанного ясно, что схема должна быть предварительно организована, но подойдет любая согласованная предварительно организованная схема.
В противном случае можно опираться на вероятностный анализ и сделать вывод, что с большой вероятностью они встретятся, но эта вероятность не одна (т.е. при всех случаях).
Можно также рассмотреть обратные от сближения проблемы , то проблема избегания , где целью является для агентов , чтобы всегда избегать друг друга .
Решение проблемы избегания состоит в том, чтобы агенты точно отражали друг друга. Это означает, что то, что один агент делает другому, должно отражать это. Поскольку проблема избегания также имеет решение , ясно, что стратегии для проблемы сближения, которые могут привести к отражающему поведению агентов, не могут гарантировать решение.
Можно сказать, что стратегией проблемы избегания является распараллеливание (т. Е. Максимальная точка расхождения), тогда как стратегией проблемы рандеву является ортогональность (т. Е. Наименьшая сходящаяся точка).
Приведенный выше анализ может быть превращен в рандомизированный алгоритм, который не принимает заранее подготовленные роли для агентов, например, следующий:
В среднем это приведет к тому, что люди в конечном итоге встретятся, но не гарантируется при всех случаях.
Если предположить, что агенты могут оставлять следы , например, метки их (текущего) направления и скорости. Затем другой агент может использовать эти следы в качестве информации для настройки как собственного направления, так и скорости (см. Ниже).
Проблема такого рода является примером глобальной оптимизации с использованием только локальной информации . Или, другими словами, способ сопоставить глобальные ограничения с локальными ограничениями . Эта, более общая проблема (которая включает проблему рандеву) рассматривается в этом посте math.se (и содержит ссылки на него) "Методы преобразования глобальных ограничений в локальные ограничения"
источник