Алгоритм количества переходов между парой множеств (графа) разбиений

Question

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

Например, существует один переход между разделами

1 2 | 3 и 1 | 2 | 3

, но между 1 2 3 4 и 1 2 | 3 | 4

Минимальное количество переходов составляет 2, как я полагаю.

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

Есть еще одно осложнение, что этот набор на самом деле представляет граф, и я бы хотел, чтобы каждыйраздел (и переходный раздел), который нужно подключить (т. е. 1 2 | 3 будет недопустимым, если между 1 и 2 не существует прямой / прямой связи, не заблокированной одним разделом 3), но если вы действительно не разбираетесь в этой теме, вы, вероятно, можете игнорироватьчто.

Спасибо

Как примечание, у меня есть метод, который я думал оЯ, в основном, должен найти всех соседей раздела A (то есть всех разделов, которые можно найти в одном переходе) и сделать то же самое для раздела B, и если это какое-то совпадение между этими двумя наборами соседей, то они находятся на расстоянии одного перехода,Однако этот метод очень быстро становится очень дорогим.

Answer 1

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

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

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