Определение формул для построения почти оптимального дерева поиска
(Стр. 222-234)
Гадасин Денис Вадимович
Маклачкова Виктория Валентиновна
Рулев Денис Владиславович
Косенок Иван Игоревич
Подробнее об авторах
Гадасин Денис Вадимович
кандидат технических наук, доцент; заместитель заведующего, кафедра «Сетевые информационные технологии и сервисы»
Московский технический университет связи и информатики (МТУСИ)
г. Москва, Российская Федерация Маклачкова Виктория Валентиновна кандидат технических наук; доцент; Московский технический университет связи и информатики (МТУСИ); г. Москва, Российская Федерация Рулев Денис Владиславович ассистент; Московский технический университет связи и информатики (МТУСИ); г. Москва, Российская Федерация Косенок Иван Игоревич ассистент; Московский технический университет связи и информатики (МТУСИ); г. Москва, Российская Федерация
Московский технический университет связи и информатики (МТУСИ)
г. Москва, Российская Федерация Маклачкова Виктория Валентиновна кандидат технических наук; доцент; Московский технический университет связи и информатики (МТУСИ); г. Москва, Российская Федерация Рулев Денис Владиславович ассистент; Московский технический университет связи и информатики (МТУСИ); г. Москва, Российская Федерация Косенок Иван Игоревич ассистент; Московский технический университет связи и информатики (МТУСИ); г. Москва, Российская Федерация
Аннотация:
Передача любого пакета от узла отправителя до узла получателя происходит только после того, как для него на устройстве коммутации будет определен маршрут в соответствии с таблицами маршрутизации. Таблица составляется исходя из состояния сети на фиксированный момент времени, в случае изменения состояния сети таблица должна перестраиваться. Чем оптимальнее выбран маршрут, тем меньше задержка передачи. Для того чтобы выбрать маршрут, в таблице маршрутизации осуществляется поиск соответствующего интерфейса. Время поиска включается в общую задержку. Таблица представляет собой структуру данных. Одной из форм существования данных является бинарное дерево. Оптимальное дерево – сумма произведений веса листовой вершины на номер уровня на котором данная вершина находится, является минимальной. Целью работы являлось определить подход, с помощью которого возможно построение почти оптимальных деревьев для осуществления задач поиска в средах, которые требуют частого изменения своего состояния. Результатом работы стали формулы построения почти оптимального дерева. Оценка их точности показала, что относительная погрешность не превышает 6%, а выигрыш во времени при построении дерева для 7531 вершины составляет 2,68 раза.
Образец цитирования:
ОБРАЗЕЦ ЦИТИРОВАНИЯ: Гадасин Д.В., Маклачкова В.В., Рулев Д.В., Косенок И.И. Определение формул для построения почти оптимального дерева поиска // Computational Nanotechnology. 2026. Т. 13. № 3. С. 222-234. DOI: 10.33693/2313-223X-2026-13-3-222-234. EDN: WYBWZQ
Список литературы:
Гадасин Д.В. Построение бинарного дерева минимальной цены // T-Comm: Телекоммуникации и транспорт. 2024. Т. 18. № 11. С. 38–44. DOI: 10.36724/2072-8735-2024-18-11-38-44. EDN: GMCEWG.
Гадасин Д.В. Способ определения основных узлов сети для анализа ее состояния // T-Comm: Телекоммуникации и транспорт. 2025. Т. 19. № 12. С. 16–24. DOI: 10.36724/2072-8735-2025-19-12-16-24. EDN: FGAATI.
Гадасин Д.В., Галицкий М.В., Цыганков Р.О. Сравнительный анализ производительности сокетов: TCP, UDP, SCTP, QUIC // Известия Кабардино-Балкарского научного центра РАН. 2026. Т. 28. № 1. С. 117–134. DOI: 10.35330/1991-6639-2026-28-1-117-134. EDN: EFWDBI.
Гадасин Д.В., Горохов К.И. Анализ методов поиска решения в соответствии с критериями отбора для задачи ранжирования товаров платформ электронной коммерции // Computational Nanotechnology. 2026. Т. 13. № 1. С. 186–201. DOI: 10.33693/2313-223X-2026-13-1-186-201. EDN: NCCXTS.
Гадасин Д.В., Тремасова Л.А., Калининский Д.С. Снижение размерности данных для анализа посредством метода главных компонент // Computational Nanotechnology. 2025. Т. 12. № 3. С. 130–140. DOI: 10.33693/2313-223X-2025-12-3-130-140. EDN: BLPFIZ.
Гадасин Д.В., Шведов А.В. Применение транспортной задачи для балансировки нагрузки в условиях нечеткости исходных данных // T-Comm: Телекоммуникации и транспорт. 2024. Т. 18. № 1. С. 13–20. DOI: 10.36724/2072-8735-2024-18-1-13-20. EDN: WKNPIX.
Калининский Д.С., Тремасова Л.А., Гадасин Д.В. Определение модели управления доступом для телекоммуникационной системы // Моделирование, оптимизация и информационные технологии. 2025. Т. 13. № 4 (51). DOI: 10.26102/2310-6018/2025.51.4.010. EDN: JCEOXO.
Тремасова Л.А., Первухина А.А., Гадасин Д.В. Использование методов Косарайю и k-средних для формирования кластеров // Электросвязь. 2024. № 9. С. 47–55. DOI: 10.34832/ELSV.2024.58.9.007. EDN: DOZTZK.
Shvedov A.V., Gadasin D.V., Alyoshintsev A.V. Segment routing in data transmission networks // T-Comm: Telecommunications and Transport. 2022. Vol. 16. No. 5. Pp. 56–62. DOI: 10.36724/2072-8735-2022-16-5-56-62. EDN: VAYLJQ.
Гадасин Д.В. Способ определения основных узлов сети для анализа ее состояния // T-Comm: Телекоммуникации и транспорт. 2025. Т. 19. № 12. С. 16–24. DOI: 10.36724/2072-8735-2025-19-12-16-24. EDN: FGAATI.
Гадасин Д.В., Галицкий М.В., Цыганков Р.О. Сравнительный анализ производительности сокетов: TCP, UDP, SCTP, QUIC // Известия Кабардино-Балкарского научного центра РАН. 2026. Т. 28. № 1. С. 117–134. DOI: 10.35330/1991-6639-2026-28-1-117-134. EDN: EFWDBI.
Гадасин Д.В., Горохов К.И. Анализ методов поиска решения в соответствии с критериями отбора для задачи ранжирования товаров платформ электронной коммерции // Computational Nanotechnology. 2026. Т. 13. № 1. С. 186–201. DOI: 10.33693/2313-223X-2026-13-1-186-201. EDN: NCCXTS.
Гадасин Д.В., Тремасова Л.А., Калининский Д.С. Снижение размерности данных для анализа посредством метода главных компонент // Computational Nanotechnology. 2025. Т. 12. № 3. С. 130–140. DOI: 10.33693/2313-223X-2025-12-3-130-140. EDN: BLPFIZ.
Гадасин Д.В., Шведов А.В. Применение транспортной задачи для балансировки нагрузки в условиях нечеткости исходных данных // T-Comm: Телекоммуникации и транспорт. 2024. Т. 18. № 1. С. 13–20. DOI: 10.36724/2072-8735-2024-18-1-13-20. EDN: WKNPIX.
Калининский Д.С., Тремасова Л.А., Гадасин Д.В. Определение модели управления доступом для телекоммуникационной системы // Моделирование, оптимизация и информационные технологии. 2025. Т. 13. № 4 (51). DOI: 10.26102/2310-6018/2025.51.4.010. EDN: JCEOXO.
Тремасова Л.А., Первухина А.А., Гадасин Д.В. Использование методов Косарайю и k-средних для формирования кластеров // Электросвязь. 2024. № 9. С. 47–55. DOI: 10.34832/ELSV.2024.58.9.007. EDN: DOZTZK.
Shvedov A.V., Gadasin D.V., Alyoshintsev A.V. Segment routing in data transmission networks // T-Comm: Telecommunications and Transport. 2022. Vol. 16. No. 5. Pp. 56–62. DOI: 10.36724/2072-8735-2022-16-5-56-62. EDN: VAYLJQ.
Ключевые слова:
оптимальные деревья, почти оптимальные деревья, структуры данных, организация данных, построение деревьев, формулы построения деревьев.