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

Автор AlexanderBolshakov, 12 лет назад, По-русски
  1. Задача: даны два множества точек на плоскости (оба размером N), нужно найти совершенное паросочетание с минимальным весом самого тяжелого ребра в нем (вес ребра — очевидно, Евклидово расстояние). Я умею решать Куном с бинпоиском по весу самого тяжелого ребра за O(N3logN). Вопрос: как решить эту задачу за чистый куб путем добавления в алгоритм какой-то жадности? Хопкрофта-Карпа и Диница прошу не предлагать. Ответ: вот так.

  2. Задача о поиске совершенного паросочетания в регулярном двудольном графе объяснялась в харьковской ЗКШ в этом году, но только для тех графов, в которых степени каждой вершины являются степенями двойки. Вопрос: как решать эту задачу для графов с произвольными степенями вершин? Применение алгоритма Хопкрофта-Карпа очевидно, но мне кажется, что существует что-то побыстрее.

  3. Задача: дан регулярный граф, нужно найти в нем гамильтонов цикл. Вопрос: существует ли алгоритм, который гарантированно найдет этот гамильтонов цикл за полиномиальное время, если он имеется?

  4. Эта задача с Тимуса имеет очевидное решение через паросочетание. Вопрос: можно ли обойтись без паросочетания и решить задачу жадно? Ответ: да, можно, а я тупой идиот, потому что думал как раз о таком решении, но не удосужился проверить 3 случая.

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

»
12 лет назад, # |
Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

2) Можно искать быстро (за O(m)), но это не совсем просто. Я знаю только алгоритм, который начинает с дробного паросочетания и постепенно округляет его до целого; хотя возможно есть что-то и попроще, по этой теме гуглится много разнообразных статей.

3) Нет^W Такого алгоритма науке неизвестно, доказано, что эта задача NP-complete.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    3) И что отсюда следует?))

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

      Из этого следует, что, если полиномиальный алгоритм найдётся,

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

        О чём и речь, копетан) Полиномиальный алгоритм вполне себе может существовать.

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

    3) а в двудольном ищется за полином? помню, например, макс. клика ищется, интересно про другие NP.

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

      Ну я про это ничего не знал, но в википедии написано, что эта задача NP-complete даже для bridgeless undirected planar 3-regular bipartite graphs.

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

        Я вчера ночью нагуглил, что в k-регулярных планарных графах с k >= 6 гамильтонов цикл ищется за полиномиальное время, но сам алгоритм не нашел (потому что почти не искал).

»
12 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

О, у меня тоже есть один вопрос про паросочетания, с этими не связанный: есть задача про покрытие ориентированного ациклического графа минимальным количеством неперескающихся путей, её решение описано на е-максе. Допустим, что пути могут пересекаться, тогда достаточно просто транзитивно замкнуть исходный граф и воспользоваться предыдущим решением. Проблема в том, что решение первой задачи работает за , а второй уже за O(V2.5). Вопрос — можно ли как-то использовать особый вид получившегося графа и ускорить решение?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Ну так транзитивное замыкание все равно за куб ищется. После этого можно паросочетание уже как угодно находить.

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

      И впрямь. Тогда интересно, как решать эту задачу(если не хотите регаться, то там 70 тестов, V ≤ 1000, E ≤ 10000, TL 4 секунды).

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        Транзитивное замыкание ищется за O(VE) запуском обхода из каждой вершины.

        Но даже если искать его за куб, то это очень быстрый куб из-за битовых операций.

»
12 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

4) каждый квадрат 4 на 4 обрабатываем отдельно — кладем либо два кирпича горизонтально либо вертикально

»
12 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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

»
12 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

1) Можно попробовать применить min-cost-max-flow. Паросочетание минимальной стоимости за куб мы находить умеем, если использовать дейкстру с потенциалами. Искать дейкстрой путь, в котором максимальное ребро минимально, мы тоже умеем, но здесь уже не получится так халявно добавить потенциалы (у сложения есть обратная операция, а у взятия обратного — нет). Если мы научимся добавлять потенциалы/каким-то другим способом искать кратчайший путь за O(V2), то будет решение ра куб.

Собственно, соображение, по которому не должна работать никакая жадность: если бы жадность работала, то паросочетания минимального веса можно было бы искать почти такой же жадностью.

upd: А не правда, что построив паросочетание минимального суммарного веса, мы в случае евклидовой плоскости решим и исходную задачу?

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

    Контрпример чуть ниже.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    А как все-таки находить паросочетание минимальной стоимости за куб?

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
      1. Венгерка
      2. Минкост с Дейкстрой с потенциалами

      UPD. Или Вам нужно рассказать Дейкстру с потенциалами поподробнее?

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

        Нет, спасибо, думал, может какой-то метод есть интересный еще — как-то не вспомнил, что это и есть по сути венгерский алгоритм.

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

̶1̶)̶ ̶В̶е̶н̶г̶е̶р̶с̶к̶и̶й̶ ̶а̶л̶г̶о̶р̶и̶т̶м̶ ̶р̶е̶ш̶и̶т̶ ̶э̶т̶у̶ ̶з̶а̶д̶а̶ч̶у̶ ̶з̶а̶ ̶к̶у̶б̶.̶ ̶Н̶а̶ ̶е̶м̶а̶к̶с̶е̶ ̶е̶с̶т̶ь̶ ̶ч̶т̶о̶ ̶п̶о̶ч̶и̶т̶а̶т̶ь̶ ̶п̶о̶ ̶э̶т̶о̶й̶ ̶т̶е̶м̶е̶.̶ В следующий раз обещаю внимательней читать условие...

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    Контрпример на сведение к задаче о назначениях: N == 2, первое множество: (0, -2) и (0, -1), второе множество: (0, 1) и (0, 2).

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    После сборов везде венгерка мерещится? =)

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

1) Если паросочетание искать не Куном, а Диницем или алгоритмом Хопкрофта-Карпа, сложность будет O(N^(5/2)*log(N))

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

    Это решение очевидно, надо было про него написать в топике. Меня интересует алгоритм не сложнее Куна (а, может быть, де-факто им и являющийся).

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

---придумал пример на котором не работает---

»
12 лет назад, # |
Rev. 3   Проголосовать: нравится +23 Проголосовать: не нравится

1) Подробностей не помню, но я точно писал какое то такое решение за точный куб: сортим все ребра по длине и запускаем куна. Как только не можем насытить вершину, то добавляем ребер до тех пор, пока не получится насытить. Если вспомню подробности — допишу.

upd. даже вот нашел задачу в архивах: http://acm.sgu.ru/problem.php?contest=0&problem=218

upd2. Ну вроде все. Когда насыщаем вершину, мы там строим дерево обхода бфс или дфс чтобы найти чередующуюся цепочку. Помечаем вершины обхода. Если не насытили — пробуем добавлять ребер, пока не добавим ребро из помеченой в непомеченную, запускаем дополнительный бфс/дфс по этому ребру (и опять же отмечаем вершины где побывали). И так далее. На одну насыщаемую вершину, в итоге получим чистый квадрат (потому что по сути у нас запуск одного бфс/дфс в несколько приемов). На весь алгоритм — чистый куб.

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

    Большое спасибо за объяснение. Как раз то, что надо. Завтра на свежую голову реализую.

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

      когда/если реализуете пожалуйста выложите сюда код, а то обяснение я понял не на 100%, а с кодом будет полностью понятно.

»
12 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Как с паросочетаниями решать?

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

    В-общем, нужно построить вот такой граф и найти в нем паросочетание (клетки раскрасил для наглядной демонстрации его двудольности).