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

Задача поиска рандеву отличается от задачи исследования в том, что она рассматривает два поисковых инструмента, расположенных в разных вершинах графа, и стремится минимизировать время, необходимое для их встречи (рандеву) в одной вершине. В любое заданное время мобильные агенты занимают вершину графа и могут оставаться в ней либо перемещаться от вершины к вершине. Нашей задачей является минимизация времени, необходимого для рандеву. Естественным расширением задачи является исследование мобильных систем с несколькими агентами. Говоря в более общем контексте, пусть даны конкретная модель агентов и модель сети; мы говорим, что множество агентов, произвольным образом распределенных по вершинам сети, встречаются (организуют рандеву), если при выполнении своих программ по прошествии некоторого конечного времени все они занимают одну и ту же вершину сети в одно и то же время. Нас особо интересует высокосимметричный случай с анонимными агентами в анонимной сети, простейшим вариантом которого является случай с двумя агентами, стремящимися организовать рандеву в кольцевой сети. В частности, в модели, изучавшейся Савчуком [ ], агенты не могут различать вершины, вычисление выполняется посредством синхронных шагов, а ребра при каждой вершине имеют глобальную ориентацию. В таблице 2 приведены соотношения времени и памяти, известные для шести алгоритмов (см. Кранакис и др. [13], а также Флоччини и др. [ ]) в случае, когда k мобильных агентов используют неразличимые камни (по одному на каждого мобильного агента) для обозначения своей позиции в кольце, состоящем из n вершин.

Кранакис и др. [ ] продемонстрировали разительное отличие в особенностях вычислений рандеву в ориентированных, синхронных торах n x n при условии, что мобильные агенты имеют больше неразличимых маркеров. Они показали, что два агента с константным набором неперемещаемых маркеров (либо имеющие каждый по одному перемещаемому маркеру) не могут организовать рандеву, если имеют o(log n) памяти; они могут устроить рандеву с обнаружением, если имеют один неперемещаемый маркер и O(log n) памяти. Напротив, если каждый из двух агентов имеет два перемещаемых маркера, то организовать рандеву (соответственно, рандеву с обнаружением) возможно на торе с константным объемом памяти. Наконец, два агента, имеющие по три перемещаемых маркера и константный объем памяти, могут организовать рандеву с обнаружением на торе. Если отбросить условие синхронности, задача организации рандеву становится исключительно сложной. При заданном начальном положении агентов в графе Де Марко и др. [ ] измеряли эффективность алгоритма организации рандеву по количеству ребер, пройденных обоими агентами до собственно рандеву. Если вначале агенты располагаются на расстоянии D друг от друга на бесконечной прямой, стоимость алгоритма организации рандеву составляет O(D|Lmin|2), если D известно, и O((D + |Lmax|)3), если D неизвестно, где |Lmin| и |Lmax| – длины самой короткой и самой длинной меток агентов, соответственно. Этот результат верен и для случая кольца неизвестного размера. Авторы также предложили оптимальный алгоритм стоимостью O(n|Lmin|), если размер n кольца известен, и O(n|Lmax|) – если он неизвестен. Для произвольных графов они показали, что рандеву возможно в случае, если верхняя граница размера графа известна, и предложили оптимальный алгоритм стоимостью O(D|Lmin|), если топология графа и начальные положения известны агентам.