h2> Перебір з поверненням.
Загальна схема
Дано N впорядкованих множин U1 U2, ..., Un (N - відомо), і потрібно побудувати вектор А = (а1 а2, ..., аn), де a1 € U1, a2 € U2, ..., An € Un, задовольняє заданій множині умов і обмежень.
В алгоритмі перебору вектор А будується покомпонентно ліворуч
направо. Припустимо, що вже знайдені значення перших (к-1)
компонент, A = (a1, a2, ..., a ( k -1) ), ?, ...,?), Тоді заданий безліч
умов обмежує вибір наступної компоненти а k деяким
безліччю S k CU k . Якщо Sk <> [] (пусте), ми вправі вибрати в
якості а до
найменший елемент Sk і
перейти до вибору ^/^ "^ вибори п В«яВ»,
(к +1) компоненти і
так далі. Однак/[ в– Д Jfcv при даному а,
якщо умови умови
а,, ^ ІАЗ
такі, що Sk виявилося порожнім, то ми повертаємося до вибору
(к-1) компоненти, відкидаємо
а ( k -1) і вибираємо в якості нового a (k-1) той елемент S (ki) , який безпосередньо слід за щойно відкинутим. Може виявитися, що для нового a (k-1) умови задачі допускають непорожнє Sk, і тоді ми намагаємося знову вибрати елемент а до . Якщо неможливо вибрати a (k-1) , ми повертаємося ще на крок назад і вибираємо новий елемент а (к-2) і так далі.
Графічне зображення - дерево пошуку. Корінь дерева (0 рівень) є порожній вектор. Його сини суть безліч кандидатів для вибору а1 і, в загальному випадку, вузли k-го рівня є кандидатами на вибір а до за умови, що а1, А2, ..., a (k-1) вибрані так, як вказують предки цих вузлів. Питання про те, чи має завдання рішення, рівносильний питання, чи є які-небудь вузли дерева рішеннями. Розшукуючи всі рішення, ми хочемо отримати всі такі вузли. p> Рекурсивна схема реалізації алгоритму,
procedure Backtrack (Beктop, i);
begin
if <вектор є рішенням> then <записати його>
else begin <обчислити Si>;
for a € Si do Васкtrаск (вектор | | a, i + l); {| | - додавання до вектора компоненти}
end; end;
Оцінка тимчасової складності алгоритму. Дана схема реалізації перебору призводить до експоненціальним алгоритмам. Дійсно, Нехай всі рішення мають довжину N, тоді досліджувати потрібно близько | Si | * | S2 | * ... * | SN | вузлів дерева. Якщо значення S; обмежено деякою константою С, то отримуємо порядку C N вузлів. h2>В В Пошук даних.
Логарифмічний (бінарний) пошук
Логарифмічний (Бінарний або метод розподілу навпіл) пошук даних застосуємо до сортували безлічі елементів а 1 <а 2 <... <А п , розміщенн...
