|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
Общий подход к решению задач на графах коллективом автоматов
И. Б. Бурдонов, А. С. Косачев Институт системного программирования РАН
Аннотация:
Предложен общий подход к решению задач на неориентированном упорядоченном корневом связном графе коллективом автоматов, расположенных в вершинах графа и обменивающихся сообщениями по рёбрам графа. Автоматы считаются полуроботами, т.е. размер их памяти может расти вместе с ростом числа $n$ вершин и числа $m$ рёбер графа, но описание графа может не помещаться в памяти автомата. В разделе 2 классифицируются модели коллектива автоматов на графе в зависимости от размера памяти автомата, времени срабатывания автомата и ёмкости ребра (числа сообщений, одновременно перемещающихся по ребру). Выбрана модель максимального распараллеливания, в которой время срабатывания автомата считается нулевым, а ёмкость ребра неограниченной. Это позволяет получать нижние оценки сложности алгоритмов решения задач. Раздел 3 определяет правила оценки алгоритмов. В разделе 4 описаны базовые процедуры обработки сообщений и проводится классификация используемых сообщений в зависимости от маршрутов, проходимых сообщениями, и способа размножения или слияния сообщений. На основе этих процедур предлагается строить алгоритмы решения задач на графах, что демонстрируется в следующих разделах статьи. В разделах 5-9 предложены алгоритм построения остова графа, алгоритм универсального «стопора», определяющего конец работы любого алгоритма по отсутствию в графе сообщений, используемых этим алгоритмом, алгоритм построения дерева кратчайших путей, алгоритм нумерации вершин графа, и алгоритм сбора полуроботами информации о графе в неограниченной памяти автомата корня. Предложенные алгоритмы имеют линейную сложность от $n$ и $m$, и используют число сообщений, линейно зависящее от $n$ и $m$. В разделе 10 рассматривается задача поиска максимального пути в нумерованном графе, которая относится к классу NP. За счёт неограниченного (экспоненциального) числа сообщений алгоритм решения этой задачи имеет линейную сложность. В заключении подводятся итоги и намечаются направления дальнейших исследований: решение других задач на графах и расширение подхода на ориентированные графы, а также недетерминированные и динамические графы.
Ключевые слова:
неориентированные графы, задачи на графах, асинхронные распределённые системы, распределенные алгоритмы.
Образец цитирования:
И. Б. Бурдонов, А. С. Косачев, “Общий подход к решению задач на графах коллективом автоматов”, Труды ИСП РАН, 29:2 (2017), 27–76
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/tisp210 https://www.mathnet.ru/rus/tisp/v29/i2/p27
|
Статистика просмотров: |
Страница аннотации: | 238 | PDF полного текста: | 68 | Список литературы: | 25 |
|