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

В этой формулировке предполагается, что агент может различать порты в вершине (локально), однако не предусматривается глобальной ориентации ребер и не имеется маркеров. Процесс исследования останавливается, когда мобильный агент обойдет все ребра и остановится на некоторой вершине. Если исследование должно вернуть значение, мобильный агент должен обойти все ребра и остановиться в начальной вершине. Если выполняется бессрочное исследование, мобильный агент должен обойти все ребра, но не обязательно должен остановиться. Верхняя и нижняя границы памяти исследовательских алгоритмов, проанализированные Диксом и др. [ ], представлены в таблице. Они зависят от знаний, которыми обладает мобильный агент. Здесь n – количество вершин дерева, N > n – верхняя граница, известная мобильному агенту, а d – максимальная степень вершины дерева.

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