Алгоритм сопоставления домино

Question

Учитывая некоторые входные данные, которые состоят из левого и правого символа, выходные цепочки связывают входные данные.

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

Выходы с более круглыми цепями (независимо от того, сколько или длина цепочки) - это то, что мы ищем. Например, выход из 3 круговых цепочек лучше, чем 1 большая цепочка и оставшееся одно домино.

Может ли кто-нибудь указать мне правильное направление? К какой группе проблем это относится и существуют ли алгоритмы для ее решения?

Примеры (выходные данные могут быть неверными!):

in[0]=(A,B)
in[1]=(B,C)
in[2]=(C,A)
out[0]=(0,1,2)

in[0]=(A,B)
in[1]=(B,A)
in[2]=(C,D)
in[3]=(D,C)
out[0]=(0,1)
out[1]=(2,3)

in[0]=(A,B)
in[1]=(B,A)
in[2]=(C,D)
in[3]=(E,F)
out[0]=(0,1)
out[1]=(2)
out[2]=(3)

in[0]=(A,B)
in[1]=(B,A)
in[2]=(C,D)
in[3]=(D,E)
out[0]=(0,1)
out[1]=(2,3)

in[0]=(A,B)
in[1]=(B,C)
in[2]=(C,D)
out[0]=(0,1,2)

Answer 1

Домино, которые нельзя перевернуть по горизонтали == ориентированные графы.

Помещение домино один за другим называется «путем», если это закрытый путь, это цепь.

Схема, которая включает в себя все вершины графа, является гамильтоновой схемой.

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

Answer 2

Проблема в том виде, в каком она есть сейчас, сформулирована не так ясно, как могла бы быть, - как именно оцениваются решения?Какой самый важный критерий?Это длина самой длинной цепочки?Есть ли штраф за создание цепочек длины один?

В таких задачах часто полезно визуализировать структуру в виде графика - скажем, назначить вершину (V [i]) для каждой плитки.Затем для каждого i, j создайте ребро между вершинами V [i], V [j], если вы можете поместить V [i] слева от V [j] в цепочке (поэтому, если V [i] соответствует (X, A) тогда V [j] соответствует (A, Y) для некоторых X, Y, A).

В таком графе цепочки - это пути, циклы - замкнутые («круговые») цепочки и задачабыл сокращен до нахождения некоторого цикла и / или пути для графа.Проблемы такого типа, в свою очередь, часто сводятся к проблемам соответствия или * потока (максимальный поток, максимальная стоимость, максимальный поток, минимальная стоимость, максимальный поток или что у вас есть).

Нопрежде чем вы сможете продолжить снижение, вы должны установить точные правила, согласно которым одно решение «лучше», чем другое.

Answer 3

Я не уверен, так ли это на самом деле, но, судя по вашим примерам, ваша проблема выглядит аналогично проблеме разложения перестановки на произведение непересекающихся циклов. Каждый фрагмент (X, Y) можно рассматривать как P (X) = Y для перестановки P. Если это согласуется с вашими предположениями, хорошая (или плохая) новость заключается в том, что такая декомпозиция уникальна (до порядка цикла) и очень легко найти. По сути, вы начинаете с любой плитки, находите подходящую плитку с другой стороны и следуйте ей до тех пор, пока соответствие не будет найдено. Затем вы переходите к следующей нетронутой точке. Если это не то, что вам нужно, то более общее решение на основе графов t.dubrownik выглядит как путь.

Answer 4

Легко проверить, существует ли круговая цепь, состоящая из всех домино. Для начала нужно сделать следующий ориентированный граф G:

• Узлы G - это символы в домино (A, B, C ..) в вашем примере,
• Для каждого домино (A, B) вы ставите направленный край от A до B.

Существует круговая цепочка, состоящая из всех домино, если существует Эйлеровый цикл в G. Чтобы проверить, существует ли Эйлеровый цикл в G, достаточно проверить, имеет ли каждый узел четную степень.