Способ определить, может ли группа касательных узлов, которым присвоены значения на графике, быть добавлена ​​к конкретному значению?

Question

Я абстрагировал мою реальную проблему в более общую проблему с графами, чтобы спросить.

У меня есть неориентированный граф, где каждому узлу присваивается целое число. Как я могу определить, существует ли на графике группа соприкасающихся узлов, которые добавляют к определенному значению?

Редактировать: Подробнее: у меня есть сетка плиток, которые помечены положительным или отрицательным целым числом. Единственный «ход» будет состоять в том, чтобы объединить любую плитку с соседней плиткой (не по диагонали), оставляя зазор в сетке позади. Если объединяемая плитка имеет нулевое значение, она также удаляется. По сути, мне нужно делать тест после каждого удаления плитки со значением 0, чтобы увидеть, существуют ли еще какие-либо возможные «движения», приводящие к значениям 0, в сетке, даже если для получения требуется несколько комбинаций им.

Сетка только 6х6.

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

Answer 1

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

Очевидно, что это доступно, зависит от того, какой у вас график и каково точное определение узлов касания. Это просто конкретный узел и его соседи? В этом случае ваша диаграмма делает этот вид более подходящим, поскольку ни у одного узла нет более четырех соседей. Если n увеличивается с размером графика, вы, вероятно, попали в беду.

Редактировать - добавить 6x6 ответ

В сетке 6x6 модификация одного из алгоритмов суммы подмножеств выглядит дорого, но не невозможно.

С 18 узлами в верхней половине сетки, есть 2 ^ 18 шаблонов узлов, включая нулевой шаблон, который вы можете игнорировать, и некоторые из них не могут создавать смежные шаблоны, даже если, например, они соответствуют нижней половине, составленной из всех 18 узлов, так что вы можете сгенерировать и сохранить все возможные, например, по поиску возврата. 18-битное растровое изображение и сумма даже не занимают так много места на шаблон. Вы заканчиваете рано, если какая-либо сумма к нулю. Если нет, отбросьте все шаблоны без узлов на нижней строке и оставьте остальные.

Повторить - поменять местами самую низкую на самую высокую - с нижней половиной, а затем, для каждого узла в верхней половине, посмотреть на все шаблоны нижней половины с их суммой -ve верхней половины суммы. Если нижняя линия верхней половины совпадает с линией нижней половины и результат является смежным, у вас есть решение. Если вы не получили никаких ранних нулевых сумм, и ни один из шаблонов + (-a) не совпадает, то решения не существует.