Я пытаюсь создать алгоритм, который получает меня из одной строки битов, т.е. от 10110100 до 1100110100, с как можно меньшим количеством шагов. Шаги, которые могут быть применены, ограничены следующим:
a) anywhere, we may insert 10
b) anywhere, we may delete 10
This can be summarized as . <--> 10
Also, we may insert or remove a 01 as long as it's 'inside' another 01.
c) 01 --> 0011
d) 0011 --> 01
In other words: 01 <--> 0011
Так, например, в приведенных выше строках мы применяем
б) в 0:
10 110100 --> 110100
c) at 2:
11 01 00 --> 11 0011 00
a) at 5:
11001 100 --> 11001 10 100
и мы сделали 3 шага.
Я думаю, что это может быть сделано путем реализации минимального расстояния редактирования, но правила намного более строгие, чем с расстоянием Левешштейна. В частности, все, что вы можете заменить, зависит от символов на сайте. Я думал, что правильный путь для этого - считать «буквы» точками между битами, а затем есть 16 возможных символов, считая биты слева и справа.
Если это слишком сложно, правила могут быть смягчены, чтобы просто разрешить вставку и удаление 01 и 10 в любом месте, что с немного большим количеством работы эквивалентно, и я думаю, что я могу довольно легко восстановить самый быстрый маршрут, который подчиняется оригиналу правила.
Буду очень признательна за любую помощь, например, за название алгоритма!
К сожалению, я нашел только такие вещи, как Левештейн, в лучшем случае с расщеплением и слиянием, но, похоже, это не совсем та же структура.
Как уже говорилось, код должен находить не только расстояние, но и (неуникальную) оптимальную последовательность шагов, которые проходят от начала до цели, что, как я понимаю, довольно легко после построения матрицы Левенштейна.