Блог пользователя lth

Meet-in-the-middle
Автор lth, 13 лет назад, По-русски

Если кто-нибудь может дать полезную ссылку на описание алгоритма  meet-in-the-middle или же сможет написать, что это за алгоритм буду признателен. Заранее спасибо.

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

13 лет назад, # |
← Rev. 2   Проголосовать: нравится -11 Проголосовать: не нравится

Вы об этом? (UPD: в гугле нашёл по одной из первых ссылок - о, чудо!)

→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Насколько я знаю, meet-in-the-middle - это не конкретный алгоритм, а способ оптимизации перебора, когда мы делим задачу на две части и потом сливаем их быстрее чем за линию (например, задача о рюкзаке с большими весами)
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Быстрее, чем за квадрат. Еще так можно назвать БФС, идущий с двух сторон.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Да, действительно ошибся, спасибо
        → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Можно по-подробнее про этот бфс?
        → Ответить
        • 13 лет назад, # ^ |
          ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          Ну, пусть известно начальное состояние, конечное состояние и то, что длина оптимального пути не превышает n. Тогда сгенерируем бфс-ом все состояния, доступные из начала и конца за n/2 или меньше ходов. Найдем состояния, которые доступны из начала  и из конца. Найдем среди них наилучшее по сумме длин путей. Собственно, пусть из каждого состояния есть k переходов. Тогда простым бфс-ом мы бы сгенерировали k^n состояний, а бфс-ом из двух концов - k^(n/2) состояний. Примерно так.

          → Ответить
          • 10 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            А что, если неизвестно, что длина пути не превышает n?

            → Ответить
            • 10 лет назад, # ^ |
                Проголосовать: нравится +5 Проголосовать: не нравится

              Будем добавлять уровни по очереди. Сначала нужно обработать в двух bfs вершины, которые на расстоянии 1 от старта/финиша, потом те, которые на расстоянии 2, потом те, которые на расстоянии 3... Как только на какой-то итерации оба bfs'а встретятся (т.е. будет хоть одна вершина, которая отмечена достижимой в обеих обходах) — остановимся, путь найден. Это как раз хорошо отображает суть названия meet-in-the-middle — наши bfs как бы идут навстречу друг другу, и сойдутся на полпути.

              → Ответить
              • 10 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

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

                → Ответить
                • 10 лет назад, # ^ |
                  ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                  Можно попробовать оптимальнее — будем выполнять итерации bfs по одной для 1 й и 2й вершины. Будем поддерживать для 1-го и 2-го поиска величину — расстояние до дальней достигнутой вершины, скажем d1 и d2. Тогда, кажется, минимальная длина кратчайшего пути при данных d1 и d2 равна (d1-1)+(d2-1)+1 = d1+d2-1.

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

                  Это реально работает при "датамайнинге" в соцсетях — в этих графах дорого стоит действовать вашим способом, особенно если нет прекешированных данных о друзьях и надо их подгружать через API.

                  → Ответить
                  • 10 лет назад, # ^ |
                    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                    Здесь под итерацией bfs подразумеваем обработку одной вершины из очереди? Да, можно так. Рассуждая о таких алгоритмах, нужно уточнить, о каких задачах и каких графах идет речь. "В худшем случае", когда структура графа относительно начальной и конечной вершины одинакова, и порядок обхода в bfs выбран неудачно — нам в обеих случаях нужно будет пересмотреть одних и тех же соседей. А еще гипотетически возможен случай, когда при "более сбалансированном" поиске с одной стороны bfs успеет зайти на более высокий уровень, чем было бы при поуровневом поиске, а на этом уровне почему-то много "очень плохих" вершин — например, вершин, у которых очень-очень много соседей, или которые очень медленно обрабатываются по какой-то другой причине.

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

                    → Ответить
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Одна реализация на Ява
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
RodionGork: Нет я имел ввиду алгоритм meet-in-the-middle для задач на подмножества.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
k1r1ch: Да и как же это сделать ?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    http://apps.topcoder.com/wiki/display/tc/Member+SRM+461 -- 950-я как раз на Meet-In-Middle. 
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Я решал всего одну такую задачу, вот ее условие - http://ifolder.ru/26399410 (задача D)
    Кстати, я правильно понимаю что нет никаких ограничений на распространение задач из ЛКШ?

    Ну так вот, идея такая: 2^32 - это много, а 2^16 - вполне так нормально. Разобьем все предметы на две половины: первые n/2 и вторые n/2 предметов. В каждой половине рассмотрим все возможные комбинации предметов (рекурсивно или битмасками, не суть). Теперь будем перебирать все эти получившиеся комбинации из первой половины по очереди, а вторую половину предварительно отсортируем по весу. Тогда если мы берем текущую комбинацию предметов из первой половины, то мы можем бинпоиском найти границы диапазона комбинаций из второй половины, так чтобы суммарный вес был не меньше L и не больше R. Теперь найдем максимум на этом отрезке (с помощью дерева отрезков или sparse table). Ну и общая стоимость будет равна этом максимуму плюс стоимость набора из первой половины. Таким образом мы рассмотрим все варианты, да еще и по времени уложимся.

    Если что непонятно объяснил, могу подробнее расписать.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Вроде как еще одна:
      http://acm.timus.ru/problem.aspx?space=1&num=1695
      → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      спасибо за объяснение, я хоть и не создавал пост, но тоже не знал что это за метод такой, теперь более менее понятно
      → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Посмотрел ради интереса условие. Если я не ошибаюсь, эту задачу можно решать без бинпоисков и структур данных - только meet-in-the-middle + 2 указателя. И исходник, приведенный выше, достаточно дополнить одним if-ом для получения аксепта...
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Сорри. Не заметил, что в задаче фигурирует второй критерий - "стоимость". Видимо подразумевалось решение как у тебя.

        P.S.: задачка "Stone Pile" с Тимуса отлично сочетает в себе максимальную простоту и возможность автоматической проверки вашего meet-in-the-middle на корректность. Несмотря на то, что может быть решена перебором :-)

        → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
http://www.spoj.pl/problems/ABCDEF/
Типичнейшая задача на meet-in-the-middle
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А откуда он здесь берется?
    → Ответить
    • 13 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      (ab+c)/d - e = f

      ab+c-de = df

      ab+c = d(e+f)

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

      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Ну это понятно, просто не подумал бы назвать это meet-in-the-middle.
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Ну ведь находим решения для правой, и затем для левой выбираем из правой :)
          → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            ну все равно извращенно как-то получается так назвать)

            → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    На Java ни в какую не заталкивается.

    Вроде решение за куб - попробовал HashMap и бинпоиск.
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Дискретное логарифмирование решается meet-in-the-middle с корневой оптимизацией за O(sqrt(Mod)) запрос и столько же предподсчёт при использовании хэштаблиц.
Есть статья на e-maxx.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
http://acm.timus.ru/problem.aspx?space=1&num=1863 - свежая задача на meet-in-the-middle.
→ Ответить
»
6 лет назад, # |
← Rev. 2   Проголосовать: нравится -16 Проголосовать: не нравится

Не пойму, зачем писать meet in the middle, если все задачи, которые я находил на это решались рекурсией намного быстрее(потому что не нужно было пересчитывать заново параметры задачи)?

→ Ответить