Линейное программирование с усложнением

Question

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

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

Это похоже на прямую проблему линейного программирования, за исключением того факта, что одна фраза может быть подфразой другой. Так, например, если ваши входные фразы включают в себя «foo bar» и «foo», то если вы повторите фразу «foo bar», вы также повторите фразу «foo». Я не знаю, как с этим справиться в модели линейного программирования.

Answer 1

У вас есть другая проблема, объединение двух фраз может образовать третью фразу. Например, если у вас есть

list...4
sting...6
ingrave...7
abcd...5

тогда решение "listingrave" имеет "усиление" 17, тогда как все, что вы можете сделать с "abcd" ("abcdingrave"), имеет только 12, хотя для длины 4 "abcd" - это оптимальный.

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

ОБНОВЛЕНИЕ: должно работать так:

1. Создание DFA из алгоритма поиска текста Aho-Corasick
2. Поиск обхода (не пути, т. Е. Вы разрешаете повторные ребра и вершины) заданной длины с максимальным усилением, начиная с начального состояния DFA. Вы можете сделать это с помощью динамического программирования (строить более длинные прогулки из более коротких на 1 символ).

Answer 2

Похоже, что это может быть решено как проблема с рюкзаком , см. http://en.wikipedia.org/wiki/Knapsack_problem, с весами, определенными в соответствии с gs.

Answer 3

Возможно, это сработает, если использовать только динамическое программирование и каждый раз пересчитывать все это. Можно было бы использовать множество оптимизаций, чтобы ускорить его. (Как попытка пересчитать только последнюю часть) Я думаю, что скорость будет разумной. O (n ^ 2 * m) или около того.

Answer 4

Просто пересчитайте вес. Например:

key = 3
board = 2
keyboard = 5

Это изменится на:

key = 3
board = 2
keyboard = 5 + 3 + 2 = 10

Если вы делаете это, вы должны остерегаться фраз, которые включают фразу, которая включает фразу. Вы должны убедиться, что не делаете этого:

ey = 7
key = 3 + 7
board = 2
keyboard = 5 + 7 + (3 + 7) + 2

Вы можете избежать этого, упорядочив список после длин фраз. (Самый длинный первый)

Кстати: разве это не проблема динамического программирования ?