Является ли эта комбинаторная задача оптимизации NP-hard?

Question

Я работаю над проблемой комбинаторной оптимизации, которую я подозреваю NP-hard, и генетический алгоритм хорошо работает с нашим набором данных. Мы - исследовательская группа и планируем опубликовать наши результаты в нашей области (не в математике или CS), и я хотел бы изучить NP-жесткий вопрос перед отправкой рукописи для обзора.

Есть два основных вопроса:

1) Я хотел бы знать, была ли изучена эта конкретная задача оптимизации. Я сильно искал свет, но ничего не видел.

2) Если проблема не была изучена, я мог бы сделать трещину при доказательстве сводимости и хотел бы, чтобы некоторые указатели были хорошими кандидатами на NP для сокращения.

Проблема может быть описана двумя способами, как вариант подпоследовательности, и как задача двудольного графа.

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

запросов: ABC, Цель: ..babc, Результат: ABC (нормальные подпоследовательности)

запросов: ABC, Цель: ..baca, Результат: BAC (подпоследовательности с одной перестановкой)

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

Любые мысли экспертов по вопросам 1 или 2?

Заранее благодарен!

Answer 1

Только некоторые идеи: Это как-то эквивалентно поиску минимального количества свопов, необходимых для сортировки массива (MIN-SBR)? Если да, то это NP-Hard.

(кстати, вы работаете над чем-то similar to this?)

Answer 2

Проблема с «проблемой слова» должно быть сложнее, не так ли? - J-16 SDiZ 14

Да, наличие нескольких вхождений персонажа в цель, похоже, делает мою проблему труднее, чем MIN-SBR, поэтому моя проблема будет по крайней мере такой же сложной, как NP-complete. С другой стороны, я пока не понимаю, как их центральное понятие блокировки блоков повлияет на мое требование NP-полноты.

Я уверен, было бы неплохо узнать, может ли моя оптимизация быть решена за полиномиальное время. Иными словами, было бы неловко, если бы рецензент вернулся с пятью строками псевдокода, который обнаруживает глобальный максимум в O (n).

Answer 3

Для piccolbo:

Если вы не публиковать в математике или сотовых станциях, NP-полнота результат будет иметь никакого значения и просто раздражает биолог или MD делать обзор. Был там.

Вы ставите. Первичный отчет будет посвящен мокрым результатам, но мы можем выбрать журнал, который будет более междисциплинарным. Кроме того, желание узнать о NP-ness является частью моего собственного назидания. Было бы неплохо использовать генетический алгоритм, если он полностью необоснован, и если есть способ найти гарантированный глобальный максимум в полиномиальное время. Сейчас GA находят хорошие решения, но, очевидно, сложно понять, найдет ли это лучшее решение.

В чем смысл перестановки? Один из них включает только два символа? Или только два соседних? Перестановка, которую я думаю в своем общем значении, позволяет перестроить всю строку, но тогда проблема становится тривиальной?

Это произвольное количество перестановок в целевой строке и минимизация числа перестановок (т. Е. Пересечений кромок в двудольной формулировке) является целевой функцией. Перестановки могут быть где угодно, и они независимо распределяются, поэтому смежность будет происходить (нечасто) случайно. Упорядочение запроса и целевых строк фиксировано, поэтому я не могу выполнить какую-либо перегруппировку.

Если я докажу это NP-hard, могу ли я получить соавторство?

Давайте посмотрим доказательство :-)

Answer 4

бы, запрос: а Цель: ..c.b.a.a Результат: CBA, три перестановки (в соответствии с вашим использованием термина), а затем? Если это так, то, возможно, вы имеете в виду транспозиции, а не перестановки. Транспозиция - это замена двух смежных символов.

Хороший вопрос. Нас интересует отображение из Query -> Target, которое имеет как можно меньше переходов. Это очень важная мотивация для упоминания двухсторонних краевых переходов в исходном посте. Кроме того, вы можете думать о максимизации статистики рангов, например, Rho Спирмена, над картированием.

Кроме того, из любопытства, сколько уникальных символов есть в запросе/цели? - Джастин Пил 18

Типичный запрос: 100, типичная цель: 1000. Комбинаторно, это огромное пространство для решения.

Answer 5

Я не думаю, что это NP-жесткий. См. Работу Певзнера и Ханнехали. Документ, который приходит на ум, называется «От капусты до репы». Идея состоит в том, чтобы найти минимальное количество инверсий для перехода от одной строки к другой. Для этого у них есть алгоритм polytime.