Аноним

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

Материал из WEGA

Мобильные агенты и исследования с их помощью (посмотреть исходный код)

Версия от 11:56, 11 октября 2016

22 байта добавлено ,  11 октября 2016
м
→‎Основные результаты
Строка 31: Строка 31:
'''Исследование в графах общего вида'''
'''Исследование в графах общего вида'''


Сеть моделируется в виде графа, агент может перемещаться от вершины к вершине только по ребрам графа. Параметры графа могут задаваться двумя разными способами. В работе Денга и Пападимитриу [ ] агент исследует сильно связные ориентированные графы, перемещаясь только в направлении от начала к концу каждого ребра, но не наоборот. В любой момент времени у агента имеется карта всех посещенных вершин и ребер, и он способен распознать их, если попадет в них вновь. Алгоритм минимизирует отношение общего количества посещенных ребер к оптимальному количеству обходов, имеющему место в случае, если граф известен агенту. Панет и Пельц [ ] исследовали неориентированный граф, в котором агенты могли обходить ребра в обоих направлениях. В графовой формулировке задачи нередко требуется, чтобы помимо исследования агент строил карту графа, т.е. выводил его изоморфную копию. Исследование изоморфных графов, предполагающих наличие меток, выполнили Альберс и Хенцингер [ ], а также Денг и Пападимитриу [8]. В работе Панета и Пельца [ ] был представлен алгоритм исследования с временем работы e + O(n), где n – количество вершин, а e – количество связей. Фрейньо и др. [ ] изучали требования к памяти при исследовании неизвестных графов (неизвестного размера) с непомеченными вершинами и локально помеченными ребрами при каждой вершине. Для исследования всех графов диаметра D с максимальной степенью мобильному агенту необходимо Q(D\ogd) бит памяти в случае, если исследование ограничивается планарными графами. Некоторые исследователи также выполняют изучение анонимных графов, в которых агентам позволяется поднимать и бросать камни. Например, Бендер и др. [ ] показали, что для исследования достаточно одного камня, если агенту известна верхняя граница размера графа, и 0 (log log n) камней необходимо и достаточно в противном случае.
Сеть моделируется в виде графа, агент может перемещаться от вершины к вершине только по ребрам графа. Графовая формулировка задачи может задаваться двумя разными способами. В работе Денга и Пападимитриу [ ] агент исследует сильно связные ориентированные графы, перемещаясь только в направлении от начала к концу каждого ребра, но не наоборот. В любой момент времени у агента имеется карта всех посещенных вершин и ребер, и он способен распознать их, если попадет в них вновь. Алгоритм минимизирует отношение общего количества посещенных ребер к оптимальному количеству обходов, имеющему место в случае, если граф известен агенту. Панет и Пельц [ ] исследовали неориентированный граф, в котором агенты могли обходить ребра в обоих направлениях. В графовой формулировке задачи нередко требуется, чтобы помимо исследования агент строил карту графа, т.е. выводил его изоморфную копию. Исследование изоморфных графов, предполагающих наличие меток, выполнили Альберс и Хенцингер [ ], а также Денг и Пападимитриу [8]. В работе Панета и Пельца [ ] был представлен алгоритм исследования с временем работы e + O(n), где n – количество вершин, а e – количество связей. Фрейньо и др. [ ] изучали требования к памяти при исследовании неизвестных графов (неизвестного размера) с непомеченными вершинами и локально помеченными ребрами при каждой вершине. Для исследования всех графов диаметра D с максимальной степенью d мобильному агенту необходимо Q(D\ogd) бит памяти в случае, если исследование ограничивается планарными графами. Некоторые исследователи также выполняют изучение анонимных графов, в которых агентам позволяется поднимать и бросать камни. Например, Бендер и др. [ ] показали, что для исследования достаточно одного камня, если агенту известна верхняя граница размера графа, в противном случае необходимо и достаточно O(log log n) камней.




Строка 54: Строка 54:


Кранакис и др. [ ] продемонстрировали разительное отличие в особенностях вычислений рандеву в ориентированных, синхронных торах n x n при условии, что мобильные агенты имеют больше неразличимых маркеров. Они показали, что два агента с константным набором неперемещаемых маркеров (либо имеющие каждый по одному перемещаемому маркеру) не могут организовать рандеву, если имеют o(log n) памяти; они могут устроить рандеву с обнаружением, если имеют один неперемещаемый маркер и O(log n) памяти. Напротив, если каждый из двух агентов имеет два перемещаемых маркера, то организовать рандеву (соответственно, рандеву с обнаружением) возможно на торе с константным объемом памяти. Наконец, два агента, имеющие по три перемещаемых маркера и константный объем памяти, могут организовать рандеву с обнаружением на торе. Если отбросить условие синхронности, задача организации рандеву становится исключительно сложной. При заданном начальном положении агентов в графе Де Марко и др. [ ] измеряли эффективность алгоритма организации рандеву по количеству ребер, пройденных обоими агентами до собственно рандеву. Если вначале агенты располагаются на расстоянии D друг от друга на бесконечной прямой, стоимость алгоритма организации рандеву составляет O(D|Lmin|2), если D известно, и O((D + |Lmax|)3), если D неизвестно, где |Lmin| и |Lmax| – длины самой короткой и самой длинной меток агентов, соответственно. Этот результат верен и для случая кольца неизвестного размера. Авторы также предложили оптимальный алгоритм стоимостью O(n|Lmin|), если размер n кольца известен, и O(n|Lmax|) – если он неизвестен. Для произвольных графов они показали, что рандеву возможно в случае, если верхняя граница размера графа известна, и предложили оптимальный алгоритм стоимостью O(D|Lmin|), если топология графа и начальные положения известны агентам.
Кранакис и др. [ ] продемонстрировали разительное отличие в особенностях вычислений рандеву в ориентированных, синхронных торах n x n при условии, что мобильные агенты имеют больше неразличимых маркеров. Они показали, что два агента с константным набором неперемещаемых маркеров (либо имеющие каждый по одному перемещаемому маркеру) не могут организовать рандеву, если имеют o(log n) памяти; они могут устроить рандеву с обнаружением, если имеют один неперемещаемый маркер и O(log n) памяти. Напротив, если каждый из двух агентов имеет два перемещаемых маркера, то организовать рандеву (соответственно, рандеву с обнаружением) возможно на торе с константным объемом памяти. Наконец, два агента, имеющие по три перемещаемых маркера и константный объем памяти, могут организовать рандеву с обнаружением на торе. Если отбросить условие синхронности, задача организации рандеву становится исключительно сложной. При заданном начальном положении агентов в графе Де Марко и др. [ ] измеряли эффективность алгоритма организации рандеву по количеству ребер, пройденных обоими агентами до собственно рандеву. Если вначале агенты располагаются на расстоянии D друг от друга на бесконечной прямой, стоимость алгоритма организации рандеву составляет O(D|Lmin|2), если D известно, и O((D + |Lmax|)3), если D неизвестно, где |Lmin| и |Lmax| – длины самой короткой и самой длинной меток агентов, соответственно. Этот результат верен и для случая кольца неизвестного размера. Авторы также предложили оптимальный алгоритм стоимостью O(n|Lmin|), если размер n кольца известен, и O(n|Lmax|) – если он неизвестен. Для произвольных графов они показали, что рандеву возможно в случае, если верхняя граница размера графа известна, и предложили оптимальный алгоритм стоимостью O(D|Lmin|), если топология графа и начальные положения известны агентам.


== Применение ==
== Применение ==
Irina
4430

правок

Источник — http://pco.iis.nsk.su/wega/index.php/Служебная:Сравнение_версий/11950