Есть ли алгоритм, который делит квадратную сетку на 3 или 4 равных пространства?

Question

Так, например, я разделил свою карту на что-то вроде этого: нажмите на ссылку

представитель матрицы будет

0 1 0 1 0

1 1 1 1 0

0 1 1 1 1

0 1 0 0 0

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

, где общая площадь равна 11, а поскольку 11/3 дает нам десятичную дробь, мне нужно иметь 2 пробела с 4 квадратами и один пробел с 3 квадратами.

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

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

1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 0
0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1

Каждое значение - это квадрат на карте, а 1 - это квадрат, который следует учитывать. 0 - это пустое / пустое пространство, которое не является частью карты и не должно учитываться при делении карты.

Пока что я пробую цикл for, добавляя все значения и деля их на 3, чтобы определить, сколько квадратов необходимо для каждого пробела. Кроме того, если я получу десятичную дробь, то один пробел может иметь еще один квадрат, чем другой Таким образом, в этой задаче есть 36 квадратов, поэтому, если я попытаюсь разделить его на 3 поля, то в каждом пространстве будет 12 квадратов.

Так что я смотрю, есть ли алгоритм, который сможет решить все типы карт.

Answer 1

Это на самом деле NP-hard для k> = 2, где вы хотите k = 3 или k = 4:

теорема 2.2 в О сложности разбиения графов на связные подграфы - М.Е. Дайер, А.М. FRIEZE

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

Было бы полезно, если бы вы дали более строгое определение «четного ишага» - например, рассмотрите карту с 13 узлами - вы бы предпочли деления по размеру (4,4,5), (3,3, 3,4), (4,4,4,1), (5,5,3) или (4,4,3,2)?