Короче, есть такая задачка... Дана текстовая строка X состоящая из букв некого алфавита. Над этой строкой можно производить следующие операции: 1.Замена участка текста с позиции P и длинной L на произвольный текст той же длинны (частный случай – замена одной буквы). 2.Вставка в позицию P произвольного текста длинной L. 3.Удаление куска текста длинной L в позиции P. 4.Инверсия текста в позиции P и длинной L (например: ABCDEF может превратиться в ADCBEF) 5.Дубликация текста в позиции P и длинной L в новую позицию P1 (например: ABCDEF – ABCDEABCF) В результате определенной последовательности действий получается новая строка Y. Как решить прямую задачу (т.е. дана X и последовательность действий) понятно! А вот как решить обратную задачу (т.е. дана X и Y, надо найти все возможные последовательности действий, которые привели к преобразованию X в Y)??? Такая задача вообще решена??? Что можно почитать по этой теме? В какую сторону капать?
sonjia _Все_ возможные последовательности действий найти не удастся, т.к. их бесконечное количество(в частности благодаря 2 и 3) Может речь идет о минимальной последовательности?
Stiver Вряд ли, т.к. минимальная последовательность всегда <=2: 0 при X==Y; 1 при X!=Y, strlen(X)==strlen(Y); 1 или 2 при X!=Y, strlen(X)!=strlen(Y);
ash Так это смотря относительно чего минимальная. Ты предлагаешь минимировать количество операций, логичней наверное минимировать количество измененных знаков. В общем случае можно например присвоить каждой операции определенную "стоимость" (зависящую от количества знаков) и минимировать суммарную стоимость преобразования X в Y.
Более точная постановка задачи... Дана текстовая строка X состоящая из букв некого алфавита. Над этой строкой можно производить следующие операции редактирования: 1. Замена подстроки с позиции P и длинной L на произвольную подстроку той же длинны. 2. Вставка в позицию P произвольного текста длинной L. 3. Удаление подстроки длинной L в позиции P. 4. Инверсия текста в позиции P и длинной L. 5. Дубликация подстроки в позиции P и длинной L в новую позицию P1. В результате определенной последовательности действий получается новая строка Y. Каждая операция имеет свою цену. Эта цена зависит от длинны подстроки (L), ее позиции (P) и от ряда других факторов (все это задается перед началом работы). Необходимо найти все последовательности операций редактирования с суммой их цен: 1. находящийся в некотором заданном интервале. 2. если такой не задан, то искать с минимальной суммой цен (но эта сумма цен должна быть больше или равна некоторого заданного минимального значения, частный случай – минимальное значение равно 0).
sonjia Эта задача эквивалентна проблеме поиска минимального пути на заданном рельефе(т.е. дается функция образующая рельеф, две точки и надо найти путь с минимальным суммарным перепадом высоты) с поправкой на в данном случае дискретный рельеф. А это в свою очередь одна из стандартных задач нелинейного/дискретного оптимирования. Существует довольно много литературы, ищи в сторону route finding, path planning и т.д. Известные простые алгоритмы/эвристики например A* search, best first search.
