DAA - Краткое руководство

Алгоритм - это набор шагов операций для решения задачи, выполняющей задачи расчета, обработки данных и автоматизированного обоснования. Алгоритм - это эффективный метод, который может быть выражен за конечное количество времени и пространства.

Алгоритм - это лучший способ представить решение конкретной проблемы очень простым и эффективным способом. Если у нас есть алгоритм для конкретной проблемы, то мы можем реализовать его на любом языке программирования, а это означает, чтоalgorithm is independent from any programming languages.

Разработка алгоритма

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

Для решения проблемы можно использовать разные подходы. Некоторые из них могут быть эффективными с точки зрения затрат времени, тогда как другие подходы могут быть эффективными с точки зрения памяти. Однако следует иметь в виду, что потребление времени и использование памяти нельзя оптимизировать одновременно. Если нам требуется, чтобы алгоритм работал за меньшее время, мы должны инвестировать в больший объем памяти, а если нам требуется, чтобы алгоритм работал с меньшим объемом памяти, нам нужно иметь больше времени.

Шаги по развитию проблемы

Следующие шаги связаны с решением вычислительных задач.

• Определение проблемы
• Разработка модели
• Спецификация алгоритма
• Разработка алгоритма
• Проверка правильности алгоритма
• Анализ алгоритма
• Реализация алгоритма
• Тестирование программы
• Documentation

Характеристики алгоритмов

Основные характеристики алгоритмов следующие:

• Алгоритмы должны иметь уникальное имя

• Алгоритмы должны иметь явно определенный набор входов и выходов.

• Алгоритмы упорядочены с однозначными операциями

• Алгоритмы останавливаются за конечное время. Алгоритмы не должны работать до бесконечности, т. Е. Алгоритм должен заканчиваться в какой-то момент.

Псевдокод

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

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

Разница между алгоритмом и псевдокодом

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

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

Например, ниже приведен алгоритм сортировки вставкой.

Algorithm: Insertion-Sort 
Input: A list L of integers of length n  
Output: A sorted list L1 containing those integers present in L 
Step 1: Keep a sorted list L1 which starts off empty  
Step 2: Perform Step 3 for each element in the original list L  
Step 3: Insert it into the correct position in the sorted list L1.  
Step 4: Return the sorted list 
Step 5: Stop

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

for i <- 1 to length(A) 
   x <- A[i] 
   j <- i 
   while j > 0 and A[j-1] > x 
      A[j] <- A[j-1] 
      j <- j - 1 
   A[j] <- x

В этом руководстве алгоритмы будут представлены в виде псевдокода, который во многом похож на C, C ++, Java, Python и другие языки программирования.

В теоретическом анализе алгоритмов принято оценивать их сложность в асимптотическом смысле, т. Е. Оценивать функцию сложности для произвольно больших входных данных. Срок"analysis of algorithms" был придуман Дональдом Кнутом.

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

Обычно эффективность или время работы алгоритма указывается как функция, связывающая длину ввода с количеством шагов, известную как time complexity, или объем памяти, известный как space complexity.

Необходимость анализа

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

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

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

Анализ алгоритма - это процесс анализа способности алгоритма решать проблемы с точки зрения требуемого времени и размера (размер памяти для хранения при реализации). Однако основная проблема анализа алгоритмов - это необходимое время или производительность. Как правило, мы выполняем следующие виды анализа -

• Worst-case - Максимальное количество шагов, сделанных для любого экземпляра размера a.

• Best-case - Минимальное количество шагов, сделанных для любого экземпляра размера a.

• Average case - Среднее количество шагов, сделанных для любого экземпляра размера a.

• Amortized - Последовательность операций, применяемых к вводу размера a усредненные по времени.

Чтобы решить проблему, нам нужно учитывать время, а также сложность пространства, так как программа может работать в системе, где память ограничена, но достаточно места, или может быть наоборот. В этом контексте, если сравнитьbubble sort и merge sort. Сортировка пузырьков не требует дополнительной памяти, но сортировка слиянием требует дополнительного места. Хотя временная сложность пузырьковой сортировки выше по сравнению с сортировкой слиянием, нам может потребоваться применить пузырьковую сортировку, если программа должна работать в среде, где память очень ограничена.

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

Асимптотический анализ

Асимптотика функции f(n) относится к росту f(n) в виде n становится большим.

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

Хорошее практическое правило состоит в том, что чем медленнее скорость асимптотического роста, тем лучше алгоритм. Хотя это не всегда так.

Например, линейный алгоритм $f(n) = d * n + k$ всегда асимптотически лучше квадратичной, $f(n) = c.n^2 + q$.

Решение рекуррентных уравнений

Повторение - это уравнение или неравенство, которое описывает функцию с точки зрения ее значения на меньших входах. Рецидивы обычно используются в парадигме «разделяй и властвуй».

Рассмотрим T(n) быть временем работы над проблемой размера n.

Если размер проблемы достаточно мал, скажите n < c где c - константа, прямое решение требует постоянного времени, которое записывается как θ(1). Если разделение проблемы дает ряд подзадач с размером$\frac{n}{b}$.

Для решения проблемы необходимо время. a.T(n/b). Если учесть, что время, необходимое для разделения, составляетD(n) а время, необходимое для объединения результатов подзадач, равно C(n), рекуррентное отношение может быть представлено как -

$$T(n)=\begin{cases}\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\theta(1) & if\:n\leqslant c\\a T(\frac{n}{b})+D(n)+C(n) & otherwise\end{cases}$$

Рекуррентное отношение может быть решено с использованием следующих методов -

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

• Recursion Tree Method - В этом методе формируется дерево повторения, где каждый узел представляет стоимость.

• Master’s Theorem - Это еще один важный метод определения сложности рекуррентного отношения.

Амортизированный анализ

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

• Амортизированный анализ позволяет ограничить фактическую стоимость всей последовательности вместо того, чтобы отдельно ограничивать стоимость последовательности операций.

• Амортизированный анализ отличается от анализа среднего случая; вероятность не участвует в амортизированном анализе. Амортизированный анализ гарантирует среднюю производительность каждой операции в худшем случае.

Это не просто инструмент для анализа, это способ размышления о дизайне, поскольку проектирование и анализ тесно связаны.

Агрегатный метод

Агрегатный метод дает глобальное представление о проблеме. В этом методе, еслиn операции требуют наихудшего времени T(n)в итоге. Тогда амортизированная стоимость каждой операции равнаT(n)/n. Хотя разные операции могут занимать разное время, в этом методе не учитывается разная стоимость.

Метод учета

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

Если фактическая стоимость и амортизированная стоимость i^th операция $c_{i}$ и $\hat{c_{l}}$, тогда

$$\displaystyle\sum\limits_{i=1}^n \hat{c_{l}}\geqslant\displaystyle\sum\limits_{i=1}^n c_{i}$$

Возможный метод

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

Если мы выполним n операции, начинающиеся с исходной структуры данных D₀. Рассмотрим,c_i как фактическая стоимость и D_i как структура данных i^thоперация. Потенциальная функция Ф отображается в действительное число Ф (D_i), связанный потенциал D_i. Амортизированная стоимость$\hat{c_{l}}$ можно определить как

$$\hat{c_{l}}=c_{i}+\Phi (D_{i})-\Phi (D_{i-1})$$

Следовательно, общая амортизированная стоимость составляет

$$\displaystyle\sum\limits_{i=1}^n \hat{c_{l}}=\displaystyle\sum\limits_{i=1}^n (c_{i}+\Phi (D_{i})-\Phi (D_{i-1}))=\displaystyle\sum\limits_{i=1}^n c_{i}+\Phi (D_{n})-\Phi (D_{0})$$

Динамический стол

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

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

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

При разработке алгоритма анализ сложности алгоритма является важным аспектом. В основном алгоритмическая сложность связана с ее производительностью, тем, насколько быстро или медленно она работает.

Сложность алгоритма описывает эффективность алгоритма с точки зрения объема памяти, необходимой для обработки данных, и времени обработки.

Сложность алгоритма анализируется с двух точек зрения: Time и Space.

Сложность времени

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

Космическая сложность

Это функция, описывающая объем памяти, занимаемой алгоритмом, с точки зрения размера входных данных для алгоритма. Мы часто говорим о «дополнительной» памяти, не считая памяти, необходимой для хранения самого ввода. Опять же, мы используем естественные (но фиксированной длины) единицы измерения.

Сложность пространства иногда игнорируется, потому что используемое пространство минимально и / или очевидно, однако иногда это становится такой же важной проблемой, как время.

Асимптотические обозначения

Время выполнения алгоритма зависит от набора команд, скорости процессора, скорости дискового ввода-вывода и т. Д. Следовательно, мы оцениваем эффективность алгоритма асимптотически.

Функция времени алгоритма представлена ​​как T(n), где n - размер ввода.

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

• O - Большой О

• Ω - Большая омега

• θ - Большая тета

• o - Маленький О

• ω - Маленькая омега

O: асимптотическая верхняя граница

«О» (Большое О) - наиболее часто используемое обозначение. Функцияf(n) может быть представлен в порядке g(n) то есть O(g(n)), если существует положительное целое число n в виде n₀ и положительная постоянная c такой, что -

$f(n)\leqslant c.g(n)$ за $n > n_{0}$ в любом случае

Следовательно, функция g(n) является верхней границей функции f(n), в виде g(n) растет быстрее, чем f(n).

пример

Рассмотрим заданную функцию, $f(n) = 4.n^3 + 10.n^2 + 5.n + 1$

Учитывая $g(n) = n^3$,

$f(n)\leqslant 5.g(n)$ для всех значений $n > 2$

Следовательно, сложность f(n) можно представить как $O(g(n))$, т.е. $O(n^3)$

Ω: асимптотическая нижняя граница

Мы говорим что $f(n) = \Omega (g(n))$ когда существует постоянная c тот $f(n)\geqslant c.g(n)$ для всех достаточно больших значений n. Вотnположительное целое число. Это означает функциюg оценка снизу функции f; после определенного значенияn, f никогда не пойдет ниже g.

пример

Рассмотрим заданную функцию, $f(n) = 4.n^3 + 10.n^2 + 5.n + 1$.

Учитывая $g(n) = n^3$, $f(n)\geqslant 4.g(n)$ для всех значений $n > 0$.

Следовательно, сложность f(n) можно представить как $\Omega (g(n))$, т.е. $\Omega (n^3)$

θ: асимптотическая жесткая граница

Мы говорим что $f(n) = \theta(g(n))$ когда существуют константы c₁ и c₂ тот $c_{1}.g(n) \leqslant f(n) \leqslant c_{2}.g(n)$ для всех достаточно больших значений n. Вотn положительное целое число.

Это означает функцию g является точной оценкой для функции f.

пример

Рассмотрим заданную функцию, $f(n) = 4.n^3 + 10.n^2 + 5.n + 1$

Учитывая $g(n) = n^3$, $4.g(n) \leqslant f(n) \leqslant 5.g(n)$ для всех больших значений n.

Следовательно, сложность f(n) можно представить как $\theta (g(n))$, т.е. $\theta (n^3)$.

O - обозначение

Асимптотическая оценка сверху, полученная с помощью O-notationможет быть или не быть асимптотически жестким. Граница$2.n^2 = O(n^2)$ асимптотически плотно, но оценка $2.n = O(n^2)$ не является.

Мы используем o-notation для обозначения неасимптотически точной верхней границы.

Формально определяем o(g(n)) (немного о г из п) как набор f(n) = o(g(n)) для любой положительной постоянной $c > 0$ и существует значение $n_{0} > 0$, так что $0 \leqslant f(n) \leqslant c.g(n)$.

Интуитивно в o-notation, функция f(n) становится несущественным по отношению к g(n) в виде nприближается к бесконечности; то есть,

$$\lim_{n \rightarrow \infty}\left(\frac{f(n)}{g(n)}\right) = 0$$

пример

Рассмотрим ту же функцию, $f(n) = 4.n^3 + 10.n^2 + 5.n + 1$

Учитывая $g(n) = n^{4}$,

$$\lim_{n \rightarrow \infty}\left(\frac{4.n^3 + 10.n^2 + 5.n + 1}{n^4}\right) = 0$$

Следовательно, сложность f(n) можно представить как $o(g(n))$, т.е. $o(n^4)$.

ω - Обозначение

Мы используем ω-notationдля обозначения нижней границы, которая не является асимптотически точной. Формально, однако, определимω(g(n)) (мало-омега г н) как набор f(n) = ω(g(n)) для любой положительной постоянной C > 0 и существует значение $n_{0} > 0$, такие что $ 0 \ leqslant cg (n) <f (n) $.

Например, $\frac{n^2}{2} = \omega (n)$, но $\frac{n^2}{2} \neq \omega (n^2)$. Отношение$f(n) = \omega (g(n))$ означает, что существует следующий предел

$$\lim_{n \rightarrow \infty}\left(\frac{f(n)}{g(n)}\right) = \infty$$

То есть, f(n) становится сколь угодно большим относительно g(n) в виде n приближается к бесконечности.

пример

Рассмотрим ту же функцию, $f(n) = 4.n^3 + 10.n^2 + 5.n + 1$

Учитывая $g(n) = n^2$,

$$\lim_{n \rightarrow \infty}\left(\frac{4.n^3 + 10.n^2 + 5.n + 1}{n^2}\right) = \infty$$

Следовательно, сложность f(n) можно представить как $o(g(n))$, т.е. $\omega (n^2)$.

Априори и апостиарный анализ

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

Апостиари-анализ алгоритма означает, что мы выполняем анализ алгоритма только после его запуска в системе. Это напрямую зависит от системы и меняется от системы к системе.

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

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

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

Пространственная сложность разделяет многие черты временной сложности и служит дополнительным способом классификации задач в соответствии с их вычислительными трудностями.

Что такое космическая сложность?

Сложность пространства - это функция, описывающая объем памяти (пространства), занимаемый алгоритмом, с точки зрения количества входных данных для алгоритма.

Мы часто говорим о extra memoryнеобходимо, не считая памяти, необходимой для хранения самого ввода. Опять же, мы используем естественные (но фиксированной длины) единицы измерения.

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

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

Сложность пространства иногда игнорируется, потому что используемое пространство минимально и / или очевидно, однако иногда это становится такой же важной проблемой, как сложность времени.

Определение

Позволять M быть детерминированным Turing machine (TM)который останавливается на всех входах. Космическая сложностьM это функция $f \colon N \rightarrow N$, где f(n) - максимальное количество ячеек ленты и M сканирует любой ввод длины M. Если космическая сложностьM является f(n)можно сказать, что M бежит в космос f(n).

Мы оцениваем пространственную сложность машины Тьюринга, используя асимптотические обозначения.

Позволять $f \colon N \rightarrow R^+$быть функцией. Классы космической сложности можно определить следующим образом:

SPACE = {L | L is a language decided by an O(f(n)) space deterministic TM}

SPACE = {L | L is a language decided by an O(f(n)) space non-deterministic TM}

PSPACE - это класс языков, разрешимых в полиномиальном пространстве на детерминированной машине Тьюринга.

Другими словами, PSPACE = U_k SPACE (n^k)

Теорема Савича

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

Для временной сложности такое моделирование, похоже, требует экспоненциального увеличения времени. Для пространственной сложности эта теорема показывает, что любая недетерминированная машина Тьюринга, использующаяf(n) пространство может быть преобразовано в детерминированную TM, которая использует f²(n) пространство.

Следовательно, теорема Савича утверждает, что для любой функции $f \colon N \rightarrow R^+$, где $f(n) \geqslant n$

NSPACE(f(n)) ⊆ SPACE(f(n))

Отношения между классами сложности

На следующей диаграмме показаны отношения между различными классами сложности.

До сих пор мы не обсуждали классы P и NP в этом руководстве. Об этом мы поговорим позже.

Многие алгоритмы рекурсивны по своей природе для решения данной проблемы, рекурсивно обрабатывая подзадачи.

В divide and conquer approach, проблема делится на более мелкие проблемы, затем более мелкие проблемы решаются независимо и, наконец, решения более мелких проблем объединяются в решение большой проблемы.

Как правило, алгоритмы «разделяй и властвуй» состоят из трех частей:

• Divide the problem на ряд подзадач, которые представляют собой меньшие экземпляры одной и той же проблемы.

• Conquer the sub-problemsрекурсивно решая их. Если они достаточно малы, решите подзадачи как базовые случаи.

• Combine the solutions к подзадачам в решение исходной проблемы.

Плюсы и минусы подхода Divide and Conquer

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

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

Применение подхода «разделяй и властвуй»

Ниже приведены некоторые проблемы, которые решаются с помощью подхода «разделяй и властвуй».

• Нахождение максимума и минимума последовательности чисел
• Умножение матриц Штрассена
• Сортировка слиянием
• Бинарный поиск

Рассмотрим простую задачу, которую можно решить с помощью техники «разделяй и властвуй».

Постановка задачи

Задача Max-Min при анализе алгоритма - найти максимальное и минимальное значение в массиве.

Решение

Чтобы найти максимальное и минимальное числа в заданном массиве numbers[] размера n, можно использовать следующий алгоритм. Сначала мы представляемnaive method а затем мы представим divide and conquer approach.

Наивный метод

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

Algorithm: Max-Min-Element (numbers[]) 
max := numbers[1] 
min := numbers[1] 

for i = 2 to n do 
   if numbers[i] > max then  
      max := numbers[i] 
   if numbers[i] < min then  
      min := numbers[i] 
return (max, min)

Анализ

Число сравнений в наивном методе равно 2n - 2.

Количество сравнений можно уменьшить, используя подход «разделяй и властвуй». Ниже приводится техника.

Подход разделяй и властвуй

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

В данной задаче количество элементов в массиве равно $y - x + 1$, где y Больше или равно x.

$\mathbf{\mathit{Max - Min(x, y)}}$ вернет максимальное и минимальное значения массива $\mathbf{\mathit{numbers[x...y]}}$.

Algorithm: Max - Min(x, y) 
if y – x ≤ 1 then  
   return (max(numbers[x], numbers[y]), min((numbers[x], numbers[y])) 
else 
   (max1, min1):= maxmin(x, ⌊((x + y)/2)⌋) 
   (max2, min2):= maxmin(⌊((x + y)/2) + 1)⌋,y) 
return (max(max1, max2), min(min1, min2))

Анализ

Позволять T(n) быть количеством сравнений, сделанных $\mathbf{\mathit{Max - Min(x, y)}}$, где количество элементов $n = y - x + 1$.

Если T(n) представляет числа, то рекуррентное отношение может быть представлено как

$$T(n) = \begin{cases}T\left(\lfloor\frac{n}{2}\rfloor\right)+T\left(\lceil\frac{n}{2}\rceil\right)+2 & for\: n>2\\1 & for\:n = 2 \\0 & for\:n = 1\end{cases}$$

Предположим, что n в форме силы 2. Следовательно,n = 2^k где k - высота дерева рекурсии.

Так,

$$T(n) = 2.T (\frac{n}{2}) + 2 = 2.\left(\begin{array}{c}2.T(\frac{n}{4}) + 2\end{array}\right) + 2 ..... = \frac{3n}{2} - 2$$

По сравнению с наивным методом в подходе «разделяй и властвуй» количество сравнений меньше. Однако, используя асимптотические обозначения, оба подхода представлены какO(n).

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

Постановка задачи

Проблема сортировки списка чисел немедленно поддается стратегии «разделяй и властвуй»: разделите список на две половины, рекурсивно сортируйте каждую половину, а затем объедините два отсортированных подсписка.

Решение

В этом алгоритме числа хранятся в массиве numbers[]. Вот,p и q представляет начальный и конечный индексы подмассива.

Algorithm: Merge-Sort (numbers[], p, r) 
if p < r then  
q = ⌊(p + r) / 2⌋ 
Merge-Sort (numbers[], p, q) 
    Merge-Sort (numbers[], q + 1, r) 
    Merge (numbers[], p, q, r)

Function: Merge (numbers[], p, q, r)
n1 = q – p + 1 
n2 = r – q 
declare leftnums[1…n1 + 1] and rightnums[1…n2 + 1] temporary arrays 
for i = 1 to n1 
   leftnums[i] = numbers[p + i - 1] 
for j = 1 to n2 
   rightnums[j] = numbers[q+ j] 
leftnums[n1 + 1] = ∞ 
rightnums[n2 + 1] = ∞ 
i = 1 
j = 1 
for k = p to r 
   if leftnums[i] ≤ rightnums[j] 
      numbers[k] = leftnums[i] 
      i = i + 1 
   else
      numbers[k] = rightnums[j] 
      j = j + 1

Анализ

Рассмотрим время работы Merge-Sort как T(n). Следовательно,

$T(n)=\begin{cases}c & if\:n\leqslant 1\\2\:x\:T(\frac{n}{2})+d\:x\:n & otherwise\end{cases}$где c и d - постоянные

Следовательно, используя это рекуррентное соотношение,

$$T(n) = 2^i T(\frac{n}{2^i}) + i.d.n$$

В виде, $i = log\:n,\: T(n) = 2^{log\:n} T(\frac{n}{2^{log\:n}}) + log\:n.d.n$

$=\:c.n + d.n.log\:n$

Следовательно, $T(n) = O(n\:log\:n)$

пример

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

В этой главе мы обсудим другой алгоритм, основанный на методе «разделяй и властвуй».

Постановка задачи

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

Решение

В этом алгоритме мы хотим выяснить, x принадлежит набору чисел, хранящемуся в массиве numbers[]. гдеl и r представляют левый и правый индексы подмассива, в котором должна выполняться операция поиска.

Algorithm: Binary-Search(numbers[], x, l, r)
if l = r then  
   return l  
else 
   m := ⌊(l + r) / 2⌋ 
   if x ≤ numbers[m]  then 
      return Binary-Search(numbers[], x, l, m) 
   else 
      return Binary-Search(numbers[], x, m+1, r)

Анализ

Линейный поиск выполняется в O(n)время. В то время как двоичный поиск дает результат вO(log n) время

Позволять T(n) быть количеством сравнений в наихудшем случае в массиве n элементы.

Следовательно,

$$T(n)=\begin{cases}0 & if\:n= 1\\T(\frac{n}{2})+1 & otherwise\end{cases}$$

Используя это рекуррентное соотношение $T(n) = log\:n$.

Следовательно, бинарный поиск использует $O(log\:n)$ время.

пример

В этом примере мы будем искать элемент 63.

В этой главе сначала мы обсудим общий метод умножения матриц, а позже мы обсудим алгоритм умножения матриц Штрассена.

Постановка задачи

Рассмотрим две матрицы X и Y. Мы хотим вычислить результирующую матрицуZ путем умножения X и Y.

Наивный метод

Сначала мы обсудим наивный метод и его сложность. Здесь мы вычисляемZ = X × Y. Используя наивный метод, две матрицы (X и Y) можно умножить, если порядок этих матриц равен p × q и q × r. Ниже приводится алгоритм.

Algorithm: Matrix-Multiplication (X, Y, Z) 
for i = 1 to p do 
   for j = 1 to r do 
      Z[i,j] := 0 
      for k = 1 to q do 
         Z[i,j] := Z[i,j] + X[i,k] × Y[k,j]

Сложность

Здесь мы предполагаем, что целочисленные операции занимают O(1)время. Есть триforциклы в этом алгоритме, и один вложен в другой. Следовательно, алгоритм принимаетO(n³) время выполнять.

Алгоритм умножения матриц Штрассена

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

Умножение матрицы Штрассена может быть выполнено только на square matrices где n это power of 2. Порядок обеих матрицn × n.

Делить X, Y и Z в четыре (n / 2) × (n / 2) матрицы, как показано ниже -

$Z = \begin{bmatrix}I & J \\K & L \end{bmatrix}$ $X = \begin{bmatrix}A & B \\C & D \end{bmatrix}$ и $Y = \begin{bmatrix}E & F \\G & H \end{bmatrix}$

Используя алгоритм Штрассена, вычислите следующее:

$$M_{1} \: \colon= (A+C) \times (E+F)$$

$$M_{2} \: \colon= (B+D) \times (G+H)$$

$$M_{3} \: \colon= (A-D) \times (E+H)$$

$$M_{4} \: \colon= A \times (F-H)$$

$$M_{5} \: \colon= (C+D) \times (E)$$

$$M_{6} \: \colon= (A+B) \times (H)$$

$$M_{7} \: \colon= D \times (G-E)$$

Потом,

$$I \: \colon= M_{2} + M_{3} - M_{6} - M_{7}$$

$$J \: \colon= M_{4} + M_{6}$$

$$K \: \colon= M_{5} + M_{7}$$

$$L \: \colon= M_{1} - M_{3} - M_{4} - M_{5}$$

Анализ

$T(n)=\begin{cases}c & if\:n= 1\\7\:x\:T(\frac{n}{2})+d\:x\:n^2 & otherwise\end{cases}$где c и d - постоянные

Используя это рекуррентное соотношение, получаем $T(n) = O(n^{log7})$

Следовательно, сложность алгоритма умножения матриц Штрассена равна $O(n^{log7})$.

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

Жадные алгоритмы создают решение по частям, выбирая следующую часть таким образом, чтобы получить немедленную выгоду. Такой подход никогда не пересматривает ранее сделанный выбор. Этот подход в основном используется для решения задач оптимизации. Жадный метод прост в реализации и в большинстве случаев достаточно эффективен. Следовательно, мы можем сказать, что жадный алгоритм - это алгоритмическая парадигма, основанная на эвристике, которая следует за локальным оптимальным выбором на каждом шаге в надежде найти глобальное оптимальное решение.

Во многих задачах он не дает оптимального решения, хотя дает приблизительное (почти оптимальное) решение за разумное время.

Компоненты жадного алгоритма

У жадных алгоритмов есть следующие пять компонентов:

• A candidate set - Из этого набора создается решение.

• A selection function - Используется для выбора лучшего кандидата для добавления в решение.

• A feasibility function - Используется, чтобы определить, можно ли использовать кандидата для внесения вклада в решение.

• An objective function - Используется для присвоения значения решению или частичному решению.

• A solution function - Используется, чтобы указать, было ли достигнуто полное решение.

Области применения

Жадный подход используется для решения многих задач, таких как

• Нахождение кратчайшего пути между двумя вершинами с использованием алгоритма Дейкстры.

• Нахождение минимального остовного дерева в графе с помощью алгоритма Прима / Краскала и т. Д.

Где жадный подход терпит неудачу

Во многих задачах жадный алгоритм не может найти оптимального решения, более того, он может дать наихудшее решение. Такие проблемы, как «Коммивояжер» и «Рюкзак», нельзя решить таким подходом.

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

Проблема с рюкзаком

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

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

Приложения

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

• Поиск наименее расточительного способа разрезания сырья
• оптимизация портфеля
• Проблемы с раскроем

Сценарий проблемы

Вор грабит магазин и может нести максимальный вес Wв рюкзак. В магазине n штук, весi^th товар w_i и его прибыль p_i. Какие предметы должен взять вор?

В этом контексте предметы следует выбирать таким образом, чтобы вор нес те предметы, за которые он получит максимальную прибыль. Следовательно, цель вора - максимизировать прибыль.

В зависимости от характера предметов проблемы с ранцем классифицируются как

• Дробный рюкзак
• Knapsack

Дробный рюкзак

В этом случае предметы можно разбить на более мелкие части, поэтому вор может выбирать части предметов.

Согласно постановке задачи,

• Есть n товары в магазине

• Вес i^th вещь $w_{i} > 0$

• Прибыль за i^th вещь $p_{i} > 0$ и

• Вместимость ранца W

В этой версии задачи о ранце предметы можно разбивать на более мелкие части. Значит, вор может забрать только частьx_i из i^th вещь.

$$0 \leqslant x_{i} \leqslant 1$$

В i^th товар вносит свой вклад в вес $x_{i}.w_{i}$ к общему весу в рюкзаке и прибыли $x_{i}.p_{i}$ к общей прибыли.

Следовательно, цель этого алгоритма -

$$maximize\:\displaystyle\sum\limits_{n=1}^n (x_{i}.p_{}i)$$

при условии ограничения,

$$\displaystyle\sum\limits_{n=1}^n (x_{i}.w_{}i) \leqslant W$$

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

Таким образом, оптимальное решение может быть получено

$$\displaystyle\sum\limits_{n=1}^n (x_{i}.w_{}i) = W$$

В этом контексте сначала нам нужно отсортировать эти элементы в соответствии со значением $\frac{p_{i}}{w_{i}}$, так что $\frac{p_{i}+1}{w_{i}+1}$ ≤ $\frac{p_{i}}{w_{i}}$. Вот,x представляет собой массив для хранения доли элементов.

Algorithm: Greedy-Fractional-Knapsack (w[1..n], p[1..n], W) 
for i = 1 to n 
   do x[i] = 0 
weight = 0 
for i = 1 to n 
   if weight + w[i] ≤ W then  
      x[i] = 1 
      weight = weight + w[i] 
   else 
      x[i] = (W - weight) / w[i] 
      weight = W 
      break 
return x

Анализ

Если предоставленные товары уже отсортированы в порядке убывания $\mathbf{\frac{p_{i}}{w_{i}}}$, тогда цикл whileloop занимает время в O(n); Таким образом, общее время, включая сортировку, составляетO(n logn).

пример

Будем считать, что вместимость ранца W = 60 и список предоставленных предметов показан в следующей таблице -

Вещь	А	B	C	D
Прибыль	280	100	120	120
Вес	40	10	20	24
Соотношение $(\frac{p_{i}}{w_{i}})$	7	10	6	5

Поскольку предоставленные товары не отсортированы по $\mathbf{\frac{p_{i}}{w_{i}}}$. После сортировки элементы выглядят так, как показано в следующей таблице.

Вещь	B	А	C	D
Прибыль	100	280	120	120
Вес	10	40	20	24
Соотношение $(\frac{p_{i}}{w_{i}})$	10	7	6	5

Решение

После сортировки всех предметов по $\frac{p_{i}}{w_{i}}$. Прежде всегоB выбирается как вес Bменьше вместимости ранца. Далее пунктA выбран, так как доступная вместимость ранца больше, чем вес A. В настоящее время,Cвыбирается следующим элементом. Однако нельзя выбрать предмет целиком, так как оставшаяся вместимость рюкзака меньше весаC.

Следовательно, доля C (т.е. (60 - 50) / 20) выбрано.

Теперь вместимость ранца равна выбранным предметам. Следовательно, выбрать больше нельзя.

Общий вес выбранных предметов составляет 10 + 40 + 20 * (10/20) = 60

И общая прибыль составляет 100 + 280 + 120 * (10/20) = 380 + 60 = 440

Это оптимальное решение. Мы не можем получить больше прибыли, выбирая любую другую комбинацию предметов.

Постановка задачи

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

Решение

Рассмотрим набор nзаданные задания, которые связаны со сроками, и прибыль получается, если работа завершена к установленному сроку. Эти работы нужно заказывать таким образом, чтобы получить максимальную прибыль.

Может случиться так, что все поставленные работы не будут выполнены в установленные сроки.

Допустим, срок i^th работа J_i является d_i и прибыль, полученная от этой работы, составляет p_i. Следовательно, оптимальное решение этого алгоритма - возможное решение с максимальной прибылью.

Таким образом, $D(i) > 0$ за $1 \leqslant i \leqslant n$.

Первоначально эти работы упорядочиваются по прибыли, т.е. $p_{1} \geqslant p_{2} \geqslant p_{3} \geqslant \:... \: \geqslant p_{n}$.

Algorithm: Job-Sequencing-With-Deadline (D, J, n, k) 
D(0) := J(0) := 0 
k := 1 
J(1) := 1   // means first job is selected 
for i = 2 … n do 
   r := k 
   while D(J(r)) > D(i) and D(J(r)) ≠ r do 
      r := r – 1 
   if D(J(r)) ≤ D(i) and D(i) > r then 
      for l = k … r + 1 by -1 do 
         J(l + 1) := J(l) 
         J(r + 1) := i 
         k := k + 1

Анализ

В этом алгоритме мы используем два цикла, один внутри другого. Следовательно, сложность этого алгоритма равна$O(n^2)$.

пример

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

Работа	J1	J2	J3	J4	J5
Крайний срок	2	1	3	2	1
Прибыль	60	100	20	40	20

Решение

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

Работа	J2	J1	J4	J3	J5
Крайний срок	1	2	2	3	1
Прибыль	100	60	40	20	20

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

• Следующий, J₁ выбран, так как он дает больше прибыли по сравнению с J₄.

• В следующие часы, J₄ не может быть выбран, поскольку его крайний срок истек, поэтому J₃ выбирается по мере выполнения в установленный срок.

• Работа J₅ отклоняется, так как он не может быть выполнен в установленный срок.

Таким образом, решение представляет собой последовательность работ (J₂, J₁, J₃), которые выполняются в срок и приносят максимальную прибыль.

Общая прибыль этой последовательности составляет 100 + 60 + 20 = 180.

Объедините набор отсортированных файлов разной длины в один отсортированный файл. Нам нужно найти оптимальное решение, при котором итоговый файл будет сгенерирован за минимальное время.

Если указано количество отсортированных файлов, есть много способов объединить их в один отсортированный файл. Это слияние может быть выполнено попарно. Следовательно, этот тип слияния называется2-way merge patterns.

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

Чтобы объединить p-record file и q-record file требует возможно p + q запись ходов, очевидный выбор - объединять два самых маленьких файла вместе на каждом шаге.

Шаблоны двустороннего слияния могут быть представлены двоичными деревьями слияния. Рассмотрим наборn отсортированные файлы {f₁, f₂, f₃, …, f_n}. Первоначально каждый элемент этого рассматривается как двоичное дерево с одним узлом. Чтобы найти это оптимальное решение, используется следующий алгоритм.

Algorithm: TREE (n)  
for i := 1 to n – 1 do  
   declare new node  
   node.leftchild := least (list) 
   node.rightchild := least (list) 
   node.weight) := ((node.leftchild).weight) + ((node.rightchild).weight)  
   insert (list, node);  
return least (list);

В конце этого алгоритма вес корневого узла представляет оптимальную стоимость.

пример

Рассмотрим данные файлы, f ₁ , f ₂ , f ₃ , f ₄ и f ₅ с количеством элементов 20, 30, 10, 5 и 30 соответственно.

Если операции слияния выполняются согласно заданной последовательности, то

M₁ = merge f₁ and f₂ => 20 + 30 = 50

M₂ = merge M₁ and f₃ => 50 + 10 = 60

M₃ = merge M₂ and f₄ => 60 + 5 = 65

M₄ = merge M₃ and f₅ => 65 + 30 = 95

Следовательно, общее количество операций равно

50 + 60 + 65 + 95 = 270

Возникает вопрос: а есть ли лучшее решение?

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

f₄, f₃, f₁, f₂, f₅

Следовательно, с этой последовательностью можно выполнять операции слияния.

M₁ = merge f₄ and f₃ => 5 + 10 = 15

M₂ = merge M₁ and f₁ => 15 + 20 = 35

M₃ = merge M₂ and f₂ => 35 + 30 = 65

M₄ = merge M₃ and f₅ => 65 + 30 = 95

Следовательно, общее количество операций равно

15 + 35 + 65 + 95 = 210

Очевидно, это лучше, чем предыдущее.

В этом контексте мы собираемся решить задачу с помощью этого алгоритма.

Начальный набор

Шаг 1

Шаг 2

Шаг 3

Шаг-4

Следовательно, для решения требуется 15 + 35 + 60 + 95 = 205 сравнений.

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

Два основных свойства проблемы предполагают, что данную проблему можно решить с помощью динамического программирования. Эти свойстваoverlapping sub-problems and optimal substructure.

Перекрывающиеся подзадачи

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

Например, у двоичного поиска нет перекрывающихся подзадач. В то время как рекурсивная программа чисел Фибоначчи имеет много перекрывающихся подзадач.

Оптимальная подструктура

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

Например, задача кратчайшего пути имеет следующее свойство оптимальной подструктуры:

Если узел x лежит на кратчайшем пути от исходного узла u к узлу назначения v, то кратчайший путь из u к v это комбинация кратчайшего пути из u к x, и кратчайший путь от x к v.

Стандартные алгоритмы кратчайшего пути по всем парам, такие как Floyd-Warshall и Bellman-Ford, являются типичными примерами динамического программирования.

Этапы подхода к динамическому программированию

Алгоритм динамического программирования разработан с использованием следующих четырех шагов -

• Охарактеризуйте структуру оптимального решения.
• Рекурсивно определить значение оптимального решения.
• Вычислите значение оптимального решения, как правило, снизу вверх.
• Постройте оптимальное решение из вычисленной информации.

Применение подхода динамического программирования

• Умножение матричной цепочки
• Самая длинная общая подпоследовательность
• Задача коммивояжера

В этом уроке ранее мы обсуждали задачу Fractional Knapsack с использованием жадного подхода. Мы показали, что жадный подход дает оптимальное решение для Fractional Knapsack. Однако в этой главе будет рассмотрена задача о рюкзаке 0-1 и ее анализ.

В рюкзаке 0-1 предметы нельзя сломать, что означает, что вор должен забрать предмет целиком или оставить его. Это причина того, что он назван «рюкзаком 0-1».

Следовательно, в случае ранца 0-1 значение x_i может быть 0 или же 1, где остальные ограничения остаются прежними.

0-1 Рюкзак не может быть решен с помощью жадного подхода. Жадный подход не гарантирует оптимального решения. Во многих случаях жадный подход может дать оптимальное решение.

Следующие примеры подтверждают наше утверждение.

Пример-1

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

Вещь	А	B	C	D
Прибыль	24	18	18	10
Вес	24	10	10	7

Без учета прибыли на единицу веса (p_i/w_i), если мы применим жадный подход к решению этой проблемы, первый пункт Aбудет выбран , как это будет способствовать макс _я мама прибыль среди всех элементов.

После выбора товара A, больше ни один элемент не будет выбран. Следовательно, для данного набора статей общая прибыль равна24. В то время как оптимальное решение может быть достигнуто путем выбора предметов,B и C, где общая прибыль составляет 18 + 18 = 36.

Пример-2

Вместо выбора элементов на основе общей выгоды, в этом примере элементы выбираются на основе отношения p _i / w _i . Предположим, что вместимость ранца W = 60, а его предметы показаны в следующей таблице.

Вещь	А	B	C
Цена	100	280	120
Вес	10	40	20
Соотношение	10	7	6

Используя жадный подход, первый пункт Aвыбрано. Затем следующий элементBвыбран. Следовательно, общая прибыль составляет100 + 280 = 380. Однако оптимальное решение этого экземпляра может быть достигнуто путем выбора элементов,B и C, где общая прибыль 280 + 120 = 400.

Следовательно, можно сделать вывод, что жадный подход может не дать оптимального решения.

Чтобы решить 0-1 Рюкзак, требуется подход динамического программирования.

Постановка задачи

Вор ограбил магазин и может нести максимальный _я ТЗ весаWв рюкзак. Естьn предметы и вес i^th товар w_i и прибыль от выбора этого элемента составляет p_i. Какие предметы должен взять вор?

Подход динамического программирования

Позволять i быть элементом с наибольшим номером в оптимальном решении S за Wдолларов. потомS^' = S - {i} оптимальное решение для W - w_i долларов и ценность решения S является V_i плюс стоимость подзадачи.

Мы можем выразить этот факт в следующей формуле: определить c[i, w] быть решением для предметов 1,2, … , iи макс _я вес мамыw.

Алгоритм принимает следующие входные данные

• Макс _я вес мамыW

• Количество предметов n

• Две последовательности v = <v₁, v₂, …, v_n> и w = <w₁, w₂, …, w_n>

Dynamic-0-1-knapsack (v, w, n, W) 
for w = 0 to W do 
   c[0, w] = 0 
for i = 1 to n do 
   c[i, 0] = 0 
   for w = 1 to W do 
      if wi ≤ w then 
         if vi + c[i-1, w-wi] then 
            c[i, w] = vi + c[i-1, w-wi] 
         else c[i, w] = c[i-1, w] 
      else 
         c[i, w] = c[i-1, w]

Набор предметов, которые нужно взять, можно вывести из таблицы, начиная с c[n, w] и проследить назад, откуда пришли оптимальные значения.

Если c [i, w] = c [i-1, w] , то элементi не является частью решения, и мы продолжаем трассировку с c[i-1, w]. В противном случае элементi является частью решения, и мы продолжаем трассировку с c[i-1, w-W].

Анализ

Этот алгоритм берет θ ( n , w ) раз, поскольку таблица c имеет ( n + 1). ( W + 1) записей, где для вычисления каждой записи требуется θ (1) времени.

Самая длинная общая проблема подпоследовательности - найти самую длинную последовательность, которая существует в обеих данных строках.

Подпоследовательность

Рассмотрим последовательность S = <s ₁ , s ₂ , s ₃ , s ₄ ,…, s _n >.

Последовательность Z = <z ₁ , z ₂ , z ₃ , z ₄ ,…, z _m > над S называется подпоследовательностью S, если и только если она может быть получена из S удаления некоторых элементов.

Общая подпоследовательность

Предположим, X и Yдве последовательности над конечным множеством элементов. Мы можем сказать чтоZ является общей подпоследовательностью X и Y, если Z является подпоследовательностью обоих X и Y.

Самая длинная общая подпоследовательность

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

Самая длинная общая проблема подпоследовательности - это классическая проблема информатики, основа программ сравнения данных, таких как утилита diff, и находящая применение в биоинформатике. Он также широко используется системами контроля версий, такими как SVN и Git, для согласования нескольких изменений, внесенных в коллекцию файлов, контролируемую версиями.

Наивный метод

Позволять X быть последовательностью длины m и Y последовательность длины n. Проверьте каждую подпоследовательностьX является ли это подпоследовательностью Y, и вернуть самую длинную найденную общую подпоследовательность.

Есть 2^m подпоследовательности X. Проверка последовательностей на предмет того, является ли она подпоследовательностьюY берет O(n)время. Таким образом, наивный алгоритм взял быO(n2^m) время.

Динамическое программирование

Пусть X = <x ₁ , x ₂ , x ₃ ,…, x _m > и Y = <y ₁ , y ₂ , y ₃ ,…, y _n > - последовательности. Для вычисления длины элемента используется следующий алгоритм.

В этой процедуре таблица C[m, n] вычисляется в основном порядке строк, а другая таблица B[m,n] вычисляется для построения оптимального решения.

Algorithm: LCS-Length-Table-Formulation (X, Y)
m := length(X) 
n := length(Y) 
for i = 1 to m do 
   C[i, 0] := 0 
for j = 1 to n do 
   C[0, j] := 0 
for i = 1 to m do 
   for j = 1 to n do 
      if xi = yj 
         C[i, j] := C[i - 1, j - 1] + 1 
         B[i, j] := ‘D’ 
      else 
         if C[i -1, j] ≥ C[i, j -1] 
            C[i, j] := C[i - 1, j] + 1 
            B[i, j] := ‘U’ 
         else 
         C[i, j] := C[i, j - 1]
         B[i, j] := ‘L’ 
return C and B

Algorithm: Print-LCS (B, X, i, j)
if i = 0 and j = 0 
   return  
if B[i, j] = ‘D’ 
   Print-LCS(B, X, i-1, j-1) 
   Print(xi) 
else if B[i, j] = ‘U’ 
   Print-LCS(B, X, i-1, j) 
else 
   Print-LCS(B, X, i, j-1)

Этот алгоритм распечатает самую длинную общую подпоследовательность X и Y.

Анализ

Чтобы заполнить таблицу, внешний for цикл повторяется m раз и внутренний for цикл повторяется nраз. Следовательно, сложность алгоритма O (m, n) , гдеm и n - это длина двух струн.

пример

В этом примере у нас есть две строки X = BACDB и Y = BDCB найти самую длинную общую подпоследовательность.

Следуя алгоритму LCS-Length-Table-Formulation (как указано выше), мы вычислили таблицу C (показанную слева) и таблицу B (показанную справа).

В таблице B вместо «D», «L» и «U» мы используем диагональную стрелку, стрелку влево и стрелку вверх соответственно. После создания таблицы B LCS определяется функцией LCS-Print. Результат - BCB.

А spanning tree - это подмножество неориентированного графа, все вершины которого соединены минимальным числом ребер.

Если все вершины соединены в графе, то существует хотя бы одно остовное дерево. В графе может существовать более одного остовного дерева.

Свойства

• Остовное дерево не имеет цикла.
• В любую вершину можно попасть из любой другой вершины.

пример

На следующем графике выделенные ребра образуют остовное дерево.

Минимальное связующее дерево

А Minimum Spanning Tree (MST)- это подмножество ребер связного взвешенного неориентированного графа, которое соединяет все вершины вместе с минимально возможным общим весом ребер. Для получения MST можно использовать алгоритм Прима или алгоритм Крускала. Следовательно, в этой главе мы обсудим алгоритм Прима.

Как мы уже говорили, один граф может иметь более одного остовного дерева. Если естьn количество вершин, остовное дерево должно иметь n - 1количество ребер. В этом контексте, если каждое ребро графа связано с весом и существует более одного остовного дерева, нам нужно найти минимальное остовное дерево графа.

Более того, если существуют какие-либо повторяющиеся взвешенные ребра, граф может иметь несколько минимальных остовных деревьев.

На приведенном выше графике мы показали остовное дерево, хотя это не минимальное остовное дерево. Стоимость этого остовного дерева составляет (5 + 7 + 3 + 3 + 5 + 8 + 3 + 4) = 38.

Мы будем использовать алгоритм Прима, чтобы найти минимальное остовное дерево.

Алгоритм Прима

Алгоритм Прима - это жадный подход к поиску минимального остовного дерева. В этом алгоритме для формирования MST мы можем начать с произвольной вершины.

Algorithm: MST-Prim’s (G, w, r) 
for each u є G.V 
   u.key = ∞ 
   u.∏ = NIL 
r.key = 0 
Q = G.V 
while Q ≠ Ф 
   u = Extract-Min (Q) 
   for each v є G.adj[u] 
      if each v є Q and w(u, v) < v.key 
         v.∏ = u 
         v.key = w(u, v)

Функция Extract-Min возвращает вершину с минимальной стоимостью ребра. Эта функция работает с min-heap.

пример

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

Вершина 3 соединен с вершиной 1 с минимальной стоимостью края, следовательно, край (1, 2) добавляется в остовное дерево.

Далее край (2, 3) считается как минимум среди ребер {(1, 2), (2, 3), (3, 4), (3, 7)}.

На следующем этапе получаем преимущество (3, 4) и (2, 4)с минимальной стоимостью. Край(3, 4) выбирается случайным образом.

Аналогично ребра (4, 5), (5, 7), (7, 8), (6, 8) и (6, 9)выбраны. Поскольку все вершины посещены, алгоритм останавливается.

Стоимость остовного дерева составляет (2 + 2 + 3 + 2 + 5 + 2 + 3 + 4) = 23. В этом графе больше нет остовного дерева со стоимостью меньше, чем 23.

Алгоритм Дейкстры

Алгоритм Дейкстры решает задачу поиска кратчайших путей с одним источником на ориентированном взвешенном графе G = (V, E) , где все ребра неотрицательны (т. Е. W (u, v) ≥ 0 для каждого ребра (u, v ) Є E ).

В следующем алгоритме мы будем использовать одну функцию Extract-Min(), который извлекает узел с наименьшим ключом.

Algorithm: Dijkstra’s-Algorithm (G, w, s) 
for each vertex v Є G.V  
   v.d := ∞ 
   v.∏ := NIL 
s.d := 0 
S := Ф 
Q := G.V 
while Q ≠ Ф 
   u := Extract-Min (Q) 
   S := S U {u} 
   for each vertex v Є G.adj[u] 
      if v.d > u.d + w(u, v) 
         v.d := u.d + w(u, v) 
         v.∏ := u

Анализ

Сложность этого алгоритма полностью зависит от реализации функции Extract-Min. Если функция extract min реализована с использованием линейного поиска, сложность этого алгоритма равнаO(V² + E).

В этом алгоритме, если мы используем min-heap, на котором Extract-Min() функция работает, чтобы вернуть узел из Q с наименьшим ключом сложность этого алгоритма может быть уменьшена еще больше.

пример

Рассмотрим вершину 1 and 9 as the start and destination vertex respectively. Initially, all the vertices except the start vertex are marked by ∞ and the start vertex is marked by 0.

Vertex	Initial	Step1 V1	Step2 V3	Step3 V2	Step4 V4	Step5 V5	Step6 V7	Step7 V8	Step8 V6
1	0	0	0	0	0	0	0	0	0
2	∞	5	4	4	4	4	4	4	4
3	∞	2	2	2	2	2	2	2	2
4	∞	∞	∞	7	7	7	7	7	7
5	∞	∞	∞	11	9	9	9	9	9
6	∞	∞	∞	∞	∞	17	17	16	16
7	∞	∞	11	11	11	11	11	11	11
8	∞	∞	∞	∞	∞	16	13	13	13
9	∞	∞	∞	∞	∞	∞	∞	∞	20

Hence, the minimum distance of vertex 9 from vertex 1 is 20. And the path is

1→ 3→ 7→ 8→ 6→ 9

This path is determined based on predecessor information.

Bellman Ford Algorithm

This algorithm solves the single source shortest path problem of a directed graph G = (V, E) in which the edge weights may be negative. Moreover, this algorithm can be applied to find the shortest path, if there does not exist any negative weighted cycle.

Algorithm: Bellman-Ford-Algorithm (G, w, s) 
for each vertex v Є G.V  
   v.d := ∞ 
   v.∏ := NIL 
s.d := 0 
for i = 1 to |G.V| - 1 
   for each edge (u, v) Є G.E 
      if v.d > u.d + w(u, v) 
         v.d := u.d +w(u, v) 
         v.∏ := u 
for each edge (u, v) Є G.E 
   if v.d > u.d + w(u, v) 
      return FALSE 
return TRUE

Analysis

The first for loop is used for initialization, which runs in O(V) times. The next for loop runs |V - 1| passes over the edges, which takes O(E) times.

Hence, Bellman-Ford algorithm runs in O(V, E) time.

Example

The following example shows how Bellman-Ford algorithm works step by step. This graph has a negative edge but does not have any negative cycle, hence the problem can be solved using this technique.

At the time of initialization, all the vertices except the source are marked by ∞ and the source is marked by 0.

In the first step, all the vertices which are reachable from the source are updated by minimum cost. Hence, vertices a and h are updated.

In the next step, vertices a, b, f and e are updated.

Following the same logic, in this step vertices b, f, c and g are updated.

Here, vertices c and d are updated.

Hence, the minimum distance between vertex s and vertex d is 20.

Based on the predecessor information, the path is s→ h→ e→ g→ c→ d

A multistage graph G = (V, E) is a directed graph where vertices are partitioned into k (where k > 1) number of disjoint subsets S = {s₁,s₂,…,s_k} such that edge (u, v) is in E, then u Є s_i and v Є s_{1 + 1} for some subsets in the partition and |s₁| = |s_k| = 1.

The vertex s Є s₁ is called the source and the vertex t Є s_k is called sink.

G is usually assumed to be a weighted graph. In this graph, cost of an edge (i, j) is represented by c(i, j). Hence, the cost of path from source s to sink t is the sum of costs of each edges in this path.

The multistage graph problem is finding the path with minimum cost from source s to sink t.

Example

Consider the following example to understand the concept of multistage graph.

According to the formula, we have to calculate the cost (i, j) using the following steps

Step-1: Cost (K-2, j)

In this step, three nodes (node 4, 5. 6) are selected as j. Hence, we have three options to choose the minimum cost at this step.

Cost(3, 4) = min {c(4, 7) + Cost(7, 9),c(4, 8) + Cost(8, 9)} = 7

Cost(3, 5) = min {c(5, 7) + Cost(7, 9),c(5, 8) + Cost(8, 9)} = 5

Cost(3, 6) = min {c(6, 7) + Cost(7, 9),c(6, 8) + Cost(8, 9)} = 5

Step-2: Cost (K-3, j)

Two nodes are selected as j because at stage k - 3 = 2 there are two nodes, 2 and 3. So, the value i = 2 and j = 2 and 3.

Cost(2, 2) = min {c(2, 4) + Cost(4, 8) + Cost(8, 9),c(2, 6) +

Cost(6, 8) + Cost(8, 9)} = 8

Cost(2, 3) = {c(3, 4) + Cost(4, 8) + Cost(8, 9), c(3, 5) + Cost(5, 8)+ Cost(8, 9), c(3, 6) + Cost(6, 8) + Cost(8, 9)} = 10

Step-3: Cost (K-4, j)

Cost (1, 1) = {c(1, 2) + Cost(2, 6) + Cost(6, 8) + Cost(8, 9), c(1, 3) + Cost(3, 5) + Cost(5, 8) + Cost(8, 9))} = 12

c(1, 3) + Cost(3, 6) + Cost(6, 8 + Cost(8, 9))} = 13

Hence, the path having the minimum cost is 1→ 3→ 5→ 8→ 9.

Problem Statement

A traveler needs to visit all the cities from a list, where distances between all the cities are known and each city should be visited just once. What is the shortest possible route that he visits each city exactly once and returns to the origin city?

Solution

Travelling salesman problem is the most notorious computational problem. We can use brute-force approach to evaluate every possible tour and select the best one. For n number of vertices in a graph, there are (n - 1)! number of possibilities.

Instead of brute-force using dynamic programming approach, the solution can be obtained in lesser time, though there is no polynomial time algorithm.

Let us consider a graph G = (V, E), where V is a set of cities and E is a set of weighted edges. An edge e(u, v) represents that vertices u and v are connected. Distance between vertex u and v is d(u, v), which should be non-negative.

Suppose we have started at city 1 and after visiting some cities now we are in city j. Hence, this is a partial tour. We certainly need to know j, since this will determine which cities are most convenient to visit next. We also need to know all the cities visited so far, so that we don't repeat any of them. Hence, this is an appropriate sub-problem.

For a subset of cities S Є {1, 2, 3, ... , n} that includes 1, and j Є S, let C(S, j) be the length of the shortest path visiting each node in S exactly once, starting at 1 and ending at j.

When |S| > 1, we define C(S, 1) = ∝ since the path cannot start and end at 1.

Now, let express C(S, j) in terms of smaller sub-problems. We need to start at 1 and end at j. We should select the next city in such a way that

$$C(S, j) = min \:C(S - \lbrace j \rbrace, i) + d(i, j)\:where\: i\in S \: and\: i \neq jc(S, j) = minC(s- \lbrace j \rbrace, i)+ d(i,j) \:where\: i\in S \: and\: i \neq j $$

Algorithm: Traveling-Salesman-Problem 
C ({1}, 1) = 0 
for s = 2 to n do 
   for all subsets S Є {1, 2, 3, … , n} of size s and containing 1 
      C (S, 1) = ∞ 
   for all j Є S and j ≠ 1 
      C (S, j) = min {C (S – {j}, i) + d(i, j) for i Є S and i ≠ j} 
Return minj C ({1, 2, 3, …, n}, j) + d(j, i)

Analysis

There are at the most $2^n.n$ sub-problems and each one takes linear time to solve. Therefore, the total running time is $O(2^n.n^2)$.

Example

In the following example, we will illustrate the steps to solve the travelling salesman problem.

From the above graph, the following table is prepared.

	1	2	3	4
1	0	10	15	20
2	5	0	9	10
3	6	13	0	12
4	8	8	9	0

S = Φ

$$\small Cost (2,\Phi,1) = d (2,1) = 5\small Cost(2,\Phi,1)=d(2,1)=5$$

$$\small Cost (3,\Phi,1) = d (3,1) = 6\small Cost(3,\Phi,1)=d(3,1)=6$$

$$\small Cost (4,\Phi,1) = d (4,1) = 8\small Cost(4,\Phi,1)=d(4,1)=8$$

S = 1

$$\small Cost (i,s) = min \lbrace Cost (j,s – (j)) + d [i,j]\rbrace\small Cost (i,s)=min \lbrace Cost (j,s)-(j))+ d [i,j]\rbrace$$

$$\small Cost (2,\lbrace 3 \rbrace,1) = d [2,3] + Cost (3,\Phi,1) = 9 + 6 = 15cost(2,\lbrace3 \rbrace,1)=d[2,3]+cost(3,\Phi ,1)=9+6=15$$

$$\small Cost (2,\lbrace 4 \rbrace,1) = d [2,4] + Cost (4,\Phi,1) = 10 + 8 = 18cost(2,\lbrace4 \rbrace,1)=d[2,4]+cost(4,\Phi,1)=10+8=18$$

$$\small Cost (3,\lbrace 2 \rbrace,1) = d [3,2] + Cost (2,\Phi,1) = 13 + 5 = 18cost(3,\lbrace2 \rbrace,1)=d[3,2]+cost(2,\Phi,1)=13+5=18$$

$$\small Cost (3,\lbrace 4 \rbrace,1) = d [3,4] + Cost (4,\Phi,1) = 12 + 8 = 20cost(3,\lbrace4 \rbrace,1)=d[3,4]+cost(4,\Phi,1)=12+8=20$$

$$\small Cost (4,\lbrace 3 \rbrace,1) = d [4,3] + Cost (3,\Phi,1) = 9 + 6 = 15cost(4,\lbrace3 \rbrace,1)=d[4,3]+cost(3,\Phi,1)=9+6=15$$

$$\small Cost (4,\lbrace 2 \rbrace,1) = d [4,2] + Cost (2,\Phi,1) = 8 + 5 = 13cost(4,\lbrace2 \rbrace,1)=d[4,2]+cost(2,\Phi,1)=8+5=13$$

S = 2

$$\small Cost(2, \lbrace 3, 4 \rbrace, 1)=\begin{cases}d[2, 3] + Cost(3, \lbrace 4 \rbrace, 1) = 9 + 20 = 29\\d[2, 4] + Cost(4, \lbrace 3 \rbrace, 1) = 10 + 15 = 25=25\small Cost (2,\lbrace 3,4 \rbrace,1)\\\lbrace d[2,3]+ \small cost(3,\lbrace4\rbrace,1)=9+20=29d[2,4]+ \small Cost (4,\lbrace 3 \rbrace ,1)=10+15=25\end{cases}= 25$$

$$\small Cost(3, \lbrace 2, 4 \rbrace, 1)=\begin{cases}d[3, 2] + Cost(2, \lbrace 4 \rbrace, 1) = 13 + 18 = 31\\d[3, 4] + Cost(4, \lbrace 2 \rbrace, 1) = 12 + 13 = 25=25\small Cost (3,\lbrace 2,4 \rbrace,1)\\\lbrace d[3,2]+ \small cost(2,\lbrace4\rbrace,1)=13+18=31d[3,4]+ \small Cost (4,\lbrace 2 \rbrace ,1)=12+13=25\end{cases}= 25$$

$$\small Cost(4, \lbrace 2, 3 \rbrace, 1)=\begin{cases}d[4, 2] + Cost(2, \lbrace 3 \rbrace, 1) = 8 + 15 = 23\\d[4, 3] + Cost(3, \lbrace 2 \rbrace, 1) = 9 + 18 = 27=23\small Cost (4,\lbrace 2,3 \rbrace,1)\\\lbrace d[4,2]+ \small cost(2,\lbrace3\rbrace,1)=8+15=23d[4,3]+ \small Cost (3,\lbrace 2 \rbrace ,1)=9+18=27\end{cases}= 23$$

S = 3

$$\small Cost(1, \lbrace 2, 3, 4 \rbrace, 1)=\begin{cases}d[1, 2] + Cost(2, \lbrace 3, 4 \rbrace, 1) = 10 + 25 = 35\\d[1, 3] + Cost(3, \lbrace 2, 4 \rbrace, 1) = 15 + 25 = 40\\d[1, 4] + Cost(4, \lbrace 2, 3 \rbrace, 1) = 20 + 23 = 43=35 cost(1,\lbrace 2,3,4 \rbrace),1)\\d[1,2]+cost(2,\lbrace 3,4 \rbrace,1)=10+25=35\\d[1,3]+cost(3,\lbrace 2,4 \rbrace,1)=15+25=40\\d[1,4]+cost(4,\lbrace 2,3 \rbrace ,1)=20+23=43=35\end{cases}$$

The minimum cost path is 35.

Start from cost {1, {2, 3, 4}, 1}, we get the minimum value for d [1, 2]. When s = 3, select the path from 1 to 2 (cost is 10) then go backwards. When s = 2, we get the minimum value for d [4, 2]. Select the path from 2 to 4 (cost is 10) then go backwards.

When s = 1, we get the minimum value for d [4, 3]. Selecting path 4 to 3 (cost is 9), then we shall go to then go to s = Φ step. We get the minimum value for d [3, 1] (cost is 6).

A Binary Search Tree (BST) is a tree where the key values are stored in the internal nodes. The external nodes are null nodes. The keys are ordered lexicographically, i.e. for each internal node all the keys in the left sub-tree are less than the keys in the node, and all the keys in the right sub-tree are greater.

When we know the frequency of searching each one of the keys, it is quite easy to compute the expected cost of accessing each node in the tree. An optimal binary search tree is a BST, which has minimal expected cost of locating each node

Search time of an element in a BST is O(n), whereas in a Balanced-BST search time is O(log n). Again the search time can be improved in Optimal Cost Binary Search Tree, placing the most frequently used data in the root and closer to the root element, while placing the least frequently used data near leaves and in leaves.

Here, the Optimal Binary Search Tree Algorithm is presented. First, we build a BST from a set of provided n number of distinct keys < k₁, k₂, k₃, ... k_n >. Here we assume, the probability of accessing a key K_i is p_i. Some dummy keys (d₀, d₁, d₂, ... d_n) are added as some searches may be performed for the values which are not present in the Key set K. We assume, for each dummy key d_i probability of access is q_i.

Optimal-Binary-Search-Tree(p, q, n) 
e[1…n + 1, 0…n],  
w[1…n + 1, 0…n], 
root[1…n + 1, 0…n]  
for i = 1 to n + 1 do 
   e[i, i - 1] := qi - 1 
   w[i, i - 1] := qi - 1  
for l = 1 to n do 
   for i = 1 to n – l + 1 do 
      j = i + l – 1 e[i, j] := ∞ 
      w[i, i] := w[i, i -1] + pj + qj 
      for r = i to j do 
         t := e[i, r - 1] + e[r + 1, j] + w[i, j] 
         if t < e[i, j] 
            e[i, j] := t 
            root[i, j] := r 
return e and root

Analysis

The algorithm requires O (n³) time, since three nested for loops are used. Each of these loops takes on at most n values.

Example

Considering the following tree, the cost is 2.80, though this is not an optimal result.

Node	Depth	Probability	Contribution
k1	1	0.15	0.30
k2	0	0.10	0.10
k3	2	0.05	0.15
k4	1	0.10	0.20
k5	2	0.20	0.60
d0	2	0.05	0.15
d1	2	0.10	0.30
d2	3	0.05	0.20
d3	3	0.05	0.20
d4	3	0.05	0.20
d5	3	0.10	0.40
Total			2.80

To get an optimal solution, using the algorithm discussed in this chapter, the following tables are generated.

In the following tables, column index is i and row index is j.

e	1	2	3	4	5	6
5	2.75	2.00	1.30	0.90	0.50	0.10
4	1.75	1.20	0.60	0.30	0.05
3	1.25	0.70	0.25	0.05
2	0.90	0.40	0.05
1	0.45	0.10
0	0.05

w	1	2	3	4	5	6
5	1.00	0.80	0.60	0.50	0.35	0.10
4	0.70	0.50	0.30	0.20	0.05
3	0.55	0.35	0.15	0.05
2	0.45	0.25	0.05
1	0.30	0.10
0	0.05

root	1	2	3	4	5
5	2	4	5	5	5
4	2	2	4	4
3	2	2	3
2	1	2
1	1

From these tables, the optimal tree can be formed.

There are several types of heaps, however in this chapter, we are going to discuss binary heap. A binary heap is a data structure, which looks similar to a complete binary tree. Heap data structure obeys ordering properties discussed below. Generally, a Heap is represented by an array. In this chapter, we are representing a heap by H.

As the elements of a heap is stored in an array, considering the starting index as 1, the position of the parent node of i^th element can be found at ⌊ i/2 ⌋ . Left child and right child of i^th node is at position 2i and 2i + 1.

A binary heap can be classified further as either a max-heap or a min-heap based on the ordering property.

Max-Heap

In this heap, the key value of a node is greater than or equal to the key value of the highest child.

Hence, H[Parent(i)] ≥ H[i]

Min-Heap

In mean-heap, the key value of a node is lesser than or equal to the key value of the lowest child.

Hence, H[Parent(i)] ≤ H[i]

In this context, basic operations are shown below with respect to Max-Heap. Insertion and deletion of elements in and from heaps need rearrangement of elements. Hence, Heapify function needs to be called.

Array Representation

A complete binary tree can be represented by an array, storing its elements using level order traversal.

Let us consider a heap (as shown below) which will be represented by an array H.

Considering the starting index as 0, using level order traversal, the elements are being kept in an array as follows.

Index	0	1	2	3	4	5	6	7	8	...
elements	70	30	50	12	20	35	25	4	8	...

In this context, operations on heap are being represented with respect to Max-Heap.

To find the index of the parent of an element at index i, the following algorithm Parent (numbers[], i) is used.

Algorithm: Parent (numbers[], i) 
if i == 1 
   return NULL 
else 
   [i / 2]

The index of the left child of an element at index i can be found using the following algorithm, Left-Child (numbers[], i).

Algorithm: Left-Child (numbers[], i) 
If 2 * i ≤ heapsize 
   return [2 * i] 
else 
   return NULL

The index of the right child of an element at index i can be found using the following algorithm, Right-Child(numbers[], i).

Algorithm: Right-Child (numbers[], i) 
if 2 * i < heapsize 
   return [2 * i + 1] 
else 
   return NULL

To insert an element in a heap, the new element is initially appended to the end of the heap as the last element of the array.

After inserting this element, heap property may be violated, hence the heap property is repaired by comparing the added element with its parent and moving the added element up a level, swapping positions with the parent. This process is called percolation up.

The comparison is repeated until the parent is larger than or equal to the percolating element.

Algorithm: Max-Heap-Insert (numbers[], key) 
heapsize = heapsize + 1 
numbers[heapsize] = -∞ 
i = heapsize 
numbers[i] = key 
while i > 1 and numbers[Parent(numbers[], i)] < numbers[i] 
   exchange(numbers[i], numbers[Parent(numbers[], i)]) 
   i = Parent (numbers[], i)

Analysis

Initially, an element is being added at the end of the array. If it violates the heap property, the element is exchanged with its parent. The height of the tree is log n. Maximum log n number of operations needs to be performed.

Hence, the complexity of this function is O(log n).

Example

Let us consider a max-heap, as shown below, where a new element 5 needs to be added.

Initially, 55 will be added at the end of this array.

After insertion, it violates the heap property. Hence, the element needs to swap with its parent. After swap, the heap looks like the following.

Again, the element violates the property of heap. Hence, it is swapped with its parent.

Now, we have to stop.

Heapify method rearranges the elements of an array where the left and right sub-tree of i^th element obeys the heap property.

Algorithm: Max-Heapify(numbers[], i) 
leftchild := numbers[2i] 
rightchild := numbers [2i + 1] 
if leftchild ≤ numbers[].size and numbers[leftchild] > numbers[i] 
   largest := leftchild 
else 
   largest := i 
if rightchild ≤ numbers[].size and numbers[rightchild] > numbers[largest] 
   largest := rightchild 
if largest ≠ i 
   swap numbers[i] with numbers[largest] 
   Max-Heapify(numbers, largest)

When the provided array does not obey the heap property, Heap is built based on the following algorithm Build-Max-Heap (numbers[]).

Algorithm: Build-Max-Heap(numbers[]) 
numbers[].size := numbers[].length 
fori = ⌊ numbers[].length/2 ⌋ to 1 by -1 
   Max-Heapify (numbers[], i)

Extract method is used to extract the root element of a Heap. Following is the algorithm.

Algorithm: Heap-Extract-Max (numbers[]) 
max = numbers[1] 
numbers[1] = numbers[heapsize] 
heapsize = heapsize – 1 
Max-Heapify (numbers[], 1) 
return max

Example

Let us consider the same example discussed previously. Now we want to extract an element. This method will return the root element of the heap.

After deletion of the root element, the last element will be moved to the root position.

Now, Heapify function will be called. After Heapify, the following heap is generated.

Bubble Sort is an elementary sorting algorithm, which works by repeatedly exchanging adjacent elements, if necessary. When no exchanges are required, the file is sorted.

This is the simplest technique among all sorting algorithms.

Algorithm: Sequential-Bubble-Sort (A) 
fori← 1 to length [A] do 
for j ← length [A] down-to i +1 do 
   if A[A] < A[j - 1] then 
      Exchange A[j] ↔ A[j-1]

Implementation

voidbubbleSort(int numbers[], intarray_size) { 
   inti, j, temp; 
   for (i = (array_size - 1); i >= 0; i--) 
   for (j = 1; j <= i; j++) 
      if (numbers[j - 1] > numbers[j]) { 
         temp = numbers[j-1]; 
         numbers[j - 1] = numbers[j]; 
         numbers[j] = temp; 
      } 
}

Analysis

Here, the number of comparisons are

1 + 2 + 3 +...+ (n - 1) = n(n - 1)/2 = O(n²)

Clearly, the graph shows the n² nature of the bubble sort.

In this algorithm, the number of comparison is irrespective of the data set, i.e. whether the provided input elements are in sorted order or in reverse order or at random.

Memory Requirement

From the algorithm stated above, it is clear that bubble sort does not require extra memory.

Example

Unsorted list:

5 2 1 4 3 7 6

1^st iteration:

5 > 2 swap	2 5 1 4 3 7 6
5 > 1 swap	2 1 5 4 3 7 6
5 > 4 swap	2 1 4 5 3 7 6
5 > 3 swap	2 1 4 3 5 7 6
5 < 7 no swap	2 1 4 3 5 7 6
7 > 6 swap	2 1 4 3 5 6 7

2^nd iteration:

2 > 1 swap	1 2 4 3 5 6 7
2 < 4 no swap	1 2 4 3 5 6 7
4 > 3 swap	1 2 3 4 5 6 7
4 < 5 no swap	1 2 3 4 5 6 7
5 < 6 no swap	1 2 3 4 5 6 7

There is no change in 3^rd, 4^th, 5^th and 6^th iteration.

Finally,

the sorted list is

1 2 3 4 5 6 7

Insertion sort is a very simple method to sort numbers in an ascending or descending order. This method follows the incremental method. It can be compared with the technique how cards are sorted at the time of playing a game.

The numbers, which are needed to be sorted, are known as keys. Here is the algorithm of the insertion sort method.

Algorithm: Insertion-Sort(A) 
for j = 2 to A.length 
   key = A[j] 
   i = j – 1 
   while i > 0 and A[i] > key 
      A[i + 1] = A[i] 
      i = i -1 
   A[i + 1] = key

Analysis

Run time of this algorithm is very much dependent on the given input.

If the given numbers are sorted, this algorithm runs in O(n) time. If the given numbers are in reverse order, the algorithm runs in O(n²) time.

Example

Unsorted list:

2 13 5 18 14

1^st iteration:

Key = a[2] = 13

a[1] = 2 < 13

Swap, no swap

2 13 5 18 14

2^nd iteration:

Key = a[3] = 5

a[2] = 13 > 5

Swap 5 and 13

2 5 13 18 14

Next, a[1] = 2 < 13

Swap, no swap

2 5 13 18 14

3^rd iteration:

Key = a[4] = 18

a[3] = 13 < 18,

a[2] = 5 < 18,

a[1] = 2 < 18

Swap, no swap

2 5 13 18 14

4^th iteration:

Key = a[5] = 14

a[4] = 18 > 14

Swap 18 and 14

2 5 13 14 18

Next, a[3] = 13 < 14,

a[2] = 5 < 14,

a[1] = 2 < 14

So, no swap

2 5 13 14 18

Finally,

the sorted list is

2 5 13 14 18

This type of sorting is called Selection Sort as it works by repeatedly sorting elements. It works as follows: first find the smallest in the array and exchange it with the element in the first position, then find the second smallest element and exchange it with the element in the second position, and continue in this way until the entire array is sorted.

Algorithm: Selection-Sort (A) 
fori ← 1 to n-1 do 
   min j ← i; 
   min x ← A[i] 
   for j ←i + 1 to n do 
      if A[j] < min x then 
         min j ← j 
         min x ← A[j] 
   A[min j] ← A [i] 
   A[i] ← min x

Selection sort is among the simplest of sorting techniques and it works very well for small files. It has a quite important application as each item is actually moved at the most once.

Section sort is a method of choice for sorting files with very large objects (records) and small keys. The worst case occurs if the array is already sorted in a descending order and we want to sort them in an ascending order.

Nonetheless, the time required by selection sort algorithm is not very sensitive to the original order of the array to be sorted: the test if A[j] < min x is executed exactly the same number of times in every case.

Selection sort spends most of its time trying to find the minimum element in the unsorted part of the array. It clearly shows the similarity between Selection sort and Bubble sort.

• Bubble sort selects the maximum remaining elements at each stage, but wastes some effort imparting some order to an unsorted part of the array.

• Selection sort is quadratic in both the worst and the average case, and requires no extra memory.

For each i from 1 to n - 1, there is one exchange and n - i comparisons, so there is a total of n - 1 exchanges and

(n − 1) + (n − 2) + ...+ 2 + 1 = n(n − 1)/2 comparisons.

These observations hold, no matter what the input data is.

In the worst case, this could be quadratic, but in the average case, this quantity is O(n log n). It implies that the running time of Selection sort is quite insensitive to the input.

Implementation

Void Selection-Sort(int numbers[], int array_size) { 
   int i, j; 
   int min, temp;  
   for (i = 0; I < array_size-1; i++) { 
      min = i; 
      for (j = i+1; j < array_size; j++) 
         if (numbers[j] < numbers[min]) 
            min = j; 
      temp = numbers[i]; 
      numbers[i] = numbers[min]; 
      numbers[min] = temp; 
   } 
}

Example

Unsorted list:

5 2 1 4 3

1^st iteration:

Smallest = 5

2 < 5, smallest = 2

1 < 2, smallest = 1

4 > 1, smallest = 1

3 > 1, smallest = 1

Swap 5 and 1

1 2 5 4 3

2^nd iteration:

Smallest = 2

2 < 5, smallest = 2

2 < 4, smallest = 2

2 < 3, smallest = 2

No Swap

1 2 5 4 3

3^rd iteration:

Smallest = 5

4 < 5, smallest = 4

3 < 4, smallest = 3

Swap 5 and 3

1 2 3 4 5

4^th iteration:

Smallest = 4

4 < 5, smallest = 4

No Swap

1 2 3 4 5

Finally,

the sorted list is

1 2 3 4 5

It is used on the principle of divide-and-conquer. Quick sort is an algorithm of choice in many situations as it is not difficult to implement. It is a good general purpose sort and it consumes relatively fewer resources during execution.

Advantages

• It is in-place since it uses only a small auxiliary stack.

• It requires only n (log n) time to sort n items.

• It has an extremely short inner loop.

• This algorithm has been subjected to a thorough mathematical analysis, a very precise statement can be made about performance issues.

Disadvantages

• It is recursive. Especially, if recursion is not available, the implementation is extremely complicated.

• It requires quadratic (i.e., n2) time in the worst-case.

• It is fragile, i.e. a simple mistake in the implementation can go unnoticed and cause it to perform badly.

Quick sort works by partitioning a given array A[p ... r] into two non-empty sub array A[p ... q] and A[q+1 ... r] such that every key in A[p ... q] is less than or equal to every key in A[q+1 ... r].

Then, the two sub-arrays are sorted by recursive calls to Quick sort. The exact position of the partition depends on the given array and index q is computed as a part of the partitioning procedure.

Algorithm: Quick-Sort (A, p, r) 
if p < r then 
   q Partition (A, p, r) 
   Quick-Sort (A, p, q) 
   Quick-Sort (A, q + r, r)

Note that to sort the entire array, the initial call should be Quick-Sort (A, 1, length[A])

As a first step, Quick Sort chooses one of the items in the array to be sorted as pivot. Then, the array is partitioned on either side of the pivot. Elements that are less than or equal to pivot will move towards the left, while the elements that are greater than or equal to pivot will move towards the right.

Partitioning the Array

Partitioning procedure rearranges the sub-arrays in-place.

Function: Partition (A, p, r) 
x ← A[p] 
i ← p-1 
j ← r+1 
while TRUE do 
   Repeat j ← j - 1 
   until A[j] ≤ x  
   Repeat i← i+1 
   until A[i] ≥ x  
   if i < j then  
      exchange A[i] ↔ A[j] 
   else  
      return j

Analysis

The worst case complexity of Quick-Sort algorithm is O(n²). However using this technique, in average cases generally we get the output in O(n log n) time.

Radix sort is a small method that many people intuitively use when alphabetizing a large list of names. Specifically, the list of names is first sorted according to the first letter of each name, that is, the names are arranged in 26 classes.

Intuitively, one might want to sort numbers on their most significant digit. However, Radix sort works counter-intuitively by sorting on the least significant digits first. On the first pass, all the numbers are sorted on the least significant digit and combined in an array. Then on the second pass, the entire numbers are sorted again on the second least significant digits and combined in an array and so on.

Algorithm: Radix-Sort (list, n) 
shift = 1 
for loop = 1 to keysize do 
   for entry = 1 to n do 
      bucketnumber = (list[entry].key / shift) mod 10 
      append (bucket[bucketnumber], list[entry]) 
   list = combinebuckets() 
   shift = shift * 10

Анализ

Каждая клавиша просматривается сразу для каждой цифры (или буквы, если клавиши буквенные) самой длинной клавиши. Следовательно, если самый длинный ключ имеетm цифры и есть n ключи, сортировка по системе счисления имеет порядок O(m.n).

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

Здесь мы видим, что размер ключей не имеет значения, и этот алгоритм имеет линейную сложность. O(n).

пример

В следующем примере показано, как сортировка Radix работает с семью трехзначными числами.

Ввод	1- й проход	2- й проход	3- й проход
329	720	720	329
457	355	329	355
657	436	436	436
839	457	839	457
436	657	355	657
720	329	457	720
355	839	657	839

В приведенном выше примере первый столбец - это ввод. Остальные столбцы показывают список после последовательной сортировки по позиции все более значимых цифр. Код для сортировки Radix предполагает, что каждый элемент в массивеA из n элементы имеют d цифры, где цифра 1 это цифра самого низкого порядка и d это цифра самого высокого порядка.

Чтобы понять класс P и NP, сначала мы должны знать вычислительную модель. Следовательно, в этой главе мы обсудим две важные вычислительные модели.

Детерминированные вычисления и класс P

Детерминированная машина Тьюринга

Одна из таких моделей - детерминированная одноленточная машина Тьюринга. Эта машина состоит из конечного управления, головки чтения-записи и двусторонней ленты с бесконечной последовательностью.

Ниже приведена схематическая диаграмма детерминированной однополосной машины Тьюринга.

Программа для детерминированной машины Тьюринга определяет следующую информацию:

• Конечный набор символов ленты (входные символы и пустой символ)
• Конечный набор состояний
• Функция перехода

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

Недетерминированные вычисления и класс NP

Недетерминированная машина Тьюринга

Для решения вычислительной задачи еще одной моделью является недетерминированная машина Тьюринга (NDTM). Структура NDTM аналогична DTM, однако здесь у нас есть один дополнительный модуль, известный как модуль предположения, который связан с одной головкой только для записи.

Ниже приводится схематическая диаграмма.

Если проблема решается за полиномиальное время с помощью недетерминированной машины Тьюринга, проблема принадлежит к классу NP.

В неориентированном графе cliqueявляется полным подграфом данного графа. Полный подграф означает, что все вершины этого подграфа соединены со всеми остальными вершинами этого подграфа.

Задача Max-Clique - это вычислительная задача нахождения максимальной клики графа. Max clique используется во многих реальных задачах.

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

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

Algorithm: Max-Clique (G, n, k) 
S := Φ 
for i = 1 to k do 
   t := choice (1…n)  
   if t Є S then 
      return failure 
   S := S ∪ t  
for all pairs (i, j) such that i Є S and j Є S and i ≠ j do 
   if (i, j) is not a edge of the graph then  
      return failure 
return success

Анализ

Задача Max-Clique - это недетерминированный алгоритм. В этом алгоритме сначала мы пытаемся определить наборk различных вершин, а затем мы пытаемся проверить, образуют ли эти вершины полный граф.

Не существует детерминированного алгоритма с полиномиальным временем для решения этой проблемы. Эта проблема является NP-полной.

пример

Взгляните на следующий график. Здесь подграф, содержащий вершины 2, 3, 4 и 6, образует полный граф. Следовательно, этот подграф являетсяclique. Поскольку это максимально полный подграф предоставленного графика, это4-Clique.

Вершина-покрытие неориентированного графа G = (V, E) это подмножество вершин V^' ⊆ V так что если край (u, v) край G, то либо u в V или же v в V^' или оба.

Найдите вершину-покрытие максимального размера в данном неориентированном графе. Это оптимальное вершинное покрытие является оптимизационной версией NP-полной задачи. Однако найти вершинное покрытие, близкое к оптимальному, не так уж и сложно.

APPROX-VERTEX_COVER (G: Graph) c ← { } E' ← E[G] 
while E' is not empty do 
   Let (u, v) be an arbitrary edge of E' c ← c U {u, v} 
   Remove from E' every edge incident on either u or v 
return c

пример

Множество ребер данного графа -

{(1,6),(1,2),(1,4),(2,3),(2,4),(6,7),(4,7),(7,8),(3,8),(3,5),(8,5)}

Теперь начнем с выбора произвольного ребра (1,6). Мы удаляем все ребра, инцидентные вершине 1 или 6, и добавляем ребро (1,6) для покрытия.

На следующем шаге мы случайно выбрали другое ребро (2,3).

Теперь выбираем еще одно ребро (4,7).

Выбираем еще одно ребро (8,5).

Следовательно, вершинное покрытие этого графа равно {1,2,4,5}.

Анализ

Легко видеть, что время работы этого алгоритма равно O(V + E), используя список смежности для представления E^'.

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

Проблема оптимизации

Проблемы оптимизации - это те, для которых цель состоит в том, чтобы максимизировать или минимизировать некоторые значения. Например,

• Нахождение минимального количества цветов, необходимого для раскрашивания данного графика.

• Нахождение кратчайшего пути между двумя вершинами в графе.

Решение проблемы

Есть много проблем, на которые можно ответить "да" или "нет". Эти типы проблем известны как decision problems. Например,

• Можно ли раскрасить данный граф только в 4 цвета.

• Нахождение гамильтонова цикла в графе не является проблемой решения, тогда как проверка того, является ли граф гамильтоновым или нет, является проблемой решения.

Что такое язык?

У каждой проблемы решения может быть только два ответа: да или нет. Следовательно, проблема принятия решения может принадлежать языку, если он дает ответ «да» на конкретный ввод. Язык - это совокупность входных данных, для которых ответ положительный. Большинство алгоритмов, обсуждаемых в предыдущих главах, являютсяpolynomial time algorithms.

Для размера ввода n, если наихудшая временная сложность алгоритма равна O(n^k), где k - константа, алгоритм представляет собой алгоритм с полиномиальным временем.

Такие алгоритмы, как умножение цепочки матриц, кратчайший путь от одного источника, кратчайший путь для всех пар, минимальное связующее дерево и т. Д., Выполняются за полиномиальное время. Однако существует множество проблем, таких как коммивояжер, оптимальная раскраска графа, гамильтоновы циклы, поиск самого длинного пути в графе и выполнение булевой формулы, для которых не известны алгоритмы с полиномиальным временем. Эти проблемы относятся к интересному классу задач, называемыхNP-Complete проблемы, статус которых неизвестен.

В этом контексте мы можем классифицировать проблемы следующим образом:

P-класс

Класс P состоит из тех задач, которые решаются за полиномиальное время, т.е. эти задачи могут быть решены за время. O(n^k) в худшем случае, когда k постоянно.

Эти проблемы называются tractable, а другие называются intractable or superpolynomial.

Формально алгоритм - это алгоритм полиномиального времени, если существует полиномиальный алгоритм p(n) так что алгоритм может решить любой экземпляр размера n вовремя O(p(n)).

Проблема, требующая Ω(n⁵⁰) время, чтобы решить, по сути, трудно решить для больших n. Самый известный алгоритм полиномиального времени работает во времениO(n^k) за довольно низкую стоимость k.

Преимущества рассмотрения класса алгоритмов с полиномиальным временем заключаются в том, что все разумные deterministic single processor model of computation могут моделироваться друг на друге с помощью не более чем полиномиального медленного

NP-Класс

Класс NP состоит из тех задач, которые проверяются за полиномиальное время. NP - это класс задач решения, для которых легко проверить правильность заявленного ответа с помощью небольшой дополнительной информации. Следовательно, мы не ищем способ найти решение, а только для того, чтобы убедиться, что предполагаемое решение действительно верно.

Каждая задача этого класса может быть решена за экспоненциальное время с помощью исчерпывающего поиска.

P против NP

Каждая проблема решения, которая может быть решена с помощью детерминированного алгоритма с полиномиальным временем, также разрешима с помощью недетерминированного алгоритма с полиномиальным временем.

Все проблемы в P могут быть решены с помощью алгоритмов с полиномиальным временем, тогда как все проблемы в NP - P трудноразрешимы.

Неизвестно, были ли P = NP. Однако в NP известно много проблем, которые принадлежат P, то можно доказать, что P = NP.

Если P ≠ NP, в NP есть задачи, которых нет ни в P, ни в NP-Complete.

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

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

Ниже приведены четыре теоремы Стивена Кука.

Теорема-1.

Если набор S строк принимается некоторой недетерминированной машиной Тьюринга за полиномиальное время, то S P-сводится к {тавтологиям ДНФ}.

Теорема 2.

Следующие множества P-сводимы друг к другу попарно (и, следовательно, все они имеют одинаковую полиномиальную степень сложности): {тавтологии}, {тавтологии DNF}, D3, {пары подграфов}.

Теорема-3.

• Для любой T_Q(k) типа Q, $\mathbf{\frac{T_{Q}(k)}{\frac{\sqrt{k}}{(log\:k)^2}}}$ неограничен

• Существует T_Q(k) типа Q такой, что $T_{Q}(k)\leqslant 2^{k(log\:k)^2}$

Теорема-4.

Если набор S строк принимается недетерминированной машиной в течение времени T(n) = 2ⁿ, и если T_Q(k) является честной (т.е. счетной в реальном времени) функцией типа Q, то существует постоянная K, так S может быть распознана детерминированной машиной во времени T_Q(K8ⁿ).

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

• Во-вторых, он сосредоточил внимание на классе NP задач принятия решений, которые могут быть решены за полиномиальное время на недетерминированном компьютере. Большинство трудноразрешимых проблем относится к этому классу, NP.

• В-третьих, он доказал, что одна конкретная проблема в NP обладает тем свойством, что любая другая проблема в NP может быть полиномиально сведена к ней. Если проблема выполнимости может быть решена с помощью алгоритма полиномиального времени, то каждая проблема в NP также может быть решена за полиномиальное время. Если какая-либо проблема в NP трудноразрешима, то проблема выполнимости должна быть неразрешимой. Таким образом, проблема выполнимости - самая сложная проблема в NP.

• В-четвертых, Кук предположил, что другие проблемы в NP могут разделять с проблемой выполнимости это свойство быть самым трудным членом NP.

Проблема в классе NPC, если он в NP и как hardкак любая проблема в НП. Проблема в томNP-hard если все проблемы в NP сводятся к нему за полиномиальное время, даже если это может не быть в самом NP.

Если для любой из этих задач существует алгоритм с полиномиальным временем, все проблемы в NP будут разрешимы за полиномиальное время. Эти проблемы называютсяNP-complete. Феномен NP-полноты важен как с теоретической, так и с практической точки зрения.

Определение NP-полноты

Язык B является NP-complete если он удовлетворяет двум условиям

• B находится в НП

• Каждые A в NP полиномиальное время сводится к B.

Если язык удовлетворяет второму свойству, но не обязательно первому, язык B известен как NP-Hard. Неформально проблема поискаB является NP-Hard если есть какие-то NP-Complete проблема A что Тьюринг сводится к B.

Проблема в NP-Hard не может быть решена за полиномиальное время, пока P = NP. Если доказано, что проблема связана с NPC, нет необходимости тратить время на попытки найти эффективный алгоритм для ее решения. Вместо этого мы можем сосредоточиться на алгоритме аппроксимации проекта.

NP-полные задачи

Ниже приведены некоторые NP-Complete задачи, для которых не известен алгоритм с полиномиальным временем.

• Определение того, есть ли у графа гамильтонов цикл
• Определение выполнимости булевой формулы и т. Д.

NP-сложные задачи

Следующие проблемы являются NP-Hard

• Проблема выполнимости схем
• Установить обложку
• Крышка Vertex
• Задача коммивояжера

В этом контексте мы сейчас обсудим TSP - это NP-Complete.

TSP - это NP-Complete

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

Доказательство

Чтобы доказать TSP is NP-Complete, сначала нужно доказать, что TSP belongs to NP. В TSP мы находим тур и проверяем, содержит ли он каждую вершину один раз. Затем рассчитывается общая стоимость краев тура. Наконец, проверяем, минимальна ли стоимость. Это может быть выполнено за полиномиальное время. Таким образомTSP belongs to NP.

Во-вторых, мы должны доказать, что TSP is NP-hard. Чтобы доказать это, один из способов - показать, чтоHamiltonian cycle ≤_p TSP (как мы знаем, проблема гамильтонова цикла NP-полна).

Предполагать G = (V, E) быть примером гамильтонова цикла.

Следовательно, создается экземпляр TSP. Создаем полный графG^' = (V, E^'), где

$$E^{'}=\lbrace(i, j)\colon i, j \in V \:\:and\:i\neq j$$

Таким образом, функция стоимости определяется следующим образом -

$$t(i,j)=\begin{cases}0 & if\: (i, j)\: \in E\\1 & otherwise\end{cases}$$

Теперь предположим, что гамильтонов цикл h существует в G. Понятно, что стоимость каждого ребра вh является 0 в G^' поскольку каждое ребро принадлежит E. Следовательно,h имеет стоимость 0 в G^'. Таким образом, если графG имеет гамильтонов цикл, то граф G^' есть тур по 0 Стоимость.

Наоборот, мы предполагаем, что G^' есть тур h^' стоимости не более 0. Стоимость ребра вE^' находятся 0 и 1по определению. Следовательно, каждое ребро должно иметь стоимость0 как стоимость h^' является 0. Таким образом, мы заключаем, чтоh^' содержит только ребра в E.

Таким образом, мы доказали, что G имеет гамильтонов цикл тогда и только тогда, когда G^' имеет тур стоимостью не более 0. ТСП является NP-полным.

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

Для многих задач путь к цели не имеет значения. Например, в задаче N-Queens нам не нужно заботиться об окончательной конфигурации ферзей, а также о том, в каком порядке они добавляются.

Скалолазание

Hill Climbing - это метод решения определенных задач оптимизации. В этом методе мы начинаем с неоптимального решения, которое многократно улучшается, пока какое-то условие не будет максимальным.

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

Следовательно, технику восхождения можно рассматривать как следующие этапы:

• Построение неоптимального решения с учетом ограничений задачи
• Пошаговое улучшение решения
• Улучшение решения до тех пор, пока улучшение не станет невозможным

Техника Hill Climbing в основном используется для решения сложных вычислительных задач. Он смотрит только на текущее состояние и состояние в ближайшем будущем. Следовательно, этот метод эффективен с точки зрения памяти, поскольку он не поддерживает дерево поиска.

Algorithm: Hill Climbing 
Evaluate the initial state. 
Loop until a solution is found or there are no new operators left to be applied: 
   - Select and apply a new operator 
   - Evaluate the new state: 
      goal -→ quit 
      better than current state -→ new current state

Итеративное улучшение

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

Избежать этой проблемы можно разными способами. Один из таких методов - имитационный отжиг.

Произвольный перезапуск

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

Проблемы техники восхождения на холмы

Локальные максимумы

Если эвристика не является выпуклой, Hill Climbing может сходиться к локальным максимумам, а не к глобальным максимумам.

Гряды и аллеи

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

Плато

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

Сложность техники восхождения на холм

Этот метод не имеет проблем, связанных с пространством, поскольку он учитывает только текущее состояние. Ранее исследованные пути не сохраняются.

Для большинства проблем в технике восхождения на холм с произвольным перезапуском оптимальное решение может быть достигнуто за полиномиальное время. Однако для задач NP-Complete время вычислений может быть экспоненциальным в зависимости от количества локальных максимумов.

Применение техники восхождения на холм

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

Скалолазание также используется в индуктивных методах обучения. Этот метод используется в робототехнике для координации между несколькими роботами в команде. Есть много других проблем, когда используется этот метод.

пример

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