algorithm complexity-theory dynamic-programming backtracking

algorithm - algoritmo para encontrar secuencias no superpuestas más largas



backtracking pdf (9)

Estoy tratando de encontrar la mejor manera de resolver el siguiente problema. Por mejor manera quiero decir menos complejo.

Como entrada, una lista de tuplas (inicio, longitud) como:

[(0,5),(0,1),(1,9),(5,5),(5,7),(10,1)]

Cada elemento representa una secuencia por su inicio y longitud , por ejemplo (5,7) es equivalente a la secuencia (5,6,7,8,9,10,11) - una lista de 7 elementos que comienzan con 5. Se puede Supongamos que las tuplas están ordenadas por el elemento de start .

La salida debe devolver una combinación no superpuesta de tuplas que representan las secuencias continuas más largas. Esto significa que, una solución es un subconjunto de rangos sin superposiciones y sin huecos y es el más largo posible, aunque podría haber más de uno.

Por ejemplo, para la entrada dada, la solución es:

[(0,5),(5,7)] equivalente a (0,1,2,3,4,5,6,7,8,9,10,11)

¿Está dando marcha atrás el mejor enfoque para resolver este problema?

Me interesan los diferentes enfoques que las personas puedan sugerir.

Además, si alguien conoce una referencia formal de este problema u otra que sea similar, me gustaría obtener referencias.

Por cierto, esto no es tarea.

Editar

Solo para evitar algunos errores este es otro ejemplo de comportamiento esperado.

para una entrada como [(0,1),(1,7),(3,20),(8,5)] la respuesta correcta es [(3,20)] equivalente a (3,4,5 ,. ., 22) con longitud 20. Algunas de las respuestas recibidas darían [(0,1),(1,7),(8,5)] equivalente a (0,1,2, ..., 11,12 ) como respuesta correcta. Pero esta última respuesta no es correcta porque es más corta que [(3,20)] .

Algoritmo revisado:

create a hashtable of start->list of tuples that start there put all tuples in a queue of tupleSets set the longestTupleSet to the first tuple while the queue is not empty take tupleSet from the queue if any tuples start where the tupleSet ends foreach tuple that starts where the tupleSet ends enqueue new tupleSet of tupleSet + tuple continue if tupleSet is longer than longestTupleSet replace longestTupleSet with tupleSet return longestTupleSet

c # implementación

public static IList<Pair<int, int>> FindLongestNonOverlappingRangeSet(IList<Pair<int, int>> input) { var rangeStarts = input.ToLookup(x => x.First, x => x); var adjacentTuples = new Queue<List<Pair<int, int>>>( input.Select(x => new List<Pair<int, int>> { x })); var longest = new List<Pair<int, int>> { input[0] }; int longestLength = input[0].Second - input[0].First; while (adjacentTuples.Count > 0) { var tupleSet = adjacentTuples.Dequeue(); var last = tupleSet.Last(); int end = last.First + last.Second; var sameStart = rangeStarts[end]; if (sameStart.Any()) { foreach (var nextTuple in sameStart) { adjacentTuples.Enqueue(tupleSet.Concat(new[] { nextTuple }).ToList()); } continue; } int length = end - tupleSet.First().First; if (length > longestLength) { longestLength = length; longest = tupleSet; } } return longest; }

pruebas:

[Test] public void Given_the_first_problem_sample() { var input = new[] { new Pair<int, int>(0, 5), new Pair<int, int>(0, 1), new Pair<int, int>(1, 9), new Pair<int, int>(5, 5), new Pair<int, int>(5, 7), new Pair<int, int>(10, 1) }; var result = FindLongestNonOverlappingRangeSet(input); result.Count.ShouldBeEqualTo(2); result.First().ShouldBeSameInstanceAs(input[0]); result.Last().ShouldBeSameInstanceAs(input[4]); } [Test] public void Given_the_second_problem_sample() { var input = new[] { new Pair<int, int>(0, 1), new Pair<int, int>(1, 7), new Pair<int, int>(3, 20), new Pair<int, int>(8, 5) }; var result = FindLongestNonOverlappingRangeSet(input); result.Count.ShouldBeEqualTo(1); result.First().ShouldBeSameInstanceAs(input[2]); }

Eliminé la solución anterior porque no fue probada.

El problema es encontrar la ruta más larga en un "gráfico acíclico dirigido ponderado", se puede resolver en tiempo lineal:

http://en.wikipedia.org/wiki/Lestest_path_problem#Weighted_directed_acyclic_graphs

Coloque un conjunto de {posiciones iniciales} unión {(posición inicial + posición final)} como vértices. Para tu ejemplo sería {0, 1, 5, 10, 11, 12}

para los vértices v0, v1 si hay un valor final w que hace que v0 + w = ​​v1, a continuación, agregue un borde dirigido que conecte v0 a v1 y ponga w como su peso.

Ahora sigue el pseudocódigo en la página de wikipedia. Dado que el número de vértices es el valor máximo de 2xn (n es el número de tuplas), el problema aún puede resolverse en tiempo lineal.

Esta es una simple operación de reducción. Dado un par de tuplas consecutivas, pueden o no pueden combinarse. Así que define la función de combinación de pares:

def combo(first,second): if first[0]+first[1] == second[0]: return [(first[0],first[1]+second[1])] else: return [first,second]

Esto solo devuelve una lista de un elemento que combina los dos argumentos, o los dos elementos originales.

Luego defina una función para iterar sobre la primera lista y combine pares:

def collapse(tupleList): first = tupleList.pop(0) newList = [] for item in tupleList: collapsed = combo(first,item) if len(collapsed)==2: newList.append(collapsed[0]) first = collapsed.pop() newList.append(first) return newList

Esto mantiene un primer elemento para comparar con el elemento actual en la lista (comenzando en el segundo elemento), y cuando no puede combinarlos, coloca el primero en una nueva lista y reemplaza first al segundo de los dos.

Luego simplemente llama a collapse con la lista de tuplas:

>>> collapse( [(5, 7), (12, 3), (0, 5), (0, 7), (7, 2), (9, 3)] ) [(5, 10), (0, 5), (0, 12)]

[Editar] Finalmente, itera sobre el resultado para obtener la secuencia más larga.

def longest(seqs): collapsed = collapse(seqs) return max(collapsed, key=lambda x: x[1])

[/Editar]

Complejidad O (N). Para las marcas de bonificación, hágalo al revés para que el pop(0) inicial pop(0) convierta en pop() y no tenga que volver a indexar la matriz, o mover el iterador en su lugar. Para las mejores marcas, hágalo funcionar como una operación de reduce por pares para una calidad de subprocesos múltiples.

Esto suena como un problema perfecto de "programación dinámica" ...

El programa más simple sería hacerlo con fuerza bruta (por ejemplo, recursiva), pero esto tiene una complejidad exponencial.

Con la programación dinámica puede configurar una matriz a de longitud n, donde n es el máximo de todos los valores (inicio + longitud) de su problema, donde [i] denota la secuencia más larga no superpuesta hasta a [i]. Luego puede pasar por todas las tuplas, actualizando a. La complejidad de este algoritmo sería O (n * k), donde k es el número de valores de entrada.

Iterar sobre la lista de tuplas usando el orden dado (por elemento de inicio), mientras usa un hashmap para realizar un seguimiento de la longitud de la secuencia continua más larga que termina en un determinado índice.

pseudocódigo, omitiendo detalles como elementos que no se encontraron en un hashmap (suponga que se devuelve 0 si no se encuentra):

int bestEnd = 0; hashmap<int,int> seq // seq[key] = length of the longest sequence ending on key-1, or 0 if not found foreach (tuple in orderedTuples) { int seqLength = seq[tuple.start] + tuple.length int tupleEnd = tuple.start+tuple.length; seq[tupleEnd] = max(seq[tupleEnd], seqLength) if (seqLength > seq[bestEnd]) bestEnd = tupleEnd } return new tuple(bestEnd-seq[bestEnd], seq[bestEnd])

Este es un algoritmo O (N).

Si necesita las tuplas reales que componen esta secuencia, también deberá mantener una lista vinculada de tuplas con el índice de finalización, actualizándolas siempre que se actualice la longitud máxima para este punto final.

ACTUALIZACIÓN: mi conocimiento de python es bastante limitado, pero según el código de python que pegó, creé este código que devuelve la secuencia real en lugar de solo la longitud:

def get_longest(arr): bestEnd = 0; seqLengths = dict() #seqLengths[key] = length of the longest sequence ending on key-1, or 0 if not found seqTuples = dict() #seqTuples[key] = the last tuple used in this longest sequence for t in arr: seqLength = seqLengths.get(t[0],0) + t[1] tupleEnd = t[0] + t[1] if (seqLength > seqLengths.get(tupleEnd,0)): seqLengths[tupleEnd] = seqLength seqTuples[tupleEnd] = t if seqLength > seqLengths.get(bestEnd,0): bestEnd = tupleEnd longestSeq = [] while (bestEnd in seqTuples): longestSeq.append(seqTuples[bestEnd]) bestEnd -= seqTuples[bestEnd][1] longestSeq.reverse() return longestSeq if __name__ == "__main__": a = [(0,3),(1,4),(1,1),(1,8),(5,2),(5,5),(5,6),(10,2)] print(get_longest(a))

Solo pensando en el algoritmo en términos básicos, ¿funcionaría esto?

(disculpas por la horrible sintaxis, pero estoy tratando de permanecer independiente del lenguaje aquí)

Primero, la forma más simple: encuentre el par contiguo más largo.

Recorra cada miembro y compárelo con cualquier otro miembro con una posición inicial más alta. Si la posición inicial del segundo miembro es igual a la suma de la posición inicial y la longitud del primer miembro, son contiguos. Si es así, forme un nuevo miembro en un nuevo conjunto con la posición inicial más baja y la longitud combinada para representar esto.

Luego, tome cada uno de estos pares y compárelos con todos los miembros individuales con una posición inicial más alta y repítalos, formando un nuevo conjunto de triples contiguos (si existen).

Continúa este patrón hasta que no tengas nuevos conjuntos.

La parte difícil entonces es que tienes que comparar la longitud de cada miembro de cada uno de tus conjuntos para encontrar la cadena más larga real.

Estoy bastante seguro de que esto no es tan eficiente como otros métodos, pero creo que este es un enfoque viable para forzar a esta solución.

Apreciaría comentarios sobre esto y cualquier error que pueda haber pasado por alto.

Editado para reemplazar el pseudocódigo con el código real de Python

Editado de nuevo para cambiar el código; El algoritmo original estaba en la solución, ¡pero no entendí cuál era el segundo valor en los pares! Afortunadamente, el algoritmo básico es el mismo, y pude cambiarlo.

Aquí hay una idea que resuelve el problema en O (N log N) y no utiliza un mapa hash (por lo que no hay tiempos ocultos). Para la memoria vamos a utilizar N * 2 "cosas".

Vamos a agregar dos valores más a cada tupla: (BackCount, BackLink). En la combinación exitosa, BackLink enlazará de derecha a izquierda desde la tupla más a la derecha hasta la tupla más a la izquierda. BackCount será el valor acumulado para el BackLink dado.

Aquí hay un código de python:

def FindTuplesStartingWith(tuples, frm): # The Log(N) algorithm is left as an excersise for the user ret=[] for i in range(len(tuples)): if (tuples[i][0]==frm): ret.append(i) return ret def FindLongestSequence(tuples): # Prepare (BackCount, BackLink) array bb=[] # (BackCount, BackLink) for OneTuple in tuples: bb.append((-1,-1)) # Prepare LongestSequenceLen=-1 LongestSequenceTail=-1 # Algorithm for i in range(len(tuples)): if (bb[i][0] == -1): bb[i] = (0, bb[i][1]) # Is this single pair the longest possible pair all by itself? if (tuples[i][1] + bb[i][0]) > LongestSequenceLen: LongestSequenceLen = tuples[i][1] + bb[i][0] LongestSequenceTail = i # Find next segment for j in FindTuplesStartingWith(tuples, tuples[i][0] + tuples[i][1]): if ((bb[j][0] == -1) or (bb[j][0] < (bb[i][0] + tuples[i][1]))): # can be linked bb[j] = (bb[i][0] + tuples[i][1], i) if ((bb[j][0] + tuples[j][1]) > LongestSequenceLen): LongestSequenceLen = bb[j][0] + tuples[j][1] LongestSequenceTail=j # Done! I''ll now build up the solution ret=[] while (LongestSequenceTail > -1): ret.insert(0, tuples[LongestSequenceTail]) LongestSequenceTail = bb[LongestSequenceTail][1] return ret # Call the algoritm print FindLongestSequence([(0,5), (0,1), (1,9), (5,5), (5,7), (10,1)]) >>>>>> [(0, 5), (5, 7)] print FindLongestSequence([(0,1), (1,7), (3,20), (8,5)]) >>>>>> [(3, 20)]

La clave para todo el algoritmo es cuando el comentario "ESTA ES LA CLAVE" está en el código. Sabemos que nuestro StartTuple actual puede estar vinculado a EndTuple. Si existe una secuencia más larga que termina en EndTuple.To, se encontró en el momento en que llegamos a este punto, porque tenía que comenzar en un StartTuple.From más pequeño, ¡y la matriz está ordenada en "De"!

  • Cree una matriz ordenada de todos los puntos de inicio y finalización e inicialícelos en uno.
  • Para cada elemento en su tupla, compare el punto final (inicio y final) con los elementos ordenados en su matriz, si algún punto se encuentra entre ellos (por ejemplo, el punto en la matriz es 5 y usted tiene inicio 2 con longitud 4) cambie el valor a cero.
  • Después de terminar el ciclo, comience a moverse a través de la matriz ordenada y cree una tira cuando vea 1 y mientras vea 1, agregue a la tira existente, con cualquier cero, cierre la tira y etc.
  • Al final verifica la longitud de las tiras.

Creo que la complejidad está alrededor de O (4-5 * N)

(VER ACTUALIZACIÓN)

siendo N el número de elementos en la tupla.

ACTUALIZAR

Como se dio cuenta, la complejidad no es precisa pero definitivamente muy pequeña, ya que es una función del número de estiramientos de línea (elementos de la tupla).

Entonces, si N es el número de tramos de línea, la clasificación es O (2N * log2N). La comparación es O (2N). Encontrar tramos de línea también es O (2N). Así que en general O (2N (log2N + 2)) .