ГЛАВА 2
ПОСТРОЕНИЕ ЛИНЕЙНОЙ МОЗАИКИ
2.1. Постановка задачи
Эта задача в том или ином виде может встречаться в разных областях, где используется прямоугольная метрика. Всякое изображение на плоскости можно ограничить прямоугольником, затем разбить горизонтальными и вертикальными прямыми на маленькие клеточки, которые можно считать раскрашенными одним цветом.
Определение 2.1. Полем зрения ? называется прямоугольник, разбитый на N = mn клеток, где m - число клеток по горизонтали (строк), а n - число клеток по вертикали (столбцов).
Пусть задано некоторое множество шаблонов S = {s1, s2, . . . , sp}, где st
(t = 1, 2, . .. , p) - связная фигура из окрашенных клеток, а r(t) - количество таких фигур. Каждой клетке шаблона поставлено в соответствие число, которое принадлежит множеству Q \ {0} = {1, 2, . . . , K-1}. Можно говорить, что каждая клетка шаблона окрашена цветом \{0}. Задано множество раскрасок B поля зрения ? (в дальнейшем - поля), которое называется множеством образов (мозаик). На множестве Q введена бинарная коммутативная операция сложения цветов, которая произвольным и ставит в соответствие некоторое . Эта операция действует для каждой клетки поля при наложении шаблонов на него и удовлетворяет некоторым условиям. Наиболее часто такой операцией является сложение чисел по конечному модулю.
Если на поле наложить какой-либо шаблон, то цвета соответствующих клеток приобретут цвет, равный сумме прежнего цвета и цвета клеток шаблона. Можно накладывать несколько шаблонов на одно место. Задача состоит в том, чтобы на чистом поле (окрашенном в цвет 0) с помощью наличных шаблонов получить любой заданный образ.
В каждом шаблоне типа st может быть выделена одна клетка, которая
фиксирует положение шаблона на поле в горизонтальном (или вертикальном) положении. Будем называть такую клетку меткою шаблона. Если метка какого-либо шаблона st зафиксирована ? раз на клетке поля зрения l = n(i - 1) + j, (), то обозначим , в противном случае . Если шаблон накладывается на поле в вертикальном состоянии, то ему будет
соответствовать переменная . Если в качестве операции сложения выбрано сложение номеров цветов по mod К, то задача сводится к решению таких mn уравнений:
, l = 1, 2, . . . , N. (2.1)
Сформулируем задачу для произвольных операций сложения.
Постановка задачи. Пусть заданы множества шаблонов S и цветов Q и
операция сложения цветов . Необходимо найти такое подмножество S ' S и так наложить эти шаблоны на поле, чтобы в результате сложения цветов получить мозаику , где b = {b1, b2 , . . . , bN}.
В общем виде эта задача довольно сложная, так как число переменных в ней значительно превышает число уравнений. Поэтому возникают проблемы с определением ранга системы, что во многом зависит от типов шаблонов.
Кроме уравнения (2.1) можно вывести несколько зависимостей между шаблонами, если их накладывать на поле различными способами.
Самая простейшая зависимость получается для одинаковых линейных шаблонов, то есть шаблонов, представляющих набор ? горизонтальных клеток или ? вертикальных клеток, окрашенных одинаковою (рис.2.1). Нетрудно увидеть, что все вертикальные положения линейных шаблонов являются линейно зависимыми от горизонтальных шаблонов. Если взять ? горизонтальных шаблонов длины ?, расположенных строго один под другим, то это равносильно ? вертикальным шаблонам длины ?, расположенным в ряд строго один за другим. Таких зависимостей может быть очень много и для других разновидностей шаблонов, и обнаружить их не всегда возможно из-за большого количества уравнений и больших размеров поля. Поэтому необходимо разработать приемы, позволяющие разрешать подобные проблемы за счет локальных свойств конкретных шаблонов.
Рис. 2.1. Построение одинаковых образов разными шаблонами.
Если имеются горизонтальные шаблоны любой длины от 2 до n - 1, то можно всегда выразить с их помощью любую окрашенную клетку строки, начиная с первого и кончая последним столбцом. Будем называть такие клетки единицами.
2.2. Построение базиса решений задачи для двух одноцветных шаблонов.
В этой главе решается простая задача для набора прямолинейных шаблонов как последовательности клеток, окрашенных цветом 1 и длины st
(t ? 1) и множества Q = {0, 1}. Самое простое поле зрения это поле размером
1? n , или просто строка длиною n.
Определение 2.2. Будем считать выделенной клеткой (меткой) в каждом шаблоне самую крайнюю левую клетку. Номер клетки, на котором расположена метка шаблона, назовем его координатой.
В качестве операции сложения выберем сложение по mod 2.
Если сложить шаблон длиною d + 1 (d ? 2) с координатою j с шаблоном длиною d и координатою j + 1, то получим единицу в j-ой клетке.
Пронумеруем клетки поля от 1 до . Образом на таком поле будет произвольное множество черных клеток. Общее число образов (без учета пустого, окрашенного белым цветом) равно . Множество типов шаблонов будем задавать как множество чисел, где равно числу соответствующих черных клеток. Легко убедиться, что шаблон может разместиться на поле способом, если двигать его последовательно слева направо. Будем считать, что у нас есть копий шаблона ,
Можно сделать вывод, что достаточно уметь получать единицу с помощью линейных горизонтальных шаблонов в любой клетке строки, чтобы построить любой образ на линейном поле.
Определение 2.3. Наименьший набор шаблонов, который позволяет представить единицу в любой клетке строки, называется базисом линейной мозаики.
Самым тривиальным базисом является один шаблон S = {1}. Для двух шаблонов длиною s1 и s2, как было указано, базис может составлять набор
S = {d, d+1}(d > 1). При наложении двух таких шаблонов можно получить единицу либо справа, либо слева от меньшего шаб