Preview

Российский технологический журнал

Расширенный поиск

Определение кратчайших гамильтоновых путей в произвольных графах распределенных баз данных

https://doi.org/10.32362/2500-316X-2019-7-4-7-20

Полный текст:

Аннотация

Разработан метод поиска кратчайшего гамильтонова пути в произвольном графе на основе рангового подхода, который обеспечивает высокую оперативность и существенное уменьшение погрешности решения задачи организации процесса управления множеством транзакций и запросов при их реализации в сетевых базах данных. Во многих случаях существующие решения не обеспечивают необходимых результатов по времени доступа и точности найденного решения. Использование разработанного метода позволяет минимизировать время простоя вычислительных устройств, сократить объемы и время передачи данных от одних исполнительных устройств к другим, повысить общую масштабируемость, минимизировать время доступа к данным и пр. Важным достоинством предлагаемого метода является уменьшения числа элементарных операций и числа обрабатываемых векторов в процедуре формирования очереди выполнения операций запроса, что приводит к существенному уменьшению времени на реализацию этих процедур. В работе используются методы теории графов. Оценка эффективности решения задачи выполнена с использованием системного подхода, системного анализа и теории исследования операций. Обработка экспериментальных данных, полученных в ходе работы, проведена в соответствии с положениями математической статистики.

Об авторах

Е. Г. Андрианова
ФГБОУ ВО «МИРЭА – Российский технологический университет»
Россия

кандидат технических наук, доцент кафедры корпоративных информационных систем Института информационных технологий

Scopus author ID 57200555430
ResearcherIDS T-7908-2018

Россия, 119454, Москва, пр. Вернадского, д. 78 

 



В. К. Раев
ФГБОУ ВО «МИРЭА – Российский технологический университет»
Россия

доктор технических наук, профессор кафедры инструментального и прикладного программного обеспечения Института информационных технологий

Россия, 119454, Москва, пр. Вернадского, д. 78 



Д. И. Фильгус
ФГБОУ ВО «МИРЭА – Российский технологический университет»
Россия

аспирант кафедры инструментального и прикладного программного обеспечения Института информационных технологий

Россия, 119454, Москва, пр. Вернадского, д. 78 



Список литературы

1. Аббасов М.Э. Методы оптимизации: Учеб. пособие. СПб.: Изд-во «ВВМ», 2014. 64 с.

2. Буй Д.Б., Скобелев В.Г. Модели, методы и алгоритмы оптимизации запросов в базах данных (обзор) // Радиоэлектронные и компьютерные системы. 2014. № 2 (66). C. 43–58. http://nbuv.gov.ua/UJRN/recs_2014_2_8

3. Бердников В.П. Модифицированный алгоритм определения полных областей устойчивости нестационарных нелинейных систем // Российский технологический журнал. 2018. Т. 6. № 3. С. 39–53. https://doi.org/10.32362/2500-316X-2018-6-3-39-53

4. Пастушков А.А., Батоврин В.К. Выбор решений при проектировании сложных систем на основе анализа вариантов со случайными весами // Российский технологический журнал. 2018. Т. 6. № 4. С. 78–88. https://doi.org/10.32362/2500-316X-2018-6-4-78-88

5. Горобец В.В. Облачная модель транзакционной системы // Вестник компьютерных и информационных технологий. 2013. № 4. С. 19–24.

6. Мендкович Н.А., Кузнецов С.Д. Обзор развития методов лексической оптимизации запросов // Труды Института системного программирования РАН. 2012. Т. 23. С. 195–214. https://doi.org/10.15514/ISPRAS-2012-23-12

7. Листровой С.В., Минухин С.В., Листровая Е.С. Разработка метода мониторинга распределенной вычислительной системы на основе определения кратчайших путей и кратчайших гамильтоновых циклов в графе // Восточно-Европейский журнал передовых технологий. 2015. Т. 6. № 4 (78). С. 32–45. https://doi.org/10.15587/1729-4061.2015.56247

8. Замбицкий Д.К., Лозовану Д.Д. Алгоритмы решения оптимизационных задач на сетях. Кишинев: Штиница, 1983. 116 с.

9. Фильгус Д.И., Андрианова Е.Г., Раев В.К. Развитие методов параллельных вычислений для фрагментации данных сетевой базы данных на основе рангового подхода // Cloud of Science. 2018. Т. 5. № 3. С. 532–550. URL: https://cloudofscience.ru/sites/default/files/pdf/CoS_5_532.pdf

10. Listrovoy S.V., Golubnichiy D.Y., Listrovaya E.S. Solutiоn method on the basis of rank approach for integer linear programming problems with Boolean variables // Engineering Simulation. 1999. V. 16. № 6. P. 707–725.

11. Listrovoy S.V., Tretiak V.F., Listrovaya E.S. Parallel algorithms of calculation process optimization for the boolean programming problems // Engineering Simulation. 1999. V. 16. № 5. Р. 569–579.

12. Федорин А.Н. Многокритериальные задачи ранцевого типа: разработка и сравнительный анализ алгоритмов: дис. ... канд. техн. наук. Нижний Новгород: Нижегородский государственный университет им. Н.И. Лобачевского, 2010. 132 с.

13. Лыфарь Д.А. Параллельные алгоритмы обработки реляционных баз данных // Вестник НГУ. Серия: Информационные технологии. 2010. Т. 8. Вып. 4. С. 72–80. URI: http://www.nsu.ru/xmlui/handle/nsu/307

14. Фраленко В.П., Агроник А.Ю. Средства, методы и алгоритмы эффективного распараллеливания вычислительной нагрузки в гетерогенных средах // Программные системы: теория и приложения. 2015. T. 6. № 3(26). C. 73–92. https://doi.org/10.25209/2079-3316-2015-6-3-73-92

15. Жуков В.С. Исследование методов оптимального размещения базы данных по узлам вычислительной сети // Siberian Journal of Life Sciences and Agriculture. 2010. № 4 (10). С. 75–76.


Дополнительные файлы

1. Рис. 1. Стянутое дерево всех путей D графа G(V, E).
Тема
Тип Research Instrument
Посмотреть (38KB)    
Метаданные

Для цитирования:


Андрианова Е.Г., Раев В.К., Фильгус Д.И. Определение кратчайших гамильтоновых путей в произвольных графах распределенных баз данных. Российский технологический журнал. 2019;7(4):7-20. https://doi.org/10.32362/2500-316X-2019-7-4-7-20

For citation:


Andrianova E.G., Raev V.K., Filgus D.I. Determination of the Shortest Hamiltonian Paths in an Arbitrary Graph of Distributed Databases. Russian Technological Journal. 2019;7(4):7-20. (In Russ.) https://doi.org/10.32362/2500-316X-2019-7-4-7-20

Просмотров: 32


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2500-316X (Online)