Subsecuencia más larga creciente parte II

Question

Utilizando la respuesta proporcionada aquí Ahora estoy tratando de encontrar el subconjunto creciente más largo en dos secuencias diferentes de números definidos por ubicación1 y ubicación2.

Para cada lugar hay 16 lecturas. Cada lectura tiene su propia posición. He ordenado ambas listas por la columna Lectura.

Utilizando un gráfico de dispersión para cada lugar, estoy tratando de encontrar el subconjunto creciente más largo

Lugar 1

Lugar 2

Basándonos en los dos gráficos, para la ubicación 1 la longitud del subconjunto creciente más largo es 7 (7 posiciones) y para la ubicación 2 es 5.

He resaltado la subsecuencia más larga que he encontrado utilizando el gráfico en azul y la subsecuencia de Itzik en rojo.

El problema es que el libro del que tomé estas dos listas Consulta TSQL (Itzik Ben-Gan) indica que el subconjunto creciente más largo para Location2 tiene 6 puntos y, utilizando el gráfico, sólo encontré 5 puntos que componen el subconjunto más largo.

Este es el subconjunto más largo según el libro

Como puede ver, la columna readingNum está desordenada. Mi suposición era que para encontrar el subconjunto creciente más largo, la posición en el array tenía que aumentar así como el valor de esa posición.

Preguntas:

¿Cuál es la subsecuencia creciente más larga para ambos lugares?

¿Cuál es la fórmula, el algoritmo o el método utilizado?

Gracias

Answer 1

En primer lugar, para dar el crédito adecuado, el Capítulo 5: Algoritmos y Complejidad, fue escrito por Steve Kass. En cuanto a su pregunta sobre la longitud de la subsecuencia creciente más larga; tenga en cuenta que el algoritmo descrito en el libro no intenta encontrar la subsecuencia creciente más larga, sino su longitud. No se confunda por los valores específicos que la solución almacena en la variable de la tabla. Por ejemplo, aquí hay una subsecuencia creciente de 6 puntos para la posición 2:

1 - 3.894 3 - 3.939 5 - 3.940 10 - 4.035 12 - 4.086 13 - 4.093

De nuevo, los valores almacenados en la variable de la tabla son diferentes, pero su recuento es 6, la longitud de la subsecuencia creciente más larga.

Salud, Itzik

Answer 2

Itzik acaba de enviarme un correo electrónico para informarme de que has hecho esta pregunta. Como él señala, el algoritmo de T-SQL Querying no revela la subsecuencia en sí. Sólo revela su longitud. Los valores intermedios que aparecen durante el cálculo no ayudan necesariamente a encontrar la secuencia real. (La complejidad algorítmica para encontrar la subsecuencia más larga real es mayor que para encontrar la longitud).

Si quiere aprender un poco más sobre el algoritmo que lo que está en T-SQL Querying, vea mi artículo de 2002 de SQL Server Magazine, disponible en línea aquí .

El álgebra relacional no es fundamental para este interesante problema matemático (encontrar la longitud de la subsecuencia creciente más larga), pero resultó ser útil en el mundo real, y una solución SQL resultó ser valiosa.