|
|
| Строка 1: |
Строка 1: |
| − | {{Определение
| + | Страница находится в разработке |
| − | |definition=
| |
| − | '''Meet-in-the-middle''' (Встреча в середине) — способ оптимизации
| |
| − | перебора. }}
| |
| − | Алгоритм Meet-in-the-middle разбивает задачу пополам и решает всю задачу через частичный расчет половинок.
| |
| − | == Задача о рюкзаке ==
| |
| − | Классической задачей является задача о наиболее эффективной упаковке рюкзака. Каждый предмет характеризуется весом (<tex> {w_{i} <= 10^{9}} </tex> ) и ценностью (<tex>{cost_{i} <= 10^{9}} </tex>). В рюкзак, ограниченный по весу, необходимо набрать вещей с максимальной суммарной стоимостью. Для ее решения изначальное множество вещей N разбивается на два равных(или примерно равных) подмножества, для которых за приемлемое время, можно перебрать все варианты и подсчитать суммарный вес и стоимость, а затем для каждого из них найти группу вещей из первого подмножества с максимальной стоимостью, укладывающуюся в ограничение по весу рюкзака. Сложность алгоритма <tex>O({2^{n/2}}\times{n})</tex>. Память <tex> O({2^{n/2}})</tex>
| |
| − | | |
| − | === Реализация ===
| |
| − | Реализуем данный алгоритм:
| |
| − | // N - количество всех вещей, w[] - массив весов всех вещей, cost[] - массив стоимостей всех вещей, R - ограничение по весу рюкзака.
| |
| − | sn = N / 2, fn = N - sn;
| |
| − | for mask = 0 to 2 ** sn - 1
| |
| − | for j = 0 to sn
| |
| − | if j-ый бит mask = 1
| |
| − | first[i].w += w[j];
| |
| − | first[i].c += cost[j];
| |
| − |
| |
| − | for mask = 0 to 2 ** fn - 1
| |
| − | for j = 0 to fn
| |
| − | if j-ый бит mask = 1
| |
| − | curw += w[j + sn];
| |
| − | curcost += cost[j + sn];
| |
| − | p = findmax(); // Находим маску вещей из первой половины с макcимальной стоимостью и подходящей по весу
| |
| − | if (curw + first[p].w <= R && curcost + first[p].c > ans)
| |
| − | ans = curcost + first[p].c;
| |
| − | print ans
| |
| − | | |
| − | == Задача о нахождении кратчайшего расстояния между двумя вершинами в графе ==
| |
| − | [[Файл:bfs.png|600px|thumb|right|Нахождение кратчайшего расстояния между двумя вершинами]]
| |
| − | Еще одна задача, решаемая алгоритмом Meet-in-the-middle — это нахождение кратчайшего расстояния между двумя вершинами, зная начальное состояние, конечное состояние и то, что длина оптимального пути не превышает '''N'''.
| |
| − | Стандартным подходом для решения данной задачи, является применение алгоритма [[Обход в ширину|обхода в ширину]]. Пусть из каждого состояния у нас есть '''K''' переходов, тогда бы мы сгенерировали <tex> {K^{n}} </tex> состояний. Асимптотика данного решения составила бы <tex> {O({K^{n}})} </tex>. '''Meet-in-the-middle''' помогает снизить асимптотику до <tex> {O({K^{n/2}})} </tex>. <br>
| |
| − | === Алгоритм решения ===
| |
| − | | |
| − | 1. Сгенерируем bfs-ом все состояния, доступные из начала и конца за <tex> {n/2} </tex> или меньше ходов.
| |
| − | | |
| − | 2. Найдем состояний, которые достижимы из начала и из конца.
| |
| − | | |
| − | 3. Найдем среди них наилучшее по сумме длин путей.
| |
| − | | |
| − | | |
| − | Таким образом, bfs-ом из двух концов, мы сгенерируем максимум <tex> {O({K^{n/2}})} </tex> состояний.
| |
| − | | |
| − | == См. также ==
| |
| − | * [[Обход в ширину]]
| |
| − | | |
| − | [[Категория: Дискретная математика и алгоритмы]]
| |
| − | | |
| − | [[Категория: Динамическое программирование ]]
| |
