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

Перейти к навигации Перейти к поиску
Строка 38: Строка 38:
В этой формулировке предполагается, что агент может различать порты в вершине (локально), однако не предусматривается глобальной ориентации ребер и не имеется маркеров. Процесс ''исследования с остановкой'' завершается, когда мобильный агент обойдет все ребра и остановится на некоторой вершине. При ''исследовании с возвращением значения'' мобильный агент должен обойти все ребра и остановиться в начальной вершине. Если выполняется ''бессрочное исследование'', мобильный агент должен обойти все ребра дерева, но не обязательно должен остановиться. Верхняя и нижняя границы памяти исследовательских алгоритмов, проанализированные Диксом и др. [9], представлены в таблице. Они зависят от знаний, которыми обладает мобильный агент. Здесь n – количество вершин дерева, <math>N \ge n \;</math> – верхняя граница, известная мобильному агенту, а d – максимальная степень вершины дерева.
В этой формулировке предполагается, что агент может различать порты в вершине (локально), однако не предусматривается глобальной ориентации ребер и не имеется маркеров. Процесс ''исследования с остановкой'' завершается, когда мобильный агент обойдет все ребра и остановится на некоторой вершине. При ''исследовании с возвращением значения'' мобильный агент должен обойти все ребра и остановиться в начальной вершине. Если выполняется ''бессрочное исследование'', мобильный агент должен обойти все ребра дерева, но не обязательно должен остановиться. Верхняя и нижняя границы памяти исследовательских алгоритмов, проанализированные Диксом и др. [9], представлены в таблице. Они зависят от знаний, которыми обладает мобильный агент. Здесь n – количество вершин дерева, <math>N \ge n \;</math> – верхняя граница, известная мобильному агенту, а d – максимальная степень вершины дерева.


Таблица 1.


{| class="wikitable" style="text-align:center"
{| class="wikitable" style="text-align:center"
Строка 49: Строка 51:
| Без остановки
| Без остановки
| <math>n \le N</math>
| <math>n \le N</math>
| <math>\Omega (log \; log \; log n)</math>
| <math>\Omega (log \; log \; log \; n)</math>
| <math>O(log \; N)</math>
| <math>O(log \; N)</math>
|-
|-
Строка 57: Строка 59:
| <math>O (log^2 \; n)</math>
| <math>O (log^2 \; n)</math>
|}
|}
Таблица 1.




'''Исследование в геометрической формулировке'''
'''Исследование в геометрической формулировке'''


Исследование в геометрической формулировке с неизвестными плоскими и выпуклыми препятствиями осуществили Блюм и др. [5]. Они сравнивали расстояние, пройденное агентом (или роботом), с длиной кратчайшего пути, свободного от препятствий, в конкретной ситуации и описывали и анализировали стратегии деятельности робота, минимизировавшие это соотношение для различных типов ситуаций. Исследованию в более общей формулировке с препятствиями в виде полигонов и прямоугольников посвящены работы Денга и др. [7] и Бар-Али и др. [3], соответственно. Для исследования беспроводных сетей важна формулировка задачи, в которой вершины сети знают о своем местоположении. Для такого случая Кранакис и др. [12] предложили эффективные алгоритмы навигации, а именно маршрутизацию по циркулю и маршрутизацию по грани, которые гарантируют получение результата в графах Делоне и в произвольных планарных геометрических графах, соответственно, используя только локальную информацию.
Исследование в геометрической формулировке с неизвестными плоскими и выпуклыми препятствиями осуществили Блюм и др. [5]. Они сравнивали расстояние, пройденное агентом (или роботом), с длиной кратчайшего пути, свободного от препятствий, в конкретной ситуации и описывали и анализировали стратегии деятельности робота, минимизировавшие это соотношение для различных типов ситуаций. Исследованию в более общей формулировке с препятствиями в виде многоугольников и прямоугольников посвящены работы Денга и др. [7] и Бар-Али и др. [3], соответственно. Для исследования беспроводных сетей важна формулировка задачи, в которой вершины сети знают о своем местоположении. Для такого случая Кранакис и др. [12] предложили эффективные алгоритмы навигации, а именно маршрутизацию по циркулю и маршрутизацию по грани, которые гарантируют получение результата в графах Делоне и в произвольных планарных геометрических графах, соответственно, используя только локальную информацию.




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


Таблица 2.


{| class="wikitable" style="text-align:center"
{| class="wikitable" style="text-align:center"
Строка 90: Строка 91:
| O(n log k)
| O(n log k)
|}
|}
Таблица 2.




Источник — http://pco.iis.nsk.su/wega/index.php/Мобильные_агенты_и_исследования_с_их_помощью