Primero, un poco de fondo para indicar por qué esto no es un problema difícil. El flujo a través de un río garantiza que sus segmentos, si bien digitalizados, siempre se puede estar orientada a formar un gráfico acíclico dirigido (DAG). A su vez, un gráfico puede ser linealmente ordenado si y sólo si es un DAG, utilizando una técnica conocida como un orden topológico. Topológico de clasificación es rápido: sus requisitos de tiempo y espacio son tanto O(|E| + |V|) (E = número de aristas, V = número de vértices), que es tan bueno como se pone. La creación de un lineal de pedidos sea fácil encontrar la mayor lecho de un arroyo.
Aquí, entonces, es un boceto de un algoritmo. La secuencia de la boca de mentiras a lo largo de su gran cama. Mover aguas arriba a lo largo de cada rama adjunta a la boca (puede haber más de uno, si la boca es una confluencia) y de forma recursiva encontrar la gran cama que conducen a esa rama. Seleccione la rama en la que la longitud total es el más grande: que su "backlink" a lo largo de la gran cama.
Para hacer esto más claro, os ofrecemos algunos (no probado) pseudocódigo. La entrada es un conjunto de segmentos de línea (o arcos) S (que comprende las digitalizado stream), cada uno con dos distintos extremos de inicio(S) y el final(S) y una positiva de longitud, la longitud de la(S); y de la boca del río p, que es un punto. El resultado es una secuencia de segmentos que une la boca con el más distante aguas arriba del punto.
Debemos trabajar con los "segmentos" (S,p). Estos se componen de uno de los segmentos S , junto con uno de sus dos extremos, p. Debemos encontrar todos los segmentos S que comparten un extremo con una sonda de punto q, marca aquellos segmentos con sus otros extremos, y devolver el conjunto:
Procedure Extract(q: point, A: set of segments): Set of marked segments.
Cuando no hay tal segmento se puede encontrar, Extraer, deben devolver el conjunto vacío. Como efecto secundario, el Extracto debe quitar todos los segmentos es el regreso de la serie A, con lo que la modificación de Un sí mismo.
No le voy a dar una implementación de Extracto de: SIG proporcionará la capacidad para seleccionar los segmentos S compartir un extremo con q. El marcado de ellos es simplemente una cuestión de la comparación de ambas inicio(S) y el final(S) con p y regresar a cualquiera de los dos extremos no coinciden.
Ahora estamos listos para resolver el problema.
Procedure LongestUpstreamReach(p: point, A: set of segments): (Array of segments, length)
A0 = A // Optional: preserves A
C = Extract(p, A0) // Removes found segments from the set A0!
L = 0; B = empty array
For each (S,q) in C: // Loop over the segments meeting point p
(B0, M) = LongestUpstreamReach(q, A0)
If (length(S) + M > L) then
B = append(S, B0)
L = length(S) + M
End if
End for
Return (B, L)
End LongestUpstreamReach
El procedimiento de "append(S, B0)" palos el segmento S al final de la matriz B0 y devuelve la nueva matriz.
(Si el flujo es realmente un árbol: no hay islas, lagos, trenzas, etc, entonces usted puede dispensar con el paso de copiar Una en A0.)
La pregunta original es contestada por la formación de la unión de los segmentos devuelto por LongestUpstreamReach.
Para ilustrarlo, consideremos la secuencia en el mapa original. Supongo que es digitalizar una colección de siete arcos. Arco de una va de la boca en el punto 0 (la parte superior del mapa, a la derecha en la figura de abajo, que es girado) aguas arriba de la primera confluencia en el punto 1. Es un largo de arco, digamos 8 unidades de longitud. Arco b ramas, a la izquierda (en el mapa) y es corta, aproximadamente de 2 unidades de longitud. Arco c ramas a la derecha y es de alrededor de 4 unidades de tiempo, etc. Dejar "b", "d" y "f" denotan el lado izquierdo de ramas que van de arriba a abajo en el mapa, y "a", "c", "e" y "g" de las otras ramas, y la numeración de los vértices de 0 a 7, se puede representar de manera abstracta el gráfico como el de la colección de arcos
A = {a=(0,1), b=(1,2), c=(1,3), d=(3,4), e=(3,5), f=(5,6), g=(5,7)}
Voy a suponer que tienen longitudes de 8, 2, 4, 1, 2, 2, 2 para un a través de g, respectivamente. La boca es el vértice 0.
![Figure]()
El primer ejemplo es la llamada a Extraer(5, {f, g}). Devuelve el conjunto de segmentos señalados {(f,6), (g,7)}. Tenga en cuenta que el vértice 5 se ubica en la confluencia de los arcos f y g (los dos arcos en la parte inferior del mapa) y que (f,6) y (g,7) marca de cada uno de estos arcos con sus aguas arriba de los puntos finales.
El siguiente ejemplo es la llamada a LongestUpstreamReach(0, A). La primera acción que se lleva es la llamada a Extraer(0, A). Esto devuelve un conjunto que contiene el marcado segmento (a,1) y se elimina el segmento de la una de la serie A0, que ahora es igual a {b,c,d,e,f,g}. Hay una iteración del bucle, donde (S,q) = (a,1). Durante esta iteración se realiza una llamada a LongestUpstreamReach(1, A0). De forma recursiva, se debe devolver la secuencia de (g,e,c) o (f,e, a,c): ambas son igualmente válidas. La longitud (M) devuelve es 4+2+2 = 8. (Tenga en cuenta que LongestUpstreamReach ¿ no modificar A0.) Al final del bucle, el segmento de una ha sido añadida a la corriente de la cama y la duración se ha aumentado a 8+8 = 16. Así, el primer valor de retorno consiste en la secuencia de (g,e,c,a) o (f,e,c,a), con una longitud de 16 en cualquier caso, para el segundo valor de retorno. Esto muestra cómo LongestUpstreamReach sólo se mueve arriba de la boca, seleccionando en cada confluencia de la rama con la distancia más larga todavía, y sigue la pista de los segmentos de recorrido a lo largo de su ruta.
Una implementación más eficaz es posible cuando hay muchas trenzas y las islas, pero la mayoría de los casos habrá un poco de esfuerzo en vano si LongestUpstreamReach se implementa exactamente como se muestra, porque en cada una confluencia que no se superponen entre las búsquedas en las diversas ramas: el tiempo de cómputo (y de la pila de profundidad) será directamente proporcional al número total de segmentos.
