Динамическое программирование - основной алгоритм

Question

Рассмотрим следующую проблему:

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

Исходные последовательности могут выглядеть следующим образом: последовательность, которую мы хотим достичь,отображается справа:

C   G                     
G   C                     
C   G                     G
C   C                     C
G   G                     G
 \ /
  ?

Теперь в точке ? можно выбрать левую или правую загрузку.Выбор должен быть сделан, чтобы соответствовать требуемой конечной последовательности.

Например, мы должны выбрать Grain в начале, и тогда картина станет такой:

    G                     
C   C                     
G   G                     G
С   C                     C
С   G                     G
 \ /
  ?  ---> G (we took it from the left)

---

Итак, есть ли у этой проблемы общеизвестное имя? Я понимаю, что это можно решить простым алгоритмом динамического программирования, но я хочу знать больше.

В основном, если естьЧто-то еще, чтобы прочитать об этой проблеме, я хотел бы прочитать это. Например, я не имею представления о сложности алгоритма, если у нас бесконечное число конечных входных последовательностей.

Answer 1

У меня нет особой проницательности, чтобы поделиться, но вот оно:

• Давайте назовем грузы 0 и 1 вместо C и G, более того, давайте обозначим две очереди0 и 1 вместо правого и левого.

• Сначала алгоритм не может быть решен с бесконечными (потоковыми) входными последовательностями.В случае двух входных последовательностей, имеющих только 0, а затем 1 вне «окна видимости потоковой передачи», вы не можете стремиться к этому 1, если ваша последовательность результатов нуждается в этом, поэтому вы можете застрять, пока был ответ.

• Поскольку мы не можем говорить о бесконечности, давайте проанализируем сложность решателя.Я не вижу ничего лучше, чем ваш алгоритм ... Если результирующая последовательность имеет длину m и мы моделируем результат как последовательность 0 и 1 (для правой и левой), есть 2 ^ m возможных решений.Если учесть, что на каждом шаге, в среднем , есть один шанс из двух, что будет действительна только одна входная последовательность, это означает, что другая последовательность будет недействительной, как и другие последующие последовательности.Это должно привести к сложности O (m!).

Answer 2

Теоретик формального языка описал бы вашу проблему как проверку того, является ли строка w shuffle из двух строк u, v. Кажется, была проделана некоторая работа над сложностью распознавания языков, построенных с использованием перемешиванийнапример, перетасовывание языка без контекста и обычного языка не зависит от контекста).