Аноним

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

Материал из WEGA
м
 
(не показаны 2 промежуточные версии этого же участника)
Строка 93: Строка 93:




Кранакис и др. [14] продемонстрировали разительное отличие в особенностях вычислений рандеву в ориентированных, синхронных торах n x n при условии, что мобильные агенты могут иметь большее число неразличимых маркеров. Они показали, что два агента с константным набором неперемещаемых маркеров (либо имеющие каждый по одному перемещаемому маркеру) не могут организовать рандеву, если имеют o(log n) памяти; они могут устроить рандеву с обнаружением, если имеют один неперемещаемый маркер и O(log n) памяти. Напротив, если каждый из двух агентов имеет два перемещаемых маркера, то организовать рандеву (соответственно, рандеву с обнаружением) возможно на торе при наличии константного объема памяти. Наконец, два агента, имеющие по три перемещаемых маркера и константный объем памяти, могут организовать рандеву с обнаружением на торе. Если отбросить условие синхронности, задача организации рандеву становится исключительно сложной. Имея заданное начальное положение агентов в графе, Де Марко и др. [6] измеряли эффективность алгоритма организации рандеву по количеству ребер, пройденных обоими агентами до собственно рандеву. Если вначале агенты располагаются на расстоянии D друг от друга на бесконечной прямой, стоимость алгоритма организации рандеву составляет <math>O(D|L_{min}|^2) \;</math>, если D известно, и <math>O((D + |L_{max}|)^3) \;</math>, если D неизвестно, где <math>|L_{min}| \;</math> и <math>|L_{max}| \;</math> – длины самой короткой и самой длинной меток агентов, соответственно. Этот результат верен и для случая кольца неизвестного размера. Авторы также предложили оптимальный алгоритм стоимостью <math>O(n|L_{min}|) \;</math>, если размер n кольца известен, и <math>O(n|L_{max}|) \;</math> – если он неизвестен. Для произвольных графов они показали, что рандеву возможно в случае, если верхняя граница размера графа известна, и предложили оптимальный алгоритм стоимостью <math>O(D|L_{min}|) \;</math>, если топология графа и начальные положения известны агентам.
Кранакис и др. [14] продемонстрировали разительное отличие в особенностях вычислений рандеву в ориентированных, синхронных торах n x n при условии, что мобильные агенты могут иметь большее число неразличимых маркеров. Было показано, что два агента с константным набором неперемещаемых маркеров (либо имеющие каждый по одному перемещаемому маркеру) не могут организовать рандеву, если имеют o(log n) памяти; они могут устроить рандеву с обнаружением, если имеют один неперемещаемый маркер и O(log n) памяти. Напротив, если каждый из двух агентов имеет два перемещаемых маркера, то организовать рандеву (соответственно, рандеву с обнаружением) возможно на торе при наличии константного объема памяти. Наконец, два агента, имеющие по три перемещаемых маркера и константный объем памяти, могут организовать рандеву с обнаружением на торе. Если отбросить условие синхронности, задача организации рандеву становится исключительно сложной. Имея заданное начальное положение агентов в графе, Де Марко и др. [6] измеряли эффективность алгоритма организации рандеву по количеству ребер, пройденных обоими агентами до собственно рандеву. Если вначале агенты располагаются на расстоянии D друг от друга на бесконечной прямой, стоимость алгоритма организации рандеву составляет <math>O(D|L_{min}|^2) \;</math>, если D известно, и <math>O((D + |L_{max}|)^3) \;</math>, если D неизвестно, где <math>|L_{min}| \;</math> и <math>|L_{max}| \;</math> – длины самой короткой и самой длинной меток агентов, соответственно. Этот результат верен и для случая кольца неизвестного размера. Авторы также предложили оптимальный алгоритм стоимостью <math>O(n|L_{min}|) \;</math>, если размер n кольца известен, и <math>O(n|L_{max}|) \;</math> – если он неизвестен. Для произвольных графов они показали, что рандеву возможно в случае, если верхняя граница размера графа известна, и предложили оптимальный алгоритм стоимостью <math>O(D|L_{min}|) \;</math> для случая, когда топология графа и начальные положения известны агентам.


== Применение ==
== Применение ==
Интерес к использованию мобильных агентов был вызван двумя родственными задачами. Во-первых, они использовались для упрощения сложных аспектов распределенных вычислений, во-вторых – помогали обойти ограничения пользовательских интерфейсов. Сегодня они находят широкое применение в таких различных областях, как распределенное решение задач и планирование (например, разделение и координация заданий), обслуживание сетей (например, использование в качестве демонов в сетевых системах для выполнения таких задач, как мониторинг и наблюдение), электронная коммерция и поиск информации (например, добыча данных и роботы-сборщики, выполняющие поиск продуктов и услуг в разных источниках), исследования при помощи роботов (например, вездеходы и другие мобильные платформы, способные исследовать потенциально опасные среды и даже выполнять работы в открытом космосе), распределенное принятие рациональных решений (например, ведение протоколов аукционов или заключение сделок). Много полезной информации по данной теме можно найти в нескольких статьях тома под редакцией Вайса [18].
Интерес к использованию мобильных агентов был вызван двумя родственными задачами. Во-первых, они использовались для упрощения сложных аспектов распределенных вычислений, во-вторых – помогали обойти ограничения пользовательских интерфейсов. Сегодня они находят широкое применение в таких различных областях, как распределенное решение задач и планирование (например, разделение и координация заданий), обслуживание сетей (например, использование в качестве демонов в сетевых системах для выполнения таких задач, как мониторинг и наблюдение), электронная коммерция и поиск информации (например, добыча данных и роботы-сборщики, выполняющие поиск продуктов и услуг из нескольких источников), исследования при помощи роботов (например, вездеходы и другие мобильные платформы, способные исследовать потенциально опасные среды и даже выполнять работы в открытом космосе), распределенное принятие рациональных решений (например, ведение протоколов аукционов или заключение сделок). Много полезной информации по данной теме можно найти в нескольких статьях тома под редакцией Вайса [18].


== Открытые вопросы ==
== Открытые вопросы ==
Строка 102: Строка 102:


== См. также ==
== См. также ==
* ''[[Детерминистский поиск для линейной задачи]]
* ''[[Детерминированный алгоритм поиска на прямой]]
* ''[[Робототехника]]
* ''[[Робототехника]]
* ''[[Маршрутизация]]
* ''[[Маршрутизация]]


== Литература ==
== Литература ==
4430

правок