Магистерский диплом (ВКР) на тему Алгоритмы ограниченного перебора при интеллектуальном анализе данных

Содержание:

Введение. 2

1 Анализ и проектирование алгоритмов ограниченного
перебора. 7

1.1 Актуальность
темы исследования. 7

1.2
Описание работы существующих алгоритмов и их недостатки. 12

1.3
Понятие алгоритма ограниченного перебора. 21

1.4
Описание работы алгоритма ограниченного перебора. 23

1.5
Вывод. 29

2 Проектирование, реализация и исследование программы на
основе предложенного алгоритма ограниченного перебора. 32

2.1
Разработка структурной схемы алгоритма. 32

2.2
Выбор и обоснование языка программирования и базы данных. 35

2.3
Разработка программы.. 48

2.4
Описание работы программы.. 56

2.5
Вывод. 58

3 Ожидаемый эффект. 60

Заключение. 65

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

Приложение А. Исходный текст файла Form1.cs. 70

Приложение Б. Исходный текст файла Form1.Designer.cs. 79

Введение:

Компьютеры к текущему моменту времени прочно проникли во все
сферы жизни современного общества: начиная от игровой индустрии и развелечений,
и заканчивая жизненно важными сферами логистики продовольственных товаров,
энергетики и обороны. Очевидно, что любая электронно-вычислительная машина
(далее – ЭВМ) работает под управлением соответствующего программного
обеспечения (далее – ПО), которое можно разделить по следующим уровням:

— прошивки аппаратных составляющих ЭВМ на самом низком
уровне (код в микросхеме BIOS,
микропрограммы процессора, чипов разнообразных плат: видео, сетевой, аудио, и
т.п.);

— операционная система вместе с пакетом драйверов устройств,
других низкоуровневых системных программ, а также набором функций, образующих
ее прикладной программный интерфейс – Application Program Interface, далее — API);

— наборы служебных программ: антивирусов, программ
обслуживания дисков, архиваторов, мониторинга состояния компьютера, менеджеров
различных ресурсов и т.п.;

— прикладные пакеты программ, которые выполняют именно
те функции, ради которых и приобретается компьютерная техника (например,
текстовые редакторы, табличные процессоры и системы управления базами данных,
графические редакторы, браузеры Интернета и т.п.).

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

В литературе по основам разработки программ [1-2], которую
уже можно считать классической, утверждается, что алгоритмы плотно связаны с
данными, на обработку которых они нацелены. Отметим, что входная информация для
работы одного какого-либо конкретного алгоритма может представляться весьма
разнообразными способами, а, в зависимости от этого, может меняться и
эффективность работы самого алгоритма (скорость выполнения, надежность или
точность полученных результатов и т.п.). Мало того, при наличии нескольких
альтернативных алгоритмов, выбор оптимальной связки «алгоритм-структура данных»
может значительно улучшить качество получаемых результатов работы программы.
Таким образом, задача выбора рационального алгоритма и соответствующего способа
представления входных данных всегда является чрезвычайно актуальной для отрасли
разработки ПО.

Ясно, что в зависимости от назначения проектируемого ПО,
алгоритмы, положенные в его основу, могут быть более или менее сложными, однако
некоторые из них могут считаться типовыми, так как довольно часто встречаются и
в составе других, более сложных и укрупненных алгоритмов. Наиболее часто в
научно-технической литературе в качестве типовых обсуждаются алгоритмы поиска и
сортировки [3-4]. Однако, практика показывает, что последний тип (разнообразные
сортировки) при решении реальных задач встречаются не так часто, а лишь являются
отличной моделью для исследования основных понятий и методов теории алгоритмов.
Что же касается задач поиска, то это действительно универсальные алгоритмы,
встречающиеся повсеместно (практически в любой программе, предназначенной для
реального применения, т.е. не учебной).

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

Более точно можно сказать, что поиск представляет собой один
из распространенных видов задач в алгоритмике, а перебор может считаться одним
из основных методов поиска. С другой стороны, целью перебора может и не быть
нахождение подмножества объектов, удовлетворяющих условию поиска, а может быть
необходимым выполнение некоторого действия (преобразования) над объектами,
соответствующими некоторому условию. В такой постановке задача лишь косвенно
может быть отнесена к поиску, и грань здесь является достаточно тонкой. Более
подробно определение понятия «перебор» будет рассмотрено ниже, но уже сейчас
понятно, что этот процесс очень распространен при реализации программных
продуктов любой сложности и направленности. Соответственно, актуальной является оптимизация этого
процесса, одним из способов которой является сокращение перечня перебираемых
объектов, чего можно достигать разными способами. Этот вопрос особенно важен
для задач интеллектуального анализа данных, где добиться желаемых результатов
обычно можно только с использованием массивов больших данных (Big Data), соответственно требующих
значительных затрат времени на обработку (а значит любая оптимизация будет
чрезвычайно актуальной).

Целью данного
исследования является уменьшение времени выполнения прикладных задач,
основанных на переборе, чего можно добиться путем анализа и разработки средств
и методов для ограничения перебираемых объектов (т.е. путем внедрения ограниченного
перебора). При этом следует выполнить следующие задачи исследования:

— формализовать описание процесса перебора и связанные
с ним понятия;

— провести аналитический обзор существующих методов
перебора и возможностей по их ускорению;

— разработать улучшенный алгоритм перебора, имеющий
преимущества в эксплуатации по сравнению с известными методами (хотя бы для
некоторых частных случаев, а в идеале – для всех вариантов входных данных и
типов прикладных задач);

— провести программную реализацию предложенного
алгоритма и на конкретном примере провести анализ выявленных особенностей
предложенного решения;

— выполнить тестирование и получить реальную оценку
эффективности предложенного решения, сделать выводы по работе.

Объектом
исследования является процесс перебора объектов в самой общей постановке этой
задачи и при его ограничении в частности.

Предмет
исследования – алгоритмы ограничения перебора, в частности в задачах
интеллектуального анализа данных.

Научная новизна
работы заключается в разработке метода ограничения перебора объектов,
основанного на декомпозиции условия отбора объектов при переборе и их
кластеризации по одному из вычислительно наиболее простых получаемых при
декомпозиции подусловий, что позволяет на порядки сократить время перебора по
сравнению с методами грубой силы.

Практическое значение
работы состоит в разработке программного продукта, иллюстрирующего
эффективность предложенного метода на примере решения распространенной в
компьютерной графике задачи поиска правильных полигонов с заданным количеством
углов (число углов может быть переменным) на множестве N точек (при условии, что N достаточно
большое).

Методы исследования:
в работе применены методы теории алгоритмов и кластерного анализа, методы
теории и технологий программирования, а также анализа данных. Для построения
теоретической базы исследования используются общие методы анализа и синтеза.

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

Заключение:

Таким образом, в данной работе рассмотрена задача ускорения
перебора объектов, которая часто возникает при решении прикладных задач
обработки информации. Первоначально проведена формализация описания процесса
перебора, а также детализированы связанные с ним математические понятия.
Далее на основе аналитического обзора существующих методов перебора и
рассмотрения возможностей по их ускорению сделаны выводы о перспективах и
необходимости собственной разработки в данном направлении. Соответственно, предложен
усовершенствованный алгоритм перебора, основанный на декомпозиции условия перебора
в конъюнктивную или дизъюнктивную нормальную форму, а также с учетом
кластеризации входной информации (или кластеризации дополнительной информации,
высчитываемой на основе входной), относящейся к одному (или нескольким)
подусловиям перебора. Эффективность предложенного метода исследована на примере
распространенной задачи из отрасли компьютерной графики, которая заключается в
поиске правильных n-угольников (полигонов) на множестве точек трехмерного
пространства, заданных тройками своих координат. Предварительный теоретический
расчет позволил оценить ускорение выполнения задачи при использовании
предложенного алгоритма на уровне 2-3 раза, однако эти результаты нужно было
проверить еще и практически путем исследования конкретной программной
реализации. Были разработаны алгоритмы, положенные в основу соответствующей
программы, созданы их блок-схемы и текстовые описания.

С точки зрения возведения программной реализации, обосновано
использование языка программирования C#, среды разработки Microsoft Visual Studio (версия Community 2019) и текстовой базы данных (файл
формата PRN
генерируется дополнительной подпрограммой, написанной в математической
программе MathCad). Программный
продукт имеет удобный графический интерфейс и два режима работы: полный перебор
и ограниченный перебор по разработанному в данной работе алгоритму.

Тестирование программного продукта показало его стабильную
работу (отсутствие системных ошибок и аварийных завершений), а также реальное
ускорение процесса перебора при использовании предложенного метода, которое
составляет до нескольких раз (в 2-3 раза при использовании до 100 кластеров). В
то же самое время было установлено, что за счет попадания разных частей одного
и того же подходящего под перебор объекта в разные кластеры, на самом деле
может быть потеряна небольшая часть нужных объектов. Процент потерь зависит от
количества кластеров разбиения (так же, как и величина ускорения) и даже для
большого числа кластеров дает величину не более 2-3 %. Такие потери являются
вполне допустимыми в задачах компьютерной графики, поэтому в целом применение
данного метода в некоторых прикладных задачах является вполне обоснованным.

Фрагмент текста работы:

1 Анализ и проектирование алгоритмов ограниченного
перебора 1.1 Актуальность темы исследования На сегодняшний день существует значительное количество
предметных областей, где применяются алгоритмы перебора, рассмотрим их
подробнее (ведь чем больше таких задач существует, тем более актуальным
является данное исследование).

В первую очередь, с вычислительной точки зрения наиболее
сложные переборы встречаются в задачах поиска информации в базах данных (БД).
Обоснование этого тезиса рассмотрим подробнее.

Во-первых,
такие задачи характеризуются значительными объемами данных, среди которых нужно
производить перебор. Если речь идет о программе, запущенной в оперативную
память, и которая не использует базу данных для хранения и извлечения
информации, то, очевидно, обрабатываемые данные будут размещены в оперативной
памяти ЭВМ, которая на сегодняшний день для персональных компьютеров (далее –
ПК) составляет величины порядка нескольких гигабайт (но не нескольких десятков
гигабайт). Даже для производительных серверов объемы оперативной памяти могут
достигать сотни гигабайт, что является довольно большой величиной, требующей
применения специальных аппаратных решений (по сравнению с обычной архитектурой
ПК). Однако, данные, которые размещаются в базах данных, даже при использовании
обычных ПК легко могут достигать указанного размера в 100 Гб, а при размещении
на высокопроизводительных серверах объемы хранимых данных исчисляются сотнями
терабайт, что в целом на несколько порядков больше объемов данных, которые
можно размещать в оперативной памяти ЭВМ. Таким образом, выполнение операций на
данных, размещенных в БД, потенциально