Интернет магазин китайских планшетных компьютеров

Компьютеры - Полный перебор - Методы оптимизации полного перебора

Метод ветвей и границ

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

Распараллеливание вычислений

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

• Первый подход — построение конвейера. Пусть алгоритм соотношения можно представить в виде цепочки простейших действий: . Возьмём процессоров , зададим их порядок и положим, что — ый процессор выполняет три одинаковые по времени операции:
  1. приём данных от — го процессора;
  2. выполнение операции ;
  3. передача данных следующему -му процессору.

  Тогда конвейер из последовательно соединённых, параллельно и синхронно работающих процессоров работает со скоростью , где — скорость выполнения одной операции одним процессором.

• Второй подход состоит в том, что множество всех возможных ключей разбивается на непересекающиеся подмножества . Система из машин перебирает ключи так, что — ая машина осуществляет перебор ключей из множества . Система прекращает работу, если одна из машин нашла ключ. Самое трудное — это разделение ключевого множества. Но если каждый процессор начнёт вычисление с какого-то произвольного ключа, то время нахождения увеличится, а схема значительно упростится. Среднее число шагов в этом случае составляет , где — число элементов во множестве ключей, а — число процессоров.