Details
| Title | Алгоритм 11/6 для решения задач построения дерева Штейнера в приложениях к телекоммуникации: выпускная квалификационная работа бакалавра: направление 01.03.02 «Прикладная математика и информатика» ; образовательная программа 01.03.02_02 «Системное программирование» |
|---|---|
| Creators | Овечкин Данил Александрович |
| Scientific adviser | Пастор Алексей Владимирович |
| Other creators | Чуканов В.С. |
| Organization | Санкт-Петербургский политехнический университет Петра Великого. Физико-механический институт |
| Imprint | Санкт-Петербург, 2022 |
| Collection | Выпускные квалификационные работы ; Общая коллекция |
| Subjects | задача штейнера ; приближенные алгоритмы ; графы ; С++ ; параллельные алгоритмы ; steiner tree problem ; approximation algorithm ; graphs ; C++ ; parallel algorithm |
| Document type | Bachelor graduation qualification work |
| File type | |
| Language | Russian |
| Level of education | Bachelor |
| Speciality code (FGOS) | 01.03.02 |
| Speciality group (FGOS) | 010000 - Математика и механика |
| DOI | 10.18720/SPBPU/3/2022/vr/vr22-3058 |
| Rights | Доступ по паролю из сети Интернет (чтение, печать) |
| Record key | ru\spstu\vkr\18873 |
| Record create date | 12/19/2022 |
Allowed Actions
–
Action 'Read' will be available if you login or access site from another network
| Group | Anonymous |
|---|---|
| Network | Internet |
Данная работа посвящена реализации приближенного алгоритма 11/6 для решения задачи поиска минимального дерева Штейнера. Целью данной работы было изучение статьи про алгоритм 11/6 и реализация предложенного алгоритма на языке С++. В рамках данной работы также было проведено сравнение полученного алгоритма с алгоритмом KMB. В результате данного исследования были сделаны выводы, что решение поставленной задачи с помощью алгоритма 11/6 получается точнее, чем с помощью алгоритма KMB, но время работы алгоритма 11/6 больше, чем у KMB. Также было произведено распараллеливание блока алгоритма 11/6, что дало прирост производительности почти в 2 раза. Были также сделаны выводы о зависимости времени работы от количества потоков на четырехъядерном процессоре.
The present work is devoted to the implementation of the approximate algorithm 11/6 for solving Steiner tree problem. The purpose of this work was to research the article about the 11/6 algorithm and the implementation of the proposed algorithm in C++. As part of this work, the obtained algorithm was also compared with the KMB algorithm. As a result of this research, it was concluded that the solution of the problem using the 11/6 algorithm is obtained more accurately than using the KMB algorithm, but the running time of the 11/6 algorithm is longer that that of KMB. Also, the block of the 11/6 algorithm was parallelized, which gave a performance increase of almost 2 times. Conclusions were also drawn about the dependence of the algorithm’s runtime on the number of threads on a quad-core processor.
| Network | User group | Action |
|---|---|---|
| ILC SPbPU Local Network | All |
|
| Internet | Authorized users SPbPU |
|
| Internet | Anonymous |
|
- Алгоритм 11/6 для решения задач построения дерева Штейнера в приложениях к телекоммуникации
- Алгоритм 11/6 для решения задач построения дерева Штейнера в приложениях к телекоммуникации
- Введение
- 1. Постановка задачи поиска минимального дерева Штейнера. Основные определения.
- 2. Алгоритм 11/6 и другие алгоритмы решения
- 3. Программная реализация алгоритма
- 4. Результаты исследования работы алгоритма
- Заключение
- Список использованных источников
Access count: 16
Last 30 days: 0
