Encuentra el extremo para la función de prioridad/orden alfabético

Question

Tenemos una matriz de elementos a1,a2,...aN de un alfabeto E. Asumiendo |N| >> |E|.

Para cada símbolo del alfabeto definimos una prioridad entera única = V(sym). Definamos V{i} := V(symbol(ai)) por la simplicidad.

¿Cómo puedo encontrar la función de prioridad V para los cuales:

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

En otras palabras, necesito encontrar el prioridades/permutación del alfabeto para los que el número de posiciones i, que satisfacen la condición V{i}<V{i+1}, es máximo

Edit-1: Por favor, lea atentamente. Me dieron una matriz ai y la tarea es producir una función V. Es no sobre la clasificación de la matriz de entrada con una función de prioridad.

Editar-2: Ejemplo

E = {a,b,c}; A = 'abcab$'; (aquí $ = símbolo de interrupción artificial, V {$} = + infinito)

Una de las funciones prioritarias óptimas es: V{a}=1,V{b}=2,V{c}=3, que nos la da siguiendo las señales entre los elementos de la matriz: a<b<c>a<b<$, lo que da como resultado 4 '<' signos de 5 en total.

Answer 1

Si los elementos no podrían tener prioridades vinculadas, esto sería trivial. Solo ordena por prioridad. Pero puedes tener las mismas prioridades.

Primero ordenaría el alfabeto por prioridad. Luego extraería la subsecuencia ascendente más larga. Ese es el comienzo de tu respuesta. Extraiga la subsecuencia ascendente más larga de lo que queda. Añádelo a tu respuesta. Repita el proceso de extracción hasta que se haya extraído todo el alfabeto.

Creo que esto da un resultado óptimo, pero no he intentado probarlo. Si no es perfectamente óptimo, todavía será bastante bueno.

Ahora que creo que entiendo el problema, puedo decirte que no hay un buen algoritmo para resolverlo.

Para ver esto vamos a construir primero un gráfico dirigido cuyos vértices son sus elementos, y cuyos bordes indican cuántas veces un elemento precedió a otro. Puede crear una función de prioridad dejando caer los bordes suficientes para obtener un gráfico acíclico dirigido, usar los bordes para crear un conjunto parcialmente ordenado y luego agregar relaciones de orden hasta que tenga un orden lineal completo, desde el cual puede obtener una función de prioridad trivialmente. Todo esto es sencillo una vez que haya descubierto qué bordes caer. Por el contrario, dado que el gráfico dirigido y su función de prioridad final, es fácil averiguar qué conjunto de bordes tuvo que decidir caer.

lo tanto, su problema es totalmente equivalente a averiguar un conjunto mínimo de bordes que necesita para dejar de un que dirigieron el gráfico para obtener un que grafo acíclico dirigido. Sin embargo, como dice http://en.wikipedia.org/wiki/Feedback_arc_set, este es un problema conocido de NP conocido como el arco de retroalimentación mínimo establecido. begin update Por lo tanto, es muy poco probable que haya un buen algoritmo para los gráficos que se le ocurran. final update

Si necesita resolverlo en la práctica, sugiero ir a algún tipo de algoritmo codicioso. No siempre será correcto, pero generalmente dará resultados algo razonables en un tiempo razonable.

Actualización: Moron es correcto, no probé NP-hard. Sin embargo, hay buenas razones heurísticas para creer que el problema es, de hecho, NP-hard. Vea los comentarios para más.

Answer 2

Hay una reducción trivial del conjunto de arco de retroalimentación mínima en los gráficos dirigidos cuyos arcos se pueden organizar en una ruta euleriana. Cito de http://www14.informatik.tu-muenchen.de/personen/jacob/Publications/JMMN07.pdf:

A lo mejor de nuestro conocimiento, el estado complejidad de retroalimentación mínimo arco situado en tales gráficos es abierta. Sin embargo, por un lema de Newman, Chen, y Lovász [1, el teorema 4], un algoritmo polinómico para [este problema] daría lugar a un algoritmo de 16/9 aproximación para la retroalimentación arco establecer problema mínimo general , mejorando sobre el algoritmo O (log n log log n) más conocido actualmente [2].

1. Newman, A .: El máximo problema subgráfico acíclico y gráficos de grado-3. En: Actas del 4 ° Taller internacional sobre Algoritmos de aproximación para Problemas de optimización combinatoria, APROX. LNCS (2001) 147-158

2. Even, G., Naor, J., Schieber, B., Sudán, M .: Aproximación de reproducciones mínimas de retorno y cortes múltiples en gráficos dirigidos. En: Actas de la 4ta Internacional Conferencia sobre la programación de enteros y Optimización combinatoria. LNCS (1995) 14-28