Алгоритми перебору та лексикографічний порядок

Алгоритми для перебору дуже великого числа варіантів потрібні для великої кількості прикладних дискретних задач, таких як пошук оптимального рішення, відбір елементів за певними умовами, тощо. Для перебору елементів використовують алгоритми перебору, рекурсії та перебору з поверненням. Найбільш відомі два алгоритми генерації вибірок - рекурсивний і алгоритм лексикографічного порядку перестановок. Стандартна бібліотека шаблонів STL мови програмування С++ містить реалізований алгоритм для знаходження наступної в лексикографічному порядку перестановки next_permutation.

Розглянемо алгоритми перебору, які полягають в генерації всіх можливих варіантів усіх об’єктів, що задовольняють певні умови. У цьому розділі ми розглянемо перебір усіх вибірок із множини А. Для спрощення записів задачі розміщення (а _1, а ₂,..., а_r) позначатимемо як , і розглядатимемо розміщення множини А= {1, 2,…, п } - індексів об’єктів, так як довільну множину можна проіндексувати шляхом присвоєння кожному об’єкту індивідуального номеру. Для перебору набагато зручніше користуватись індексами, а не реальними об’єктами.

Для реалізації перебору потрібно:

· встановити лексикографічний порядок елементів, що підлягають перерахуванню (зокрема, визначити, який з них буде першим, а який останнім);

· знайти алгоритм переходу від довільного елементу до лексикографічно наступного (безпосередньо наступного) за ним.

Алгоритм ґрунтується на послідовному переході по елементах у лексикографічному порядку, починаючи від мінімального і завершуючи максимальним.

Означення 3.1. Лексикографічний порядок – це природний спосіб упорядкування послідовностей на основі порівняння індивідуальних символів. На множині всіх розміщень із r елементів означимо порівняння таким чином: < , якщо

.

У такому разі говорять, що перестановка менша від перестановки , або перестановка більша від перестановки

У програмуванні такий лексикографічний порядок використовують для порівняння стрічок, тільки замість чисел беруть символи ASCII чи Unicode (в залежності від типу стрічки) і лексикографічний порядок відповідає порядку символів.

Приклад 3.1. Порівняємо стрічки hello та hermes. Очевидно, що перша та друга літера однакові. Тому порівняння визначатиме третя літера. У таблиці ASCII (чи відповідно до англійської абетки) літера l передує літері m. Тому hello < hermes. ▲

Означення 3.2. Вибірку називають лексикографічно наступною (безпосередньо наступною) за , якщо не існує такої вибірки , що:

< <

Визначимо, яким чином можна побудувати лексикографічно наступне розміщення за розміщенням .