Заказать наборы чисел для максимального расстояния

Question

У вас есть (до 100) различных наборов (2-4) номеров. Порядок наборов или номеров в наборах не имеет значения. Наибольшее число относится к числу комплектов и увеличивается до 30. Нравится:

{1 2 3 4} {1 2 3 5} {1 2 3} {1 2 4 5} {6 2 4} {6 7 8 9} {6 7 9} {7 8 9} {2 4 8 9}

Цель состоит в том, чтобы расположить эти наборы в определенном порядке, где два последовательных набора не содержат общего числа. Это

{1 2 3 4} {2 4 8 9}

плохо (из-за 2). И

{1 2 3 4} {6 7 8 9}

это хорошо.

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

Я полагаю, что некоторый алгоритм «грубой силы» и «скоринг» невозможен при относительно большом количестве наборов. Есть ли у вас другие идеи или советы для детерминированного алгоритма для решения этой проблемы?

Как вы думаете, алгоритм shuffle + Score мог бы найти достойные решения (в течение некоторого ограниченного периода времени, например, 5 секунд, стандартного компьютера)?

Answer 1

Вы можете создать график из ваших наборов, где вершины - это наборы, и между ними есть ребра, если они могут быть последовательными в списке (то есть не имеют общего элемента).

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

Answer 2

Да, я думаю, что это возможно, если алгоритм правильно разработан. Здесь - пример решения аналогичной задачи для 60 «множеств» в 2,7 * 10 ^ 5 операций. Это число кажется достаточным для среднего современного компьютера.