Я работаю над проблемой комбинаторной оптимизации, которая, как я подозреваю, является NP-сложной, и генетический алгоритм хорошо работает с нашим набором данных. Мы исследовательская группа и планируем опубликовать наши результаты в нашей области (не в математике или CS), и я хотел бы изучить NP-сложный вопрос, прежде чем отправлять рукопись на рассмотрение.
Есть два основных вопроса:
1) Хотелось бы узнать, изучалась ли именно эта оптимизационная задача. Я тщательно искал освещенный, но не видел ничего точно такого же.
2) Если проблема не была изучена, я мог бы попробовать сделать доказательство сводимости и хотел бы получить несколько указателей на хороших NP-полных кандидатов для редукции.
Проблема может быть описана двумя способами: как вариант подпоследовательности и как проблема двудольного графа.
Во вкусе подпоследовательностей я хочу найти «расслабленную» подпоследовательность, которая допускает перестановки, и оптимизировать, чтобы минимизировать количество перестановок. Например: (. = Любой другой символ)
Запрос: abc, Цель: ..b.a.b.c., Результат: abc (обычная подпоследовательность)
Запрос: abc, Цель: ..b.a.c.a., Результат: bac (подпоследовательность с одной перестановкой)
Двудольная формулировка - это проблема сопоставления или задача линейного присвоения, при которой граф разделен на узлы символов запроса и узлы целевых символов. Ребра соединяют символы запроса с целевыми символами, так что есть ровно одно ребро от каждого символа запроса к целевому символу. Целевая функция состоит в том, чтобы минимизировать количество пересечений краев (также называемое «числом пересечений» в освещении). Это похоже на алгоритмы компоновки двудольного графа, которые меняют порядок размещения узлов, чтобы минимизировать пересечение ребер, но моя проблема требует, чтобы оба порядка узлов оставались фиксированными.
Есть мысли экспертов по вопросам 1 или 2?
Заранее спасибо!
