Programmer's Programming Art Глава 41 ~ Глава 42: Флаг Нидерландов, Алгоритм Штрассена умножения матриц

алгоритм Примечания

Глава 41–42: проблема голландского флага, алгоритм Штрассена для умножения матриц.

\

предисловие

Две проблемы, которые будут обсуждаться в этой статье: голландский флаг и алгоритм Штрассена для умножения матриц, связаны с методом «разделяй и властвуй», поэтому эти две проблемы объединены. Так называемое «разделяй и властвуй» означает «разделяй и властвуй», это все равно, что сражаться с огромными вооруженными силами врага на войне, применяя стратегию уклонения от их основных сил и разгрома их поодиночке.

Любые вопросы, пожалуйста, не стесняйтесь исправлять меня в любое время, спасибо.

\

\

Глава 11, Нидерланды Национальный флаг

Описание темы

Три шара разного цвета, красный, белый и синий, расположены в случайном порядке. Пожалуйста, переставьте эти шары так, чтобы красные, белые и синие шары одного цвета были вместе. Причина, по которой эта задача называется голландским флагом, заключается в том, что мы можем представить красный, белый и синий шары в виде полос, которые расположены в упорядоченном порядке, образуя голландский флаг. Как показано ниже:

    

\

Анализ мыслей

На первый взгляд кажется, что у нас нет хорошего решения, кроме насильственных решений, но как насчет знакомого нам алгоритма быстрой сортировки? Мы знаем, что быстрая сортировка основана на режиме «разделяй и властвуй», а процесс «разделяй и властвуй» для сортировки типичного подмассива A[p...r] состоит из трех шагов:

  1. Разложение: A[p..r] делится на два (возможно, пустых) подмассива A[p..q-1] и A[q+1..r] такие, что A[p..q-1 ]
  2. .Решение. Отсортируйте подмассивы A[p ..q-1] и A[q+1 ..r], рекурсивно вызвав быструю сортировку.
  3. сливаться.

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

Как показано в следующем псевдокоде:

Ключом к алгоритму быстрой сортировки является процедура PARTITION, которая переставляет A[p..r] на месте:
**PARTITION(A, p, r)
**1 х ← А[г]
2 я ← п - 1
3 для j ← от p до r - 1
4 делать, если A[j] ≤ x
5 затем я ← я + 1
6                  exchange A[i] <-> A[j]
7  exchange A[i + 1] <-> A[r]
8  return i + 1

Затем рекурсивно завершите весь процесс сортировки:

QUICKSORT(A, p, r)
1 if p < r
2 затем q ← PARTITION(A, p, r) //ключ
3         QUICKSORT(A, p, q - 1)
4         QUICKSORT(A, q + 1, r)\

Пример следующий: i указывает на предыдущую позицию головы массива, j указывает на элемент головы массива, j впереди, i позади, оба движутся слева направо.

① Когда j указывает на элемент 2, i также указывает на элемент 2, а 2 и 2 меняются местами без изменений.
i p/j
2 8 7 1 3 5 6 4 (Опорный)

② Итак, j продолжает двигаться назад, пока не укажет на 1, 1 i         j
2   1   7   8   3   5   6   4

③ j продолжает двигаться назад и указывает на элемент 3, 3 i         j
2   1   3   8   7   5   6   4

④ j движется назад до упора и не встречает элементов, меньших точки поворота 4:
i                   j
2   1   3   8   7   5   6   4

⑤ Наконец, A[i + 1] A[r], то есть 8 и 4 меняются местами, поэтому массив окончательно принимает следующий вид:
2   1   3   4   7   5   6   8\

хорошо, пока первый проход быстрой сортировки завершен. Таким образом, 4 делит весь массив на две части, 2 1 3, 7 5 6 8, а затем рекурсивно сортирует эти две части соответственно.

Весь процесс можно найти в этой статье:Алгоритм быстрой сортировки, или посмотрите на картинки, которые я рисовала в школе:

И проблема, с которой мы сталкиваемся, состоит в том, чтобы переставить все шары в три шара разных цветов, можем ли мы установить три указателя и извлечь уроки из процесса разделения?

Решение 1, разделяй разделяй и властвуй

Из предыдущего анализа мы знаем, что эта проблема аналогична процессу разделения в быстрой сортировке. Просто нужно использовать три указателя, один перед началом, один в текущем, один после конца, и два обмениваются.

  1. текущий обход, вся последовательность массива, текущий относится к 1 и не перемещается,
  2. current относится к 0, заменяется на begin, затем current++, begin++,
  3. ток относится к 2, который заменяется на конец, а затем ток не движется, конец--.

Почему на третьем шаге ток ссылается на 2. После замены на конец, ток не перемещает столбец, да, как сказал алгоритм__: причина, по которой ток заменяется на начало, текущий++, начало++, заключается в том, что нет никаких забот. После того, как ток и конец поменялись местами, ток не движется, а конец - из-за забот.

Читатель может представить, что ваша конечная цель — не что иное, как упорядоченное расположение 0, 1 и 2. Только представьте, если на третьем шаге, до того, как ток и конец поменялись местами, в случае, если конец относится к предшествующему 0, и после обмена током в этот момент ток равен 0. Может ли ток двигаться в это время? Я не могу двигаться, это означает 0, и я должен поменять местами столбцы с началом.

хорошо, после стольких слов, возможно, вам будет не очень понятно, просто процитируйте график gnuhpc, с первого взгляда будет ясно:

    

    

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

//引用自gnuhpc
while( current<=end )      
{           
  if( array[current] ==0 )           
   {               
      swap(array[current],array[begin]);                
      current++;                
      begin++;          
   }           
   else if( array[current] == 1 )          
   {               
      current++;          
   } 
          
   else //When array[current] =2 
   {             
      swap(array[current],array[end]);              
      end--;          
   }    
}

Эта глава окончена.

\

\

Глава 42: Алгоритм Штрассена для умножения матриц

Описание темы

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

Анализ мыслей

Согласно введению в Википедии: умножение двух матриц может быть определено только тогда, когда количество столбцов первой матрицы B и количество строк другой матрицы A равны. Если A представляет собой матрицу размера m × n, а B представляет собой матрицу размера n × p, их произведение AB представляет собой матрицу размера m × p, и один из ее элементовгде 1 ≤ i ≤ m, 1 ≤ j ≤ p.

    

Стоит отметить, что умножение матриц удовлетворяет ассоциативному закону и скорости распределения, но не удовлетворяет коммутативному закону.В примере, показанном на рисунке ниже, после обмена и перемножения двух матриц результат меняется:

Давайте подробно решим задачу на умножение матриц.

Решение 1. Насильственное решение

На самом деле, благодаря предыдущему анализу мы ясно увидели, что сложность умножения двух матриц одинаковой размерности составляет O (n ^ 3). Справочный код выглядит следующим образом:

//矩阵乘法，3个for循环搞定  
void Mul(int** matrixA, int** matrixB, int** matrixC)  
{  
	for(int i = 0; i < 2; ++i)   
	{  
		for(int j = 0; j < 2; ++j)   
		{  
			matrixC[i][j] = 0;  
			for(int k = 0; k < 2; ++k)   
			{  
				matrixC[i][j] += matrixA[i][k] * matrixB[k][j];  
			}  
		}  
	}  
}

Решение 2, алгоритм Штрассена

В решении 1 мы использовали циклы 3 for для умножения матриц, но когда размеры двух матриц становятся очень большими, временная сложность O (n ^ 3) становится очень большой, поэтому нам нужно найти лучшее решение.

Вообще говоря, когда объем данных велик, мы склонны делить большие данные на маленькие и обрабатывать их отдельно. Следуя этой идее, если бы мы выбросили две большие матрицы, можем ли мы рассмотреть метод «разделяй и властвуй» для поэтапной обработки умножения каждой маленькой матрицы, потому что мы знаем, что матрицу можно разделить на более мелкие матрицы.

Как показано ниже, когда даны две двумерные матрицы AB:

При умножении этих двух матриц А и В мы находим, что в процессе умножения происходит 8 умножений и 4 сложения:

Сложность матричного умножения в основном отражается на умножении, и одно или два сложения не слишком увеличат сложность. Поэтому мы думаем, можно ли уменьшить количество операций умножения в процессе умножения матриц, чтобы уменьшить сложность умножения матриц? Ответ положительный.

В 1969 году немецкий математик Штрассен доказал, что решение O(N^3) не является оптимальным алгоритмом для умножения матриц.Он проделал ряд работ, чтобы уменьшить окончательную временную сложность до O(n^2,80).

Как он это сделал? Все еще используя приведенный выше пример умножения двух матриц A и B, он определяет 7 переменных:

Таким образом, процесс алгоритма Штрассена выглядит следующим образом:

  • При умножении двух матриц A B разделить A, B, C на квадратные матрицы одинакового размера:

;

  • Видно, что C получается таким образом:

\

  • Теперь определим 7 новых матриц (читатель может подумать о том, как появились эти 7 новых матриц):

  • И конечную результирующую матрицу C можно получить, объединив 7 вышеперечисленных новых матриц:

На первый взгляд, алгоритм Штрассена лишь немного лучше, чем общий алгоритм умножения матриц, потому что временная сложность общего алгоритма умножения матриц равна, а сложность алгоритма Штрассена всего. Но по мере увеличения n, например, когда n >> 100, алгоритм Штрассена становится более эффективным, чем обычный алгоритм умножения матриц.

Как показано ниже:

Решение 3. Непрерывная оптимизация

Согласно введению в Википедии, позже алгоритм Копперсмита-Винограда уменьшает временную сложность матричного умножения N*N до:, а в 2010 году Эндрю Стотерс снова уменьшил сложность до, год спустя, в 2011 году, Вирджиния Уильямс доработала сложность следующим образом:

\

\

использованная литература

  1. Алгоритм быстрой сортировки:blog.CSDN.net/V_July_V/AR…;

  2. Углубленный анализ алгоритма быстрой сортировки:blog.CSDN.net/V_July_V/AR…;

  3. гнухпс:blog.CSDN.net/GNU HPC/Aretti…;

  4. Введение в алгоритм Штрассена в Википедии:Это.Wikipedia.org/wiki/%E6%96…;

  5. Часть диаграммы в главе 42 взята из этой статьи «Компьютерные алгоритмы: умножение матриц Штрассена»:Ву Ву. St OIs.com/blog/2012/1…  ;\

  6. Перевод вышеизложенного от сообщества Тьюринга:Woohoo.ITU ring.com.capable/article/179…;

  7. Алгоритм Копперсмита-Винограда:En. Wikipedia.org/wiki/copper…;\

\

постскриптум

Искусство программирования изначально планировалось написать к пятидесятой главе, а сейчас остались только последние восемь глав.Спасибо за постоянное внимание. Я желаю всем читателям этого блога счастливого китайского Нового года, и все может сбыться в год Лошади, спасибо.

Июль, 28 января 2014 г.

Категории