4551
правка
Мобильные агенты и исследования с их помощью: различия между версиями
Перейти к навигации
Перейти к поиску
м
Мобильные агенты и исследования с их помощью (посмотреть исходный код)
Версия от 21:03, 28 октября 2016
, 28 октября 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 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> | ||
|} | |} | ||
'''Исследование в геометрической формулировке''' | '''Исследование в геометрической формулировке''' | ||
Исследование в геометрической формулировке с неизвестными плоскими и выпуклыми препятствиями осуществили Блюм и др. [5]. Они сравнивали расстояние, пройденное агентом (или роботом), с длиной кратчайшего пути, свободного от препятствий, в конкретной ситуации и описывали и анализировали стратегии деятельности робота, минимизировавшие это соотношение для различных типов ситуаций. Исследованию в более общей формулировке с препятствиями в виде | Исследование в геометрической формулировке с неизвестными плоскими и выпуклыми препятствиями осуществили Блюм и др. [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) | ||
|} | |} | ||