Про підходи до прискорення перебору об’єктів в задачах обробки інформації

Анотація

У роботі докладно розглянуто поняття процесу перебору. Він здійснюється з об'єктами x, які є елементами деякої множини Х. Метою перебору є виконання деякої активної дії y = f(x) над елементами, що перебираються. Ця дія може, звичайно, застосовуватися і до кожного елемента, але у переважній більшості практичних завдань дія застосовується тільки до тих елементів, які задовольняють певній умові перебору P(x).

Найбільш простим способом перебору є повний перебір або «брут-форс». При цьому до кожного без винятку елементу множини Х застосовується перевірка умови P(x) і, залежно від результату, здійснюється виконання дії y = f(x). Очевидно, що повний перебір є певним еталонним процесом у тому сенсі, що саме в порівнянні з ним зручно оцінювати ефективність того чи іншого алгоритму обмеженого перебору. Алгоритми обмеженого перебору доцільно застосовувати у переважній більшості практичних випадків, якщо тільки повний перебір не займає малопомітний час порядку часток секунди. Однак, у деяких випадках доцільно оптимізувати (обмежувати) перебір навіть за таких малих часів виконання всього процесу – зокрема, якщо такі короткі процеси перебору повторюються багато разів на одиницю часу, складаючись сумарно у деякий, уже досить значний час.

Метод гілок і меж є найвідомішим алгоритмом обмеженого перебору і дозволяє, поступово просуваючись від одного варіанта до іншого, відкидати цілі набори елементів, завідомо не відповідних умові P(x). Однак, даний метод не дозволяє робити надійні попередні оцінки ефективності обходу всього дерева відповідних елементів, а його застосовність для кожної конкретної задачі стає зрозумілою тільки в процесі перебору.

У цій роботі пропонується метод обмеження, заснований на поданні умови перебору P(x) у кон’юнктивній або диз’юнктивній нормальній формі з подальшою перевіркою цієї умови за схемою скорочених логічних обчислень з використанням лише однієї з умов. Також для перевірки цієї умови пропонується заздалегідь проводити обчислення деякої додаткової інформації, спираючись на яку під час перебору, можна отримувати кінцевий результат швидше. В якості такої інформації можна прийняти поділ на класи (кластери) всіх об'єктів, що перебираються, і виконання переборів тільки в межах кластерів, що скорочує загальну кількість елементів, що перебираються.

Пропонований підхід докладно пояснюється на прикладі рішення актуальної задачі з області комп'ютерної графіки, яка полягає у пошуку всіх правильних n-кутників (на прикладі правильних трикутників) на множині N точок тривимірного простору, які задані своїми координатами. Наведено словесний опис повного перебору, необхідного для вирішення такого завдання, а також докладний опис алгоритму обмеженого перебору, який складений за пропонованою схемою (скорочені обчислення за КНФ і попередня кластеризація всіх об'єктів, що перебираються або, точніше, пов'язаної з ними інформації – відстаней між усіма парами).

У роботі наведено числові розрахунки, що дозволяють провести теоретичну оцінку ефективності запропонованого рішення. Встановлено, що при ідеально рівномірному розподілі всіх об'єктів, що перебираються по K класам, відбувається значне зменшення кількості операцій порівняння відстаней при пошуку рівносторонніх трикутників (при числі K = 50 – теоретичне прискорення становить до 3 разів). Прискорення, що одержується, досліджено практично на модельній програмній реалізації, написаній мовою C#, в результаті чого показано, що реальне прискорення є досить близьким до ідеального, а сам запропонований підхід, відповідно, є ефективним.