4551
правка
Мобильные агенты и исследования с их помощью: различия между версиями
Перейти к навигации
Перейти к поиску
Мобильные агенты и исследования с их помощью (посмотреть исходный код)
Версия от 12:28, 11 октября 2016
, 11 октября 2016→Основные результаты
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) |
||
| Строка 37: | Строка 37: | ||
В этой формулировке предполагается, что агент может различать порты в вершине (локально), однако не предусматривается глобальной ориентации ребер и не имеется маркеров. Процесс исследования останавливается, когда мобильный агент обойдет все ребра и остановится на некоторой вершине. Если исследование должно возвращать значение, мобильный агент должен обойти все ребра и остановиться в начальной вершине. Если выполняется бессрочное исследование, мобильный агент должен обойти все ребра дерева, но не обязательно должен остановиться. Верхняя и нижняя границы памяти исследовательских алгоритмов, проанализированные Диксом и др. [ ], представлены в таблице. Они зависят от знаний, которыми обладает мобильный агент. Здесь n – количество вершин дерева, N > n – верхняя граница, известная мобильному агенту, а d – максимальная степень вершины дерева. | В этой формулировке предполагается, что агент может различать порты в вершине (локально), однако не предусматривается глобальной ориентации ребер и не имеется маркеров. Процесс исследования останавливается, когда мобильный агент обойдет все ребра и остановится на некоторой вершине. Если исследование должно возвращать значение, мобильный агент должен обойти все ребра и остановиться в начальной вершине. Если выполняется бессрочное исследование, мобильный агент должен обойти все ребра дерева, но не обязательно должен остановиться. Верхняя и нижняя границы памяти исследовательских алгоритмов, проанализированные Диксом и др. [ ], представлены в таблице. Они зависят от знаний, которыми обладает мобильный агент. Здесь n – количество вершин дерева, N > n – верхняя граница, известная мобильному агенту, а d – максимальная степень вершины дерева. | ||
{| class="wikitable" style="text-align:center" | |||
! Исследование !! Знание !! Нижние границы !! Верхние границы | |||
|- | |||
| Бессрочное | |||
| <math>\empty</math> | |||
| Нет | |||
| <math>O(log \; d)</math> | |||
|- | |||
| Без остановки | |||
| <math>n \le N</math> | |||
| <math>\Omega (log \; log \; log n)</math> | |||
| <math>O(log \; N)</math> | |||
|- | |||
| С возвращением значения | |||
| <math>\empty</math> | |||
| <math>\Omega (log \; n)</math> | |||
| <math>O (log^2 \; n)</math> | |||
|} | |||