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

Автор vintage_Vlad_Makeev, 10 лет назад, По-русски

Здравствуйте!

При решении задачи наткнулся на следующую подзадачу: у нас есть n элементов и для каждой пары известен штраф за то, что они стоят рядом в перестановке. Необходимо сгенерировать перестановку с минимальным суммарным штрафом. Можно ли это решать быстрее, чем за O(N!) с отсечениями?

Спасибо!

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

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

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

У вас есть N городов и для каждой пары дорога известной длинны. Вы пытаетесь найти маршрут посещающий все города по одному разу с минимальной длинной.

Кажется что-то напоминает, если я конечно не туплю... ;-)

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

    Спасибо!

    Только вот в отличии от коммивояжера, нам не надо возвращаться домой.

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

      А много разницы-то?

      Вашу задачу можно привести к коммивояжёрской если добавить ещё один город расстояния из которого до всех остальных будут 0. Решаете TSP и удаляете этот город получая незамкнутый маршрут на множестве исходных городов. %)

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

        Действительно, спасибо большое!

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

          Не уверен что заслужил "спасибо" :)

          Во-первых вроде TSP точного решения намного быстрее предложенной вами ассимптотики не имеет, во-вторых то что незамкнутую задачу можно свести к замкнутой не означает обратного... :-o

          Но надеюсь более умудрённые коллеги либо подскажут, либо опровергнут меня!

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

            Сведение и правда не в ту сторону, однако концепция верная. В нужную сторону можно свести например так: заметим, что оптимальный цикл это ребро + некоторый кратчайший путь между двумя вершинами. Ребро будем перебирать, а кратчайший путь между его концами сводить к задаче выше: если мы хотим путь от a к b, то добавим вершины v1 и v2 и ребра a -> v1, b -> v2 и попросим кратчайший путь через все вершины в этом графе.

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

              ребро + некоторый кратчайший путь между двумя вершинами. Ребро будем перебирать

              О, здорово — теперь даже жалко что не догадался сам :)

              Спасибо!

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

Первое, что приходит в голову — можно за 2n * n2. Динамика вида DP[n][mask][last], mask — маска использованных элементов, last — последний использованный элемент.

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

    Параметр N не нужен — хватает маски.

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

    А еще кажется n на переход.

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

      В смысле?

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

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

        Ну в этой динамике 2n·n2 состояний. И переход я умею делать только за n. Итого асимптотика 2n·n3

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

          Блин... А как за 2n * n2 делать? Оо

          UPD: А, блин, last не нужон, да? То есть можно просто перебрать элементы в маске и прибавить по меньшему ребру.

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

за O(2^N*N^2) можно. поменяйте название поста, чтобы лучше отражало суть