4551
правка
Мобильные агенты и исследования с их помощью: различия между версиями
Перейти к навигации
Перейти к поиску
Мобильные агенты и исследования с их помощью (посмотреть исходный код)
Версия от 19:29, 5 октября 2016
, 5 октября 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 30: | Строка 30: | ||
'''Исследование в графах общего вида''' | '''Исследование в графах общего вида''' | ||
Сеть моделируется в виде графа, агент может перемещаться от вершины к вершине только по ребрам графа. Параметры графа могут задаваться двумя разными способами. В работе Денга и Пападимитриу [ ] агент исследует сильно связные ориентированные графы, перемещаясь только в направлении от начала к концу каждого ребра, но не наоборот. В любой момент времени у агента имеется карта всех посещенных вершин и ребер, и он способен распознать их, если попадет в них вновь. Алгоритм минимизирует отношение общего количества посещенных ребер к оптимальному количеству обходов, имеющему место в случае, если граф известен агенту. Панет и Пельц [ ] исследовали неориентированный граф, в котором агенты могли обходить ребра в обоих направлениях. В графовой формулировке задачи нередко требуется, чтобы помимо исследования агент строил карту графа, т.е. выводил его изоморфную копию. Исследование изоморфных графов, предполагающих наличие меток, выполнили Альберс и Хенцингер [ ], а также Денг и Пападимитриу [8]. В работе Панета и Пельца [ ] был представлен алгоритм исследования с временем работы e + O(n), где n – количество вершин, а e – количество связей. Фрейньо и др. [ ] изучали требования к памяти при исследовании неизвестных графов (неизвестного размера) с непомеченными вершинами и локально помеченными ребрами при каждой вершине. Для исследования всех графов диаметра D с максимальной степенью мобильному агенту необходимо Q(D\ogd) бит памяти в случае, если исследование ограничивается планарными графами. Некоторые исследователи также выполняют изучение анонимных графов, в которых агентам позволяется поднимать и бросать камни. Например, Бендер и др. [ ] показали, что для исследования достаточно одного камня, если агенту известна верхняя граница размера графа, и 0 (log log n) камней необходимо и достаточно в противном случае. | |||
'''Исследование на деревьях''' | |||