## Жадные алгоритмы
Имеется некоторая сумма $S$, которую некто хочет снять в банкомате. Банкомат предоставляет купюры стоимостью $S_1$, $S_2$, $S_3$, ..., $1$. Каким минимальным количеством купюр можно получить сумму $S$?  
Данная задача даёт оптимальный результат при решении жадным алгоритмом. В начале берём наибольшее возможное количество купюр максимального номинала $S_1$. Остаток покрываем максимально возможным набором купюр следующего подходящего номинала и т. д.  
**Жадный алгоритм** (greedy algorithm) - алгоритм, заключающийся в принятии локально оптимальных решений на каждом этапе, допуская, что конечное решение тоже окажется оптимальным.  
Известно, что если структура задачи задается матроидом, тогда применение жадного алгоритма выдаст глобальный оптимум.  
**Матроид** - пара множеств $(D,F)$, где $D =$ {$d_1, d_2, d_3 ... d_k$}, $F =$ {$f_1, f_2, f_3, ... f_m$}, отвечающая следующим свойствам:
1. Если $f∈F$ и $h∈f$, то $h∈F$
2. Пусть $f, g ∈ F$, $|f|=n$, $|g|=n+1$. Тогда $e ∈ g$, $f ∪ e ∈ F$, $|f+e|=n+1$
## Метод ветвей и границ
Предназначен в первую очередь для решения NP-трудных оптимизационных задач.  
Сочетание 2 операций:
- Ветвление
- Оценка верхней/нижней границы и "отсечение" неперспективной ветви
#### Задача коммивояжера
Имеется $N$ населённых пунктов, некоторые из которых соединены дорогами. Проезд по каждой дороге обладает некоторой стоимостью. Коммивояжеру нужно выехать из дома, находящегося в одном из пунктов, побывать в каждом пункте лишь однократно, вернутся домой и при этом путь должен иметь минимальную стоимость.  
![Граф для задачи коммивояжера](../Pictures/06_01.%20Граф%20для%20задачи%20коммивояжера.png)  
Математической моделью данной задачи является граф. Задача сводится к нахождению цикла в графе, проходящего через все вершины один раз и имеющего минимальную стоимость. Цикл, проходящий через все вершины графа, называется **гамильтоновым циклом**. На сегодняшний день не существует ни одного алгоритма, работающего быстро, который решил бы задачу Коммивояжера. Полный перебор на полносвязном графе пропорционален n!  
Метод ветвей и границ в худшем случае тоже приведёт к полному перебору. В среднем он позволяет заранее отсечь заведомо плохие варианты.  
На первом шаге оценим, лучше какого значения стоимость гамильтонова цикла не может быть. Для этого сложим для каждой вершины пару дорог минимальной стоимости, разделив общую сумму на 2.
1. Нижняя граница: **(2+3+3+5+4+4+2+3+3+5) / 2 = 17**
2. Левая ветвь - ребро $AB$ входит: граница **= 17**
3. Правая ветвь - ребро $AB$ не входит: **(2+4+7+5+4+4+2+3+3+5) / 2 = 19,5**
  
Далее введём в начале просмотр налево, включая и исключая те или иные рёбра, двигаясь каждый раз в сторону той границы, которая меньше. Когда мы дойдём до некоторого цикла, то все ветви, имеющие границу, большую или равную стоимости этого цикла, можно не рассматривать.
## Генетические алгоритмы
**Генетический алгоритм** - это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, аналогичных естественному отбору в природе.  
![Генетический алгоритм](../Pictures/06_02.%20Генетический%20алгоритм.png)  
## Муравьиные алгоритмы
**Муравьиный алгоритм** (алгоритм оптимизации подражанием муравьиной колонии) - один из эффективных полиномиальных алгоритмов для нахождения приближённых решений задачи коммивояжера, а также решения аналогичных задач поиска маршрутов на графах.  
![Муравьиный алгоритм](../Pictures/06_03.%20Муравьиный%20алгоритм.png)