Партнерка на США и Канаду по недвижимости, выплаты в крипто
- 30% recurring commission
- Выплаты в USDT
- Вывод каждую неделю
- Комиссия до 5 лет за каждого referral
Для этого нужен дополнительный массив весов 
, в котором каждому корню приписывается либо число вершин, либо высота дерева (эти значения модифицируются при объединении множеств).
При указанных выше условиях дерево высоты 
будет содержать 
вершин (док-во по МИ):
1. Для 
– выполняется.
2. Пусть объединяются деревья высоты 
и 
, с числом вершин 
и 
, 
, 
, 
.
Если 
, то объединенное дерево будет также иметь высоту . Если 
, то высота нового дерева будет 
, а число вершин 
.
=> Если множество содержит 
вершин, то его корень можно найти не более, чем за 
шагов.
=> Трудоемкость выделения всех ребер остова (после сортировки ребер графа) не превышает 
.
Еще более эффективной будет проверка со сжатием путей, когда при поиске корня ссылки на «отца» заменяются на ссылки прямо на корень мн-ва для всех пройденных вершин.
Тогда трудоемкость выделения остова равна 
, где 
– «обратная» к част. случаю ф-ции Аккермана 
:
, 
, 
;
(это фактически 
).
| 0 | 1 | 2 | 3 | 4 | 5 |
| 1 | 2 | 4 | 16 | 65536 |
|
| 0 | 0 | 1 | 2 | 2 | 3 |
Ниже приводится алгоритм Крускала для графа, заданного массивом взвешенных ребер R[1…e].
Ребро R[i] – это структура, содержащая 3 поля:
v1 – номер 1-й вершины,
v2 – номер 2-й вершины,
wg – вес ребра (используется только при сортировке ребер).
k выделенных ребер остова сохраняются в массиве W[1…k].
упорядочить_ребра_по_возрастанию_весов(R);
// нач. значения ссылок и весов множеств
for (i = 1; i <= n; i++) { A[i] = i; B[i] = 1; }
for (k = 0, i = 1; k < n-1 && i <= e; i++) {
for (r1 = R[i].v1; r1 != A[r1]; r1 = A[r1]); // r1 – 1-й корень
for (r2 = R[i].v2; r2 != A[r2]; r2 = A[r2]); // r2 – 2-й корень
if (r1 == r2) continue; // ребро дает цикл
W[++k] = R[i]; // ребро – в остов
if (B[r1] >= B[r2])
{ A[r2] = r1; B[r1] += B[r2]; } // r2 -> r1
else
{ A[r1] = r2; B[r2] += B[r2]; } // r1 -> r2
}
Алгоритмы Прима и Крускала – жадные: на каждом их шаге делается локально оптимальный (жадный) выбор, который никогда не отменяется на последующих шагах.
Жадный алгоритм можно использовать, если для задачи выполняются 2 условия:
- оптимальное решение задачи содержит в себе оптимальные решения подзадач (свойство оптимальности подзадач);
- последовательность локально оптимальных выборов дает глобально оптимальное решение (т. е. жадный выбор на каждом шаге не закрывает путь к оптимальному решению).
Поиск кратчайших путей в графе
Пусть 
– взвешенный ориентированный граф с матрицей весов дуг 
, 
, 
, если 
.
Если в графе 
некоторый путь, последовательно проходящий через вершины 
, то его весом является величина 
. Если несколько различных путей из 
в 
, то можно сформулировать оптимизационную задачу поиска кратчайшего (минимального по весу) пути (пример с атласом дорог).
3 варианта задачи поиска кратчайших путей в графе:
- кратчайший путь между парой вершин и ,
- кратчайшие пути из одной вершины во все остальные,
- кратчайшие пути между всеми парами вершин.
Алгоритм Дейкстры –
кратчайшие пути из одной вершины-источника во все остальные.
Вес кратчайшего пути из в будем обозначать 
.
Пусть этот путь проходит через вершины 
, тогда 
(легко доказать от противного).
=>
Для задачи поиска кратчайшего пути выполняется свойство оптимальности подзадач.
Пусть для некоторого мн-ва вершин 
(старых) найдены кратчайшие пути из с весами 
, 
( никогда не пусто, т. к. 
).
Для остальных вершин 
(новых) проверка пока не завершена, но определены текущие значения длин путей: 
, т. е. соответствующий путь проходит только через старые вершины.
При 
начальные значения 
.
Если в графе еще не найдены пути из в 
, проходящие только через старые вершины, то 
.
Выберем 
и соответствующую вершину 
. По условию выбора, любой путь, проходящий из в через произвольную новую вершину 
, не может иметь вес, меньший чем 
(вес такого пути
).
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 |
Основные порталы (построено редакторами)