Сокращение набора неуникальных элементов с помощью преобразований

Question

у меня есть:

1) «стартовый набор», мультимножество, например {x, y, z, z},

2) набор преобразований, например. {x, z} => {y}, {z, z} => {z}, {x} => {z}, {y} => {x} и

3) «целевой набор», который я пытаюсь получить, применяя преобразования к начальному набору, например. {z}.

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

{ x, y, z, z }, y => x
{ x, x, z, z }, x => z
{ z, x, z, z }, x => z
{ z, z, z, z }, {z, z} => z
{ z, z, z }, {z, z} => z
{ z, z }, {z, z} => z
{ z }

Порядок элементов не имеет значения везде.

Звучит так, как будто это существующая (названная) проблема, но я ее не узнаю. Может кто-нибудь помочь мне отследить его или предложить дальнейшее чтение чего-нибудь подобного?

Answer 1

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

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

Answer 2

Это кажется очень сложной проблемой! Я полагаю, что даже проблема решения, чтобы определить, существует ли последовательность преобразований (чтобы преобразовать источник в цель), является Неразрешимой проблемой . Посмотрите на страницу Tag System на странице Список неразрешимых проблем .

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

n -> n/2 if n is even
n -> 3n+1 if n is odd

всегда заканчивается 1.

Эта гипотеза может быть сформулирована как:

с учетом набора преобразований

a -> bc
b -> a
c -> aaa

Может ли слово

aaa...aaa (a repeated n times)

в итоге преобразуется в слово

a

(одна буква а).

Поскольку преобразования принимают только один символ за раз, порядок не имеет значения: слово может рассматриваться как мультимножество и применимо к вашей проблеме.

Этот набор преобразований для гипотезы Коллатца был получен здесь: http://logica.ugent.be/liesbeth/TagColOK.pdf (см. Стр. 7).

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

Полагаю, вам просто нужно изучить все пути (используя BFS / A * как угодно) и надеяться, что вам повезет.

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

Итак, как вы сказали, выполните BFS / эвристику. Но теперь, после этой информации, я думаю, вы можете сделать это уверенно . : -)