Сколько комбинаций k соседних пикселей на изображении?

Question

Я отстой в математике, поэтому не могу понять: сколько комбинаций k соседних пикселей на изображении? Комбинации из k пикселей из n * n общих пикселей изображения, но с ограничением на то, что они должны быть соседями, для каждого k от 2 до n * n. Мне нужна сумма для всех значений k для программы, которая должна учитывать столько элементов в наборе, о которых она рассуждает.

Соседи 4-соединенные и не имеют циклического перебора.

Answer 1

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

Если я понимаю ваш вопрос, вы пытаетесь посчитать пути длины k следующим образом:

Start          (end)-> any pixel after visiting k neighbours
*     - - - - -*
|     |
|     |
- - - -

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

Я думаю, что вы хотите, чтобы пути были самодостаточными, а это означает, что пиксель не должен пересекаться дважды за шаг (то есть без петель). Это условие приводит к классической проблеме под названием SAWs (Self Avoiding Walks).

Хорошо, теперь плохие новости: проблема открыта! Никто еще не решил это.

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

Надеюсь, это поможет ... чтобы избежать проблемы.

Answer 2

Как только вы получите количество различных фигур для сгустка пикселей размером k ( вот ссылка ), тогда все сводится к двум вещам:

• Сколько способов на вашем изображении вы можете разместить этот шарик?
• Сколько из них одинаково, чтобы вы не учитывали дважды (из-за симметрии)?

Получение точного ответа - огромная вычислительная работа (вы смотрите на более чем 10 ^ 30 различных форм для k = 56 - представьте, если k = 10000), но вы можете быть достаточно хороши для того, что вам нужно путем подбора первых 50 значений k.

(Примечание: ссылка в статье в Википедии заботится о дубликатах с их определением A_k.)

Answer 3

Если вы планировали перебрать все возможные polyominos , боюсь, вы будете ждать долго.На сайте Википедии о Поломино это будет как минимум O (4.0626 ^ n) и, вероятно, ближе к O (8 ^ n).К моменту n = 14 число будет более 5 миллиардов и будет слишком большим, чтобы вписаться в int.К моменту времени n = 30 счет будет больше 17 квинтиллионов, и вы не сможете его долго разместить.Если бы все мировые правительства объединили свои ресурсы, чтобы перебрать все множители в значке 32 x 32, они не смогли бы сделать это до того, как солнце станет сверхновой.делать трудно.Вероятно, почти вся работа, которую вы выполняете на одном полиоминале, была частично выполнена на других.Это может быть забавная задача, сделать экспоненциальное ускорение с помощью динамического программирования.Чего вы пытаетесь достичь?