Метод генерации палиндромов с помощью решения задачи ЦЛП
Ранее я уже показывал, как задача поиска разнобуквиц сводится
к задаче ЦЛП - целочисленного линейного программирования.
http://marinol.livejournal.com/165386.html
Чем это хорошо? Тем, что для решения таких задач существуют
эффективные алгоритмы, реализованные в виде работающих, отлаженных
пакетов программ.
Те, кто считает, что это представляет чисто теоретический интерес,
могут познакомиться с программой "Комбинаторный Поэт".
В этой программе такой подход реализован практически и позволяет быстро
находить разнобуквицы необходимого качества.
Здесь же мы попробуем применить аналогичный подход к задаче
создания палиндромов. Можно ли свести проблему создания палиндромов
к линейной задаче, для которой, как я уже сказал, имеются эффективные
алгоритмы и отлаженные программы? Ответ на этот вопрос положительный.
В этой заметке я приведу логику создания линейной модели для генерации
палиндромов. Вопросы её практического использования использования будут
освещены в другой (следующей) заметке. И, возможно, подход будет реализован
в одной из следующих версий программы Комбинаторный Поэт.
Глупо утверждать, что этот подход заменит умение и искусство опытных
палиндромистов. Но, наверное, он сможет быть для них каким-то существенным
подспорьем.
Итак, пусть мы имеем словарь слов S[i],i=1:N, N-количество слов в словаре.
И хотим создать палиндром длиной в M букв. В текущем варианте модели я буду
фиксировать длину палиндрома. Идея заключается в том, что мы вводим
целочисленную переменную X[i,j], которая означает, что слово с индексом i,
начинается в палиндроме с (буквенной) позиции j, если эта переменная имеет значение 1.
И 0, если слово S[i] не входит в палиндром с позиции j.
Ясно, что если не вводить никаких ограничений на вхождение слова в палиндром,
то будет хаос - разные слова смогут начинаться (и продолжаться) с одной и той же
позиции. Для того, чтобы прекратить это безобразие мы вводим матрицу структурных
ограничений R[j,k], где j=1,M - индекс строки матрицы, k=1:M*N. Каждой строке
матрицы соответствует позиция палиндрома, поэтому их M. Каждому столбцу матрицы k
соответствует некая переменная X[i,j], поэтому количество столбцов
будет равно ~ N (кол-во слов)*M(кол-во позиций).
Столбец матрицы R формируется следующим образом. Начиная со строки индексом j
в столбце B будет поставлено столько единиц (1), какова длина слова. Во всех остальных
позициях нужно проставить 0. Если мы возьмём и умножим матрицу R на вектор X
то получим вектор B, размером M строк (длина палиндрома). Что он будет означать?
Он будет давать количество слов, чьи буквы находятся на каждой позиции палиндрома.
НО... в палиндроме (да и в любом другом ПРЕДЛОЖЕНИИ) на каждой позиции находится
буква от ОДНОГО слова. Поэтому, если мы имеем вектор B состоящим только из единиц (1),
то задав условие (линейное, это важно) R*X=B, мы гарантируем, что переменные будут
выбираться так, чтобы слова не пересекались, а образовывали одну линейную
последовательность.
Фу, уже легче. Но это не всё. Ведь нам нужен палиндром.
Чем характеризуется палиндром, тем, что на позиции L, L=1:M, находится
та же буква, что и на позиции M-L+1. Например, если L=1 (начало слова), то
такая же буква должна быть на позиции M-1+1 = M, то есть в конце слова.
И так далее со смещением к центру палиндрома.
Для того, что бы это формализовать, вводим матрицу W[j,k], j=1:M, k=1:M*N,
которая полностью аналогична матрице R, но... в ячейках матрицы находятся
не нули или единицы, а числа представляющие собой числовые КОДЫ соответствующих
букв каждого слова. Тогда если мы возьмём произведение матрицы W на вектор
переменную X, то получим вектор P, который ... в чистом виде даёт нам
последовательность слов (точнее букв), включённых в 'палиндром'. Для того,
что я смог убрать кавычки у слова палиндром в предыдущем предложении, мне
нужно лишь правильно задать 'палиндромные' ограничения. Как их задать ?
Очень просто:
P[L]=P[M-L+1], где L=1,M.
Как мы видим все ограничения, которые мы вводили
линейны, то есть для решения задачи вполне можно пользоваться пакетами
решения задач целочисленного линейного программирования.
В качестве критерия (а также дополнительных ограничений) можно задавать
различные выражения, (как в задаче о разнобуквицах). Например можно задать
ограничения, чтобы любое слово не входило более двух раз в палиндром.
Или чтобы в палиндроме было от 4 до 6 существительных. Или, чтобы в палиндроме
обязательно были заданные слова (неважно на каких позициях, или наоборот
в определённых).
Вопросы практического применения, то есть того, насколько полезна такая
формализация, будем обсуждать в следующей статье.
Аналогичный подход может быть применён для генерации пантограмм.
к задаче ЦЛП - целочисленного линейного программирования.
http://marinol.livejournal.com/165386.html
Чем это хорошо? Тем, что для решения таких задач существуют
эффективные алгоритмы, реализованные в виде работающих, отлаженных
пакетов программ.
Те, кто считает, что это представляет чисто теоретический интерес,
могут познакомиться с программой "Комбинаторный Поэт".
В этой программе такой подход реализован практически и позволяет быстро
находить разнобуквицы необходимого качества.
Здесь же мы попробуем применить аналогичный подход к задаче
создания палиндромов. Можно ли свести проблему создания палиндромов
к линейной задаче, для которой, как я уже сказал, имеются эффективные
алгоритмы и отлаженные программы? Ответ на этот вопрос положительный.
В этой заметке я приведу логику создания линейной модели для генерации
палиндромов. Вопросы её практического использования использования будут
освещены в другой (следующей) заметке. И, возможно, подход будет реализован
в одной из следующих версий программы Комбинаторный Поэт.
Глупо утверждать, что этот подход заменит умение и искусство опытных
палиндромистов. Но, наверное, он сможет быть для них каким-то существенным
подспорьем.
Итак, пусть мы имеем словарь слов S[i],i=1:N, N-количество слов в словаре.
И хотим создать палиндром длиной в M букв. В текущем варианте модели я буду
фиксировать длину палиндрома. Идея заключается в том, что мы вводим
целочисленную переменную X[i,j], которая означает, что слово с индексом i,
начинается в палиндроме с (буквенной) позиции j, если эта переменная имеет значение 1.
И 0, если слово S[i] не входит в палиндром с позиции j.
Ясно, что если не вводить никаких ограничений на вхождение слова в палиндром,
то будет хаос - разные слова смогут начинаться (и продолжаться) с одной и той же
позиции. Для того, чтобы прекратить это безобразие мы вводим матрицу структурных
ограничений R[j,k], где j=1,M - индекс строки матрицы, k=1:M*N. Каждой строке
матрицы соответствует позиция палиндрома, поэтому их M. Каждому столбцу матрицы k
соответствует некая переменная X[i,j], поэтому количество столбцов
будет равно ~ N (кол-во слов)*M(кол-во позиций).
Столбец матрицы R формируется следующим образом. Начиная со строки индексом j
в столбце B будет поставлено столько единиц (1), какова длина слова. Во всех остальных
позициях нужно проставить 0. Если мы возьмём и умножим матрицу R на вектор X
то получим вектор B, размером M строк (длина палиндрома). Что он будет означать?
Он будет давать количество слов, чьи буквы находятся на каждой позиции палиндрома.
НО... в палиндроме (да и в любом другом ПРЕДЛОЖЕНИИ) на каждой позиции находится
буква от ОДНОГО слова. Поэтому, если мы имеем вектор B состоящим только из единиц (1),
то задав условие (линейное, это важно) R*X=B, мы гарантируем, что переменные будут
выбираться так, чтобы слова не пересекались, а образовывали одну линейную
последовательность.
Фу, уже легче. Но это не всё. Ведь нам нужен палиндром.
Чем характеризуется палиндром, тем, что на позиции L, L=1:M, находится
та же буква, что и на позиции M-L+1. Например, если L=1 (начало слова), то
такая же буква должна быть на позиции M-1+1 = M, то есть в конце слова.
И так далее со смещением к центру палиндрома.
Для того, что бы это формализовать, вводим матрицу W[j,k], j=1:M, k=1:M*N,
которая полностью аналогична матрице R, но... в ячейках матрицы находятся
не нули или единицы, а числа представляющие собой числовые КОДЫ соответствующих
букв каждого слова. Тогда если мы возьмём произведение матрицы W на вектор
переменную X, то получим вектор P, который ... в чистом виде даёт нам
последовательность слов (точнее букв), включённых в 'палиндром'. Для того,
что я смог убрать кавычки у слова палиндром в предыдущем предложении, мне
нужно лишь правильно задать 'палиндромные' ограничения. Как их задать ?
Очень просто:
P[L]=P[M-L+1], где L=1,M.
Как мы видим все ограничения, которые мы вводили
линейны, то есть для решения задачи вполне можно пользоваться пакетами
решения задач целочисленного линейного программирования.
В качестве критерия (а также дополнительных ограничений) можно задавать
различные выражения, (как в задаче о разнобуквицах). Например можно задать
ограничения, чтобы любое слово не входило более двух раз в палиндром.
Или чтобы в палиндроме было от 4 до 6 существительных. Или, чтобы в палиндроме
обязательно были заданные слова (неважно на каких позициях, или наоборот
в определённых).
Вопросы практического применения, то есть того, насколько полезна такая
формализация, будем обсуждать в следующей статье.
Аналогичный подход может быть применён для генерации пантограмм.