ЖАДНЫЙ АЛГОРИТМ И МАТРОИДЫ (2023)
Рассмотрены некоторые задачи дискретной оптимизации, решаемые жадным алгоритмом, который на каждом шаге делает локально оптимальный выбор. Описаны различные примеры использования жадного алгоритма. Гарантом получения правильного ответа жадным алгоритмом является матроидная структура решаемых задач. Приведены сведения из теории матроидов, а также примеры прикладных задач, сформулированных на матроидах, и алгоритмы их решения.
Идентификаторы и классификаторы
- eLIBRARY ID
- 52663764
Жадный алгоритм (greedy algorithm) — это метод решения оптимизационных задач, основанный на том, что процесс принятия решения можно разбить на элементарные шаги, на каждом из которых принимается отдельное решение. Такое решение должно быть оптимальным только на текущем шаге и без учёта предыдущих или последующих решений.
Например, алгоритм Дейкстры, один из алгоритмов нахождения кратчайшего пути в графе, вполне себе жадный, потому что на каждом шаге ищет вершину с наименьшим весом, где ещё не побывали, после чего обновляются значения других вершин. К слову, алгоритм Флойда, который тоже ищет кратчайшие пути в графе, не является примером жадного алгоритма. Он демонстрирует другой метод — метод динамического программирования [1]. Рассмотрим примеры использования жадного алгоритма.
Список литературы
- Ревякин А. М., Бардушкина И. В. Математические методы моделирования в экономике. М.: МИЭТ, 2013. 327 с.
- Oxley J. G. Matroid theory. N. Y.: Oxford University Press, 2006. 532 p.
- Recski A. Matroid theory and its applications in electric network theory and in statics. Budapest: Akad. Kiado, 1989. 531 p.
- Ревякин А. М. Матроиды // Итоги науки и техники. Сер. Современная математика и её приложения. Т. 72. Вычислительная математика и кибернетика-3. M.: ВИТИТИ, 2000. № 1. C. 71-130 (Пер. на англ. яз.: Revyakin A. M. Matroids //j. Math. Sci. 2002. V. 108).
- Ревякин А. М. Графы, матроиды и их инженерные приложения. М.: МИЭТ, 1991. 178 с.
- Исаченко А. Н., Ревякин А. М. Матроиды в математическом моделировании экономических систем // Экономические и социально-гуманитарные исследования. 2015. № 1 (5). С. 13-18. EDN: TPCSAF
- Ревякин А. М. Матроиды: криптоморфные системы аксиом и жесткость ферм // Вестник МГАДА. Сер.: философские, социальные и естественные науки. 2010. № 5 (5). С. 96-106. EDN: NCIZEH
- Алгоритмы: построение и анализ / Т. Х. Кормен, Ч. И. Лейзерсон, Р. Л. Ривест, К. Штайн. М.: ВИЛЬЯМС, 2013. 1328 с.
- Исаченко А. Н., Ревякин А. М. Электрические цепи и ориентированные матроиды // Электронные информационные системы. 2019. № 2 (21). С. 105-111. EDN: CNWFUD
-
Ревякин А. М., Исаченко А. Н. Матроиды и их некоторые приложения // Материалы XIII Международного семинара "Дискретная математика и её приложения" имени академика О. Б. Лупанова (Москва, МГУ, 17-22 июня 2019 г.). М.: Изд-во механико-математического факультета МГУ, 2019. С. 37-49.
Выпуск
Другие статьи выпуска
Выполнено комплексное моделирование стрельбы зенитно-артиллерийского комплекса для оптимизации его параметров на этапе проектирования. Предложен математический аппарат анализа траектории полёта снаряда и возникающих при его взрыве поражающих элементов. Рассмотрен процесс взаимодействия снаряда и поражаемого объекта в целях оценки эффективности стрельбы. Приведена методика расчёта траекторий, обеспечивающая моделирование стрельбы зенитно-артиллерийского комплекса с использованием данных, соответствующих реальным объектам.
Рассмотрена математическая модель квадрокоптера. В рамках уравнений динамики углов Эйлера и линейных координат квадрокоптера выделены линейные регрессии, описывающие параметрическую неопределённость модели. Корректность проведённых преобразований подтверждена результатами численных экспериментов. Полученное представление неопределённости будет использовано при построении адаптивной системы управления.
Уязвимость авианосца со стороны верхней полусферы (попадание в полётную палубу) предлагается характеризовать плоским скалярным полем вероятностей попадания. Его расчёт основан на упрощении геометрического силуэта цели системой равновеликих прямоугольников. Визуализация результата состоит в совместном изображении в одном масштабе силуэта полётной палубы и совокупности изовероятностных контуров. Для модели силуэта полётной палубы при использовании нормального распределения двух независимых случайных величин и варьировании значениями рассеивания установлены форма и положение изолиний, а также соответствующие значения вероятностей попадания.
Описан принцип работы системы нейтрального газа гражданского воздушного судна. Предложен алгоритм проведения встроенного контроля системы нейтрального газа, позволяющий снизить риск отказа системы в полёте за счёт раннего обнаружения скрытых дефектов её составных частей.
Предложена технология создания приложения для расчёта теплового режима электронного блока типовой конструкции при использовании принудительного воздушного охлаждения с учётом фактической производительности вентилятора. В первой части работы даны определения тепловых режимов электронных блоков, выбраны формулы для расчёта тепловых режимов и приведены разработанные схемы приложения. В данной статье описаны разработанные экранные формы и структура приложения, созданного в среде программирования Embarcadero RAD Studio 10.1 Berlin Version 24.022858.6822.
Рассмотрены вопросы построения электрогидравлической системы управления робототехническим комплексом. Отмечены особенности и выделены преимущества использования комбинированного управления в робототехнических комплексах, построенных на базе гусеничных шасси. Особенности предлагаемой электрогидравлической системы управления расширяют функциональные возможности робототехнического комплекса, обеспечивая управление им как в дистанционном, так и в экипажном варианте.
Предложено и экспериментально проверено применение метода роя частиц с островной схемой организации вычислений для решения задачи планирования маршрута движения летательного аппарата с учётом известного рельефа местности. Определены исходные данные задачи. Для оценки качества получаемого решения использована штрафная функция. Осуществлена экспериментальная проверка эффективности решения задачи предложенным методом.
Рассмотрены возможности снижения требуемого уровня быстродействия квазиоптимальных алгоритмов обнаружения, отражённых от малоскоростных целей. Показано, что весовая обработка входной реализации может быть выполнена в частотной области. Приведена структурная схема алгоритма обнаружения. Установлено, что основную обработку сигналов достаточно проводить в пределах полосы частот, равной эффективной ширине АЧХ весового вектора. Проведена оценка зависимости вероятности обнаружения от радиальных скоростей цели.
Приведены параметры, которые должна определять метеостанция для артиллерийского комплекса. Представлены технические и конструктивные особенности станции индикации параметров атмосферы, разработанной специалистами АО «НТЦ ЭЛИНС». Описаны инженерные решения, позволяющие упростить эксплуатацию станции и повысить её надёжность.
Издательство
- Издательство
- АО "НТЦ Элинс"
- Регион
- Россия, Москва
- Почтовый адрес
- 124460, город Москва, город Зеленоград, Панфиловский пр-кт, д. 4 стр. 1, пом V; ком 1-9
- Юр. адрес
- 124460, город Москва, город Зеленоград, Панфиловский пр-кт, д. 4 стр. 1, пом V; ком 1-9
- ФИО
- Тикменов Василий Николаевич (Руководитель)
- Сайт
- https://elins.ru/