Как найти кратчайший путь, который проходит через группу множеств? - PullRequest
Новая
       101

Как найти кратчайший путь, который проходит через группу множеств?

0 голосов
/ 14 февраля 2019

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

Например, пусть будут следующие 4 неупорядоченных набора: A = АБВГДЕЖ B = CD C = abch D = Defi

Размер кратчайшего пути - 11 .

Одним из возможных решений является: P = CADB = habcgdeficd| P | = 11

Обратите внимание, что наборы могут совместно использовать элементы с соседними наборами в пути!Также могут быть дублированные элементы, принадлежащие разным наборам (как в примере выше: «c» и «d» дублируются в P , путем добавления B к CAD ).

Посоветуйте с алгоритмом найти кратчайший путь, как описано.Спасибо!

Ответы [ 2 ]

0 голосов
/ 17 февраля 2019

Этот вопрос может быть сведен к варианту Кратчайшей общей проблемы суперструн

0 голосов
/ 14 февраля 2019

У вас есть график:

  • узлом являются множества;
  • ребро A-B существует, если A и B имеют пересечение, но не являются подмножествомодин из другого;
  • если существует ребро A-B, расстояние A-B равно размеру A union B.

Вы ищетекратчайший путь, который охватывает все узлы.Это вариант задачи коммивояжера без необходимости возврата к началу.

Некоторое чтение: Как называется проблема для задачи коммивояжера (TSP) безрассматриваете возможность возврата к исходной точке?

РЕДАКТИРОВАТЬ: Я пытаюсь обобщить то, что обсуждалось в комментариях и моих ответах.

  1. Что не было ясно в вопросе: что вы будете делать, если набор является надмножеством другого?Я предположил, что вы хотите разделить эти два набора, поэтому я написал: «ребро AB существует, если A и B имеют пересечение, но не являются подмножествами друг друга».Для TSP просто используйте бесконечное расстояние между наборами A и B, если ребро не существует.Это относится к подмножествам / надмножествам.

  2. Путь упорядочен (по определению пути), но наборы неупорядочены.Вот почему это не тривиальная вариация самой короткой общей проблемы суперструн.Строка упорядочена, номер набора

  3. Идея TSP не очень хорошо работает с расстоянием, определенным выше, потому что:

    • определениерасстояние не хорошее: расстояние должно строго уменьшаться при увеличении пересечения.Решение было бы max(len(S)) - len(A ^ B).
    • более важным: вам не разрешено использовать одни и те же буквы на «обеих сторонах» набора.Например, «abc» не может быть на расстоянии 1 от «bcd» и на расстоянии 2 от «eb», потому что если вы выберете путь «a-bc-d», то ребро «abc» - «eb» не будетбольше не существуетМожет быть, жадный выбор поможет, но я не уверен.
...