Если кто-нибудь может дать полезную ссылку на описание алгоритма meet-in-the-middle или же сможет написать, что это за алгоритм буду признателен. Заранее спасибо.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3821 |
| 3 | Benq | 3736 |
| 4 | Radewoosh | 3631 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3388 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 10.11.2024 12:42:39 (j3).
Десктопная версия, переключиться на мобильную.
При поддержке
Вы об этом? (UPD: в гугле нашёл по одной из первых ссылок - о, чудо!)
Ну, пусть известно начальное состояние, конечное состояние и то, что длина оптимального пути не превышает n. Тогда сгенерируем бфс-ом все состояния, доступные из начала и конца за n/2 или меньше ходов. Найдем состояния, которые доступны из начала и из конца. Найдем среди них наилучшее по сумме длин путей. Собственно, пусть из каждого состояния есть k переходов. Тогда простым бфс-ом мы бы сгенерировали k^n состояний, а бфс-ом из двух концов - k^(n/2) состояний. Примерно так.
А что, если неизвестно, что длина пути не превышает n?
Будем добавлять уровни по очереди. Сначала нужно обработать в двух bfs вершины, которые на расстоянии 1 от старта/финиша, потом те, которые на расстоянии 2, потом те, которые на расстоянии 3... Как только на какой-то итерации оба bfs'а встретятся (т.е. будет хоть одна вершина, которая отмечена достижимой в обеих обходах) — остановимся, путь найден. Это как раз хорошо отображает суть названия meet-in-the-middle — наши bfs как бы идут навстречу друг другу, и сойдутся на полпути.
Да, так вроде бы понятно. Но в этом способе нужно обязательно действовать последовательно, т.е. перебираем все уровни для обеих вершин. Ясно, что в худшем случае это ничего не меняет. Но представим ситуацию, когда в 1-й вершине граф ветвится очень сильно, но при этом из второй вершины в первую есть путь длиной 3 ребра и у второй вершины всего 1 сосед (вершина из этого пути). Предложенный подход переберет всех соседей 1-й вершины.
Можно попробовать оптимальнее — будем выполнять итерации bfs по одной для 1 й и 2й вершины. Будем поддерживать для 1-го и 2-го поиска величину — расстояние до дальней достигнутой вершины, скажем d1 и d2. Тогда, кажется, минимальная длина кратчайшего пути при данных d1 и d2 равна (d1-1)+(d2-1)+1 = d1+d2-1.
Соответственно, если мы нашли путь меньше или равный этой длине — можно останавливаться.
Это реально работает при "датамайнинге" в соцсетях — в этих графах дорого стоит действовать вашим способом, особенно если нет прекешированных данных о друзьях и надо их подгружать через API.
Здесь под итерацией bfs подразумеваем обработку одной вершины из очереди? Да, можно так. Рассуждая о таких алгоритмах, нужно уточнить, о каких задачах и каких графах идет речь. "В худшем случае", когда структура графа относительно начальной и конечной вершины одинакова, и порядок обхода в bfs выбран неудачно — нам в обеих случаях нужно будет пересмотреть одних и тех же соседей. А еще гипотетически возможен случай, когда при "более сбалансированном" поиске с одной стороны bfs успеет зайти на более высокий уровень, чем было бы при поуровневом поиске, а на этом уровне почему-то много "очень плохих" вершин — например, вершин, у которых очень-очень много соседей, или которые очень медленно обрабатываются по какой-то другой причине.
На практике для разных задач подходят разные алгоритмы, а банальный bfs обычно приходится обвешивать какими-то эвристиками информированного поиска.
http://pastebin.ru/V29kyu0Q попробовал написать даже) Работает классно
http://acm.timus.ru/problem.aspx?space=1&num=1695
Сорри. Не заметил, что в задаче фигурирует второй критерий - "стоимость". Видимо подразумевалось решение как у тебя.
P.S.: задачка "Stone Pile" с Тимуса отлично сочетает в себе максимальную простоту и возможность автоматической проверки вашего meet-in-the-middle на корректность. Несмотря на то, что может быть решена перебором :-)
(ab+c)/d - e = f
ab+c-de = df
ab+c = d(e+f)
Находим все варианты для левой части, перебираем правую, смотрим кол-во вариантов.
спойлер
спойлер
Есть статья на e-maxx.
Не пойму, зачем писать meet in the middle, если все задачи, которые я находил на это решались рекурсией намного быстрее(потому что не нужно было пересчитывать заново параметры задачи)?