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

Задача коммивояжера на разреженном графе
Автор Tigutor, история, 5 лет назад, По-русски

Недавно передо мной встала задача — найти цикл минимального веса в взвешенном графе на 20 вершин и 100 ребер. Используя обычный dfs-подход(смотрим исходящие рёбра из текущей вершины, рекурсивно запускаемся от детей), и оптимизацию, что если текущий путь больше минимального найденного, то продолжать нет смысла, я получил TL Прошу вашего совета — какие ещё оптимизации тут можно применить?

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

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

Добавить к перебору меморизацию

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

    Что тут можно запоминать, кроме того что я упомянул?

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

      результаты для подмножеств. в любой момент в дфсе вершины делятся на использованные и нет. использованные образуют подмножество.

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

      dp[v][msk] — путь минимального веса из вершины 0 в вершину v используя вершины из msk.

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

Советую почитать про ДП по подмножествам. Задачи, где n примерно равно 20, часто именно так и решаются. Например, здесь.

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

    Чуть чуть дольше, чем нужно Может какие-то эвристики применить, чтобы ответ находился с большой вероятностью?

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

Вроде бы цикл минимального веса решается за O(M^2 log M) путем перебора удаляемого ребра и запуска Дейкстры

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

    Тут это не пройдёт, нужен гамильтонов цикл, это NP-полная задача

    → Ответить