Найти экстремум для функции приоритета / алфавитный порядок

Question

У нас есть массив элементов a1,a2,...aN из алфавита E. Предполагая, |N| >> |E|.

Для каждого символа алфавита мы определяем уникальный целочисленный приоритет = V(sym). Давайте определим V{i} := V(symbol(ai)) для простоты.

Как найти функцию приоритета V, для которой:

Count(i)->MAX | V{i} < V{i+1}

Другими словами, мне нужно найти приоритеты / перестановки алфавита, для которых число позиций i, удовлетворяющих условию V{i}<V{i+1}, является максимальным.

Правка-1: Пожалуйста, прочитайте внимательно. Мне дан массив ai, и задача состоит в том, чтобы создать функцию V. Это не о сортировке входного массива с функцией приоритета.

Edit-2: Пример

E = {a,b,c}; A = 'abcab$'; (здесь $ = символ искусственного завершения, V {$} = + бесконечность)

Одна из оптимальных функций приоритета: V{a}=1,V{b}=2,V{c}=3, которая дает нам следующие знаки между элементами массива: a<b<c>a<b<$, что приводит к 4 '<' знакам из 5.

Answer 1

Существует тривиальное сокращение от минимального набора дуг обратной связи для ориентированных графов, дуги которых могут быть расположены по эйлерову траектории. Я цитирую http://www14.informatik.tu -muenchen.de / personen / jacob / Publications / JMMN07.pdf :

Насколько нам известно, статус сложности минимальной обратной связи дуга, заданная на таких графиках, является открытой. Тем не менее, по лемме Ньюмена, Чен, и Ловас [1, теорема 4], а полиномиальный алгоритм для [этой проблемы] приведет к приближению 16/9 алгоритм для общего минимума задание дуги обратной связи, улучшение над самым известным в настоящее время O (log n log log n) алгоритм [2].

1. Newman, A .: Задача максимального ациклического подграфа и графы степени 3. В: Материалы 4-го Международный семинар по Аппроксимационные алгоритмы для Комбинаторные проблемы оптимизации, ПРИБЛИЗИТЕЛЬНО. LNCS (2001) 147–158

2. Даже Г., NaOR, J., Шибер, B., Судан, М.: Approximatingminimumfeedbacksets и множественные разрезы в ориентированных графах. В: Материалы 4-го Интернационала Конференция по целочисленному программированию и комбинаторная оптимизация. LNCS (1995) 14–28

Answer 2

Если бы элементы не могли иметь связанные приоритеты, это было бы тривиально. Просто сортировка по приоритету. Но у вас могут быть равные приоритеты.

Сначала я бы отсортировал алфавит по приоритету. Тогда я бы извлек самую длинную восходящую подпоследовательность. Это начало вашего ответа. Извлеките самую длинную восходящую последовательность из того, что осталось. Добавьте это к вашему ответу. Повторяйте процесс извлечения, пока не будет извлечен весь алфавит.

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

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

Чтобы увидеть это, давайте сначала построим ориентированный граф, вершинами которого являются ваши элементы, а ребра которого указывают, сколько раз один элемент непосредственно предшествовал другому. Вы можете создать функцию приоритета, отбрасывая достаточное количество ребер, чтобы получить ориентированный ациклический граф, используя ребра, чтобы создать частично упорядоченный набор, а затем добавляйте отношения порядка, пока не получите полный линейный порядок, из которого вы можете легко получить функцию приоритета. Все это просто, если вы определили, какие края нужно отбрасывать. И наоборот, с учетом этого ориентированного графа и вашей функции конечного приоритета легко определить, какой набор ребер вы решили отбросить.

Следовательно, ваша задача полностью эквивалентна вычислению минимального набора ребер, которые вам нужно отбросить с a этого ориентированного графа, чтобы получить a этого направленного ациклического графа. Однако, как говорит http://en.wikipedia.org/wiki/Feedback_arc_set, это известная сложная проблема NP, называемая минимальным набором дуг обратной связи. начать обновление Поэтому очень маловероятно, что существует хороший алгоритм для графиков, который вы можете придумать. конец обновления

Если вам нужно решить это на практике, я бы предложил использовать какой-нибудь жадный алгоритм. Это не всегда будет правильно, но в целом даст разумные результаты в разумные сроки.

Обновление: Морон правильно, я не доказал NP-хард. Однако есть веские эвристические причины полагать, что проблема, на самом деле, NP-сложная. Смотрите комментарии для более.