Comparison of Permutation Methods with Two Types of Data Structures
Comparison of Permutation Methods with Two Types of Data Structures
Abstract
The exhaustive permutation algorithm is a widely used approach to solve discrete optimization problems by exploring all possible combinations of parameters (vectors) to find the optimal solution. This work presents a performance analysis of different permutation methods used to generate solution vectors, (next_permutation function in C++, heap method, next lexicographical permutation method) with two types of data structures. The main objective of the research is to improve the efficiency of the exhaustive search algorithm in solving discrete optimization problem. The next lexicographical permutation method using dynamic set showed better results. The obtained results confirm the possibility of increasing the efficiency of the exhaustive search algorithm by using the next lexicographical permutation method for generating solution vectors.
1. Введение
Генерация перестановок является важной задачей во многих областях, для которой известно множество методов решения. Классические методы, такие как подсчет, рекурсивный метод сверху вниз и итерационный метод снизу вверх , являются наиболее часто используемыми, но также существуют и другие алгоритмы, которые могут быть эффективными в определенных случаях.
Методы перестановки играют решающую роль в алгоритме полного перебора, определяющем порядок, в котором исследуются комбинации параметров. В статье автор описывает сравнительное исследование производительности алгоритмов перестановок, таких как «Снизу вверх», лексикография и Johnson-trotter, которые были реализованы с использованием алгоритмов полного перебора (BFA) и ветвей и границ (BBA). Использование этих методов перестановки позволяет быстрее исследовать комбинации параметров, при этом гарантируя рассмотрение всех возможных решений . Такая интеграция эффективных методов перестановки с алгоритмом полного перебора является новым подходом к снижению вычислительной сложности для крупномасштабных задач.
Структуры данных играют ключевую роль в хранении, доступе и обработке данных в памяти. Они являются важной частью решения научных задач, позволяя эффективно работать с большими объемами данных и выполнять операции оптимальным образом . Выбор структуры данных может оказать значительное влияние на эффективность алгоритма. Оптимальная структура данных может сократить количество операций и повысить эффективность выполнения алгоритма . Различные структуры данных обладают разными характеристиками, и выбор правильной из них может привести к повышению эффективности. В статье автор проанализировал использование различных структур данных для повышения эффективности алгоритмов.
Для задач небольшого размера, комбинаторные алгоритмы могут быть достаточно эффективными и позволяют найти оптимальное решение. Однако, с увеличением размера задачи, комбинаторные алгоритмы могут стать слишком медленными и несостоятельными. В таких случаях применение быстрых алгоритмов оптимизации может быть более эффективным.
В нашей статье показано, что использование динамического массива в методах перестановок позволяет значительно повысить эффективность процесса поиска решения в BFA. Алгоритм может быть распараллелен для использования вычислительной мощности современных архитектур параллельных вычислений, повышая его эффективность при решении крупномасштабных задач.
2. Методы перестановки и структурирования данных
Функция next_permutation (метод_1), предоставляемая библиотекой стандартных шаблонов C++, является полезным инструментом для решения задач комбинаторной оптимизации , анализа алгоритмов, основанных на перестановках. Функция генерирует следующую лексикографически большую перестановку заданной последовательности и изменяет входную последовательность, переставляя элементы для получения следующей лексикографически большей перестановки. Функция начинается с наименьшей возможной перестановки и рекурсивно перебирает все возможные перестановки, увеличивая элементы по порядку, пока не достигнет наибольшей перестановки, возвращая значение ложь, когда перестановок больше нет. Эта функция использует лексикографический порядок элементов для определения следующей перестановки.
Метод heap (метод_2) генерирует перестановки с использованием рекурсивного обратного отслеживания, если длина равна 1, он выводит текущую перестановку. В противном случае, он генерируется рекурсивным методом, при котором каждый элемент замещается последним, а затем происходит рекурсивное создание перестановок для остальных элементов . Метод чередует генерацию перестановок с нечетной длиной и четной длиной, в зависимости от того, является ли длина вектора четной или нечетной.
Метод – next lexicographical permutation (метод_3) является общим подходом для генерации следующей лексикографически большей перестановки элементов последовательности . Алгоритм работает путем нахождения крайнего правого элемента, справа от которого находится меньший элемент. Затем этот крайний правый элемент заменяется наименьшим элементом справа, который больше текущего элемента. После этого происходят изменения элементов справа от точки поворота . Этот процесс осуществляется шаг за шагом и генерирует следующую лексикографически большую перестановку.
В таблице 1 представлено сравнение быстродействия различных методов перестановки с двумя структурами данных для векторов размерностью . Во всех случаях число генерируемых векторов составляет N!.
Таблица 1 - Сравнение методов перестановки с двумя структурами данных
Размер N | Структура данных | Время генерации векторов (сек) | ||
Метод_1 | Метод_2 | Метод_3 | ||
10 | Вектор | 2,36 | 0,38 | 0,36 |
Динамический массив | 0,65 | 0,13 | 0,08 | |
11 | Вектор | 23,39 | 3,94 | 3,34 |
Динамический массив | 6,61 | 1,32 | 0,88 | |
12 | Вектор | 279,3 | 45,43 | 38,2 |
Динамический массив | 76,6 | 14,38 | 8,72 | |
13 | Вектор | 3730,86 | 585,4 | 492,99 |
Динамический массив | 980,79 | 183,96 | 110,51
| |
14 | Вектор | 51322,04 | 8222,44 | 6999,98 |
Динамический массив | 14035,65 | 2571,32 | 1572,83 | |
Динамический массив и вектор используются для хранения коллекций элементов в языке программирования C++. Динамический массив – это массив, размер которого может быть изменен во время выполнения, а вектор представляет собой специализированную реализацию динамического массива, которая обеспечивает дополнительную функциональность и безопасность, такие как проверка границ и автоматическое изменение размера при необходимости.
Динамические массивы имеют фиксированный объем, но мы можем увеличить или уменьшить их размер по мере необходимости, выделив новую память и скопировав элементы . Вектор является частью библиотеки стандартных шаблонов (STL), и он автоматически обрабатывает выделение памяти и изменение размера . Динамические массивы требуют ручного выделения и освобождения памяти с помощью new и delete, в то время как векторы управляют памятью автоматически, и вам не нужно обрабатывать память явно.
Избегая операций изменения размера, динамический массив может быть быстрее вектора при генерации лексикографической перестановки. Вектор обеспечивает безопасность, удобство и более высокий уровень абстракции, в то время как динамический массив обеспечивает более низкий уровень управления и может быть немного быстрее в некоторых конкретных случаях использования. Наши эксперименты показали, что динамический массив работает быстрее, чем вектор, для всех возможных комбинаций перестановок из-за меньших затрат памяти, улучшенной локализации кэша и прямого доступа к памяти.
Повышение эффективности BFA с помощью next lexicographical permutation
В статье проанализированы рекурсивные и итерационные реализации алгоритмов поиска. В статье автор представил сравнительный анализ между рекурсивным и итерационным методами генерации перестановок для решения задачи коммивояжера и показал, что итерационный алгоритм работает в 8-16 раз быстрее, чем рекурсивный алгоритм.
В нашей статье было исследовано применение next lexicographical permutation с итерационной технологией и динамическим массивом для повышения эффективности метода BFA при решении задачи квадратичного назначения (QAP). Данный метод генерирует перестановки с использованием итерационного подхода для поиска перестановки следующей непосредственно за данной перестановкой в лексикографическом порядке. Она включает в себя идентификацию элементов, которые необходимо заменить, а также реверсирования частей последовательности.
Алгоритм полного перебора и QAP
Алгоритм полного перебора гарантирует нахождение точного решения задачи квадратичного назначения путем оценки всех возможных комбинаций . BFA легко реализуется и не требует сложных модификаций или настройки параметров, специфичных для конкретной задачи. Этот алгоритм универсален и может быть применен в различных областях, включая расположение объектов, планирование, оптимизацию сетей и кластеризацию данных .
В качестве оптимизационной задачи в наших исследованиях использовалась задача квадратичного назначения. Её математическая формулировка и условия задачи описаны в работе .
Повышение скорости генерации вариантов решений за счёт совершенствования операции перестановки снижает вычислительную сложность BFA при решении QAP.
Ниже представлен фрагмент псевдокода, который демонстрирует использование метода next lexicographical permutation с итерацией и динамическим массивом для эффективного перебора всех возможных комбинаций элементов вектора решения. Такой подход значительно уменьшает количество вариантов, которые необходимо рассмотреть.
Рисунок 1 - Фрагмент псевдокода
3. Основные результаты
Для проведения вычислительных экспериментов был использован персональный компьютер с процессором Intel® Core™ i3 9th поколения с тактовой частотой 3.1 ГГц. Эксперименты были выполнены в среде Visual Studio 2019. В таблице 2 показано время, затраченное на решение задачи с использованием метода BFA с различными методами перестановок, при решении QAP с использованием итерации и структур данных.
Таблица 2 - Время решения QAP с использованием BFA
Размер N | Структура данных | Время решения (сек) | ||
Метод_1 | Метод_2 | Метод_3 | ||
14 | Вектор | 87,724 | 54,174 | 53,264 |
Динамический массив | 17,772 | 12,176 | 11,323 | |
Полученные результаты подтверждают, что меньшее время решения обеспечивает метод next lexicographical permutation с динамическими массивами.
4. Заключение
Проведенные исследования показали важность операции перестановки элементов вектора решения для алгоритма полного перебора. Использование эффективного метода next lexicographical permutation с динамическим массивом, позволяет снизить вычислительную нагрузку BFA, делает его более практичным для реальных задач высокой размерности.