Общий подход к решению задач на графах коллективом автоматов

Предложен общий подход к решению задач на неориентированном упорядоченном корневом связном графе коллективом автоматов, расположенных в вершинах графа и обменивающихся сообщениями по рёбрам графа. Автоматы считаются полуроботами, т.е. размер их памяти может расти вместе с ростом числа n вершин и числа m рёбер графа, но описание графа может не помещаться в памяти автомата. В разделе 2 классифицируются модели коллектива автоматов на графе в зависимости от размера памяти автомата, времени срабатывания автомата и ёмкости ребра (числа сообщений, одновременно перемещающихся по ребру). Выбрана модель максимального распараллеливания, в которой время срабатывания автомата считается нулевым, а ёмкость ребра неограниченной. Это позволяет получать нижние оценки сложности алгоритмов решения задач. Раздел 3 определяет правила оценки алгоритмов. В разделе 4 описаны базовые процедуры обработки сообщений и проводится классификация используемых сообщений в зависимости от маршрутов, проходимых сообщениями, и способа размножения или слияния сообщений. На основе этих процедур предлагается строить алгоритмы решения задач на графах, что демонстрируется в следующих разделах статьи. В разделах 5-9 предложены алгоритм построения остова графа, алгоритм универсального «стопора», определяющего конец работы любого алгоритма по отсутствию в графе сообщений, используемых этим алгоритмом, алгоритм построения дерева кратчайших путей, алгоритм нумерации вершин графа, и алгоритм сбора полуроботами информации о графе в неограниченной памяти автомата корня. Предложенные алгоритмы имеют линейную сложность от n и m , и используют число сообщений, линейно зависящее от n и m . В разделе 10 рассматривается задача поиска максимального пути в нумерованном графе, которая относится к классу NP . За счёт неограниченного (экспоненциального) числа сообщений алгоритм решения этой задачи имеет линейную сложность. В заключении подводятся итоги и намечаются направления дальнейших исследований: решение других задач на графах и расширение подхода на ориентированные графы, а также недетерминированные и динамические графы.

неориентированные графы, задачи на графах, асинхронные распределённые системы, распределенные алгоритмы

1. И. Бурдонов, А. Косачев. Обход неизвестного графа коллективом автоматов. Труды ИСП РАН, том 26, вып. 2, 2014, стр. 43-86. DOI: 10.15514/ISPRAS-2014-26(2)-2

2. И. Бурдонов, А. Косачев. Исследование графа взаимодействующими автоматами. «Вестник Томского государственного университета. Управление, вычислительная техника и информатика», №3, 2014, стр. 67-75.

3. И. Бурдонов, А. Косачев. Обход неизвестного графа коллективом автоматов. Недетерминированный случай. Труды ИСП, том 27, вып. 1, 2015, стр. 51-68. DOI: 10.15514/ISPRAS-2015-27(1)-4

4. И.Б. Бурдонов, А.С. Косачев., В.В. Кулямин. Исследование графа набором автоматов. "Программирование", 2015, №6, стр. 3-8.

5. И.Б. Бурдонов, А.С. Косачев. Исследование графов коллективом двигающихся автоматов. "Программная инженерия", 2016, том 7, № 12, стр. 559-567.

6. И.Б.Бурдонов, А.С. Косачев. Построение прямого и обратного остовов автоматами на графе. Труды ИСП РАН, том 26, вып. 6, 2014, стр. 57-62. DOI: 10.15514/ISPRAS-2014-26(6)-4

7. И.Б.Бурдонов, А.С.Косачев, В.В.Кулямин. Параллельные вычисления автоматами на прямом и обратном остовах графа. Труды ИСП РАН, том 26, вып. 6, 2014, стр. 63-66. DOI: 10.15514/ISPRAS-2014-26(6)-5

8. И.Б. Бурдонов, А.С. Косачев, В.В. Кулямин. Параллельные вычисления на графе. "Программирование", 2015, №1, стр. 3-20.

9. И. Бурдонов, А. Косачев. Мониторинг динамически меняющегося графа. Труды ИСП РАН, том 27, вып. 1, 2015, стр. 69-96. DOI: 10.15514/ISPRAS-2015-27(1)-5

10. И. Бурдонов, А. Косачев. Параллельные вычисления на динамически меняющемся графе. Труды ИСП РАН, том 27(2), 2015, стр. 189-220. DOI: 10.15514/ISPRAS-2015-27(2)-12

11. И.Б. Бурдонов, А.С. Косачев. Исследование ориентированного графа коллективом неподвижных автоматов. "Программная инженерия", 2017, том 8, № 1, стр. 16-25.

12. И.Б.Бурдонов, А.С.Косачев, В.В.Кулямин. Неизбыточные алгоритмы обхода ориентированных графов. Недетерминированный случай. // Программирование. — 2004. — №1. — С. 2-17.

13. И. Бурдонов, А. Косачев. Размер памяти для хранения упорядоченного корневого графа. Труды ИСП РАН, том 29, вып. 2, 2017, стр. xx-xx. DOI: 10.15514/ISPRAS-2017-29(2)-1

14. И.Б. Бурдонов, А.С. Косачев. Исследование графа автоматом. "Программная инженерия", 2016, №11, стр. 498-508.

15. И.Б.Бурдонов. Обход неизвестного ориентированного графа конечным роботом. "Программирование", 2004, №4, стр.11-34.

16. И.Б.Бурдонов. Проблема отката по дереву при обходе неизвестного ориентированного графа конечным роботом. "Программирование", 2004, №6, стр.6-29.

17. David Peleg. Distributed computing — A Locality-sensitive approach. SIAM Monographs on Discrete Mathematics and Applications. 2000, 359 pp.

18. Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5.