Полный перебор: различия между версиями

Хотя полный перебор в большинстве прикладных задач (особенно не связанных со [[криптанализкриптоанализ|взломом шифров]]) на практике не применяется, есть ряд исключений. В частности, когда полный перебор всё же оказывается оптимальным, либо представляет собой ''начальный этап'' в разработке алгоритма, его использование оправдано. Примером оптимальности полного перебора является алгоритм оценки времени вычисления цепочечных произведений матриц, который не удаётся ускорить по сравнению с алгоритмом, основанным на методе «грубой силы»{{sfn|Cormen|2001|p=372}}. Этот алгоритм используется для решения классической задачи [[Динамическое программирование|динамического программирования]] — определения приоритетов вычислений матричных произведений следующего вида: <math>A_1 A_2 A_3 \cdots A_n</math>.

Выбрав правильный порядок вычислений, можно добиться значительного ускорения вычислений. Чтобы убедиться в этом, рассмотрим простой пример цепочки из 3-х матриц. Положим, что их размеры равны соответственно <math>10 \times 100, 100 \times 5, 5 \times 50 </math>. Стандартный алгоритм перемножения двух матриц размерами <math>p \times q, q \times r</math> требует время вычисления, пропорциональное числу <math>pqr</math> (число вычисляемых скалярных произведений){{sfn|Cormen|2001|pp=370-372370—372|loc=Произведение матричных цепочек}}. Следовательно, вычисляя цепочку в порядке <math>((A_1 A_2) A_3)</math>, получаем <math>10 \cdot 100 \cdot 5 = 5000</math> скалярных произведений для вычисления <math>(A_1 A_2)</math>, плюс дополнительно <math>10 \cdot 5 \cdot 50 = 2500</math> скалярных произведений, чтобы вычислить второе матричное произведение. Общее число скалярных произведений: 7500. При ином выборе порядка вычислений получаем

<math>100 \cdot 5 \cdot 50 = 25000</math> плюс <math>10\cdot 100 \cdot 50 = 50000</math> скалярных произведений, то есть 75000 скалярных произведений{{sfn|Cormen|2001|pp=370-372370—372|loc=Произведение матричных цепочек}}.

В [[Теория алгоритмов|теории алгоритмов]] известны несколько широко применимых общих концепций. Метод полного перебора является одной из них. Фактически, полным перебором ''возможно'' воспользоваться в тех случаях, когда мы имеем дело с дискретной детерминированной системой, состояния которой могут быть легко проанализированы{{sfn|Cormen|2001|pp=65-6765—67|loc=Раздел 4. Метод «разделяй и властвуй»}}.