viernes, 28 de junio de 2019

LISTAS RELACIONADAS CON LAS MATEMÁTICAS - ALGORITMOS


TrustRank es una técnica de análisis de vínculos descrita en el artículo Combatiendo el spam web con TrustRank por los investigadores Zoltan Gyongyi y Hector Garcia-Molina de la Universidad de Stanford y Jan Pedersen de Yahoo! La técnica se utiliza para la separación semiautomática de páginas web útiles de spam .
Muchas páginas web de spam se crean solo con la intención de engañar a los motores de búsqueda . Estas páginas, creadas principalmente por razones comerciales, utilizan diversas técnicas para lograr clasificaciones más altas de lo merecido en las páginas de resultados de los motores de búsqueda . Si bien los expertos humanos pueden identificar fácilmente el correo no deseado, una revisión manual de Internet no es práctica.
Un método popular para mejorar las clasificaciones es aumentar la importancia percibida de un documento a través de complejos esquemas de vinculación. El PageRank de Google y otros algoritmos de clasificación de búsqueda han sido sometidos a tal manipulación.
TrustRank busca combatir el spam filtrando la web según la confiabilidad. El método requiere seleccionar un pequeño conjunto de páginas semilla para que las evalúe un experto. Una vez que las páginas semilla acreditadas se identifican manualmente, un rastreo que se extiende hacia afuera desde el conjunto semilla busca páginas confiables y confiables de manera similar. La confiabilidad de TrustRank disminuye con el aumento de la distancia entre los documentos y el conjunto de semillas.
La lógica también funciona de manera opuesta, lo que se denomina Rango Anti-Trust. Cuanto más cerca esté un sitio de los recursos de spam, más probable será que también sea spam. [1]
Los investigadores que propusieron la metodología TrustRank han continuado refinando su trabajo mediante la evaluación de temas relacionados, como la medición de la masa de spam .








El algoritmo de Dinic o el algoritmo de Dinitz es un algoritmo fuertemente polinomial para calcular el flujo máximo en una red de flujo , concebido en 1970 por el científico informático israelí (anteriormente soviético) Yefim (Chaim) A. Dinitz. [1] El algoritmo se ejecuta eny es similar al algoritmo de Edmonds-Karp , que se ejecuta enTiempo, en el sentido de que utiliza rutas de aumento más cortas. La introducción de los conceptos del gráfico de nivel y el flujo de bloqueo permiten que el algoritmo de Dinic alcance su rendimiento.

Historia editar ]

Yefim Dinitz inventó este algoritmo en respuesta a un ejercicio previo a la clase en la clase de algoritmos de Adelson-Velsky . En ese momento no estaba al tanto de los hechos básicos relacionados con el algoritmo Ford-Fulkerson . [2]
Dinitz menciona haber inventado su algoritmo en enero de 1969, que se publicó en 1970 en la revista Doklady Akademii Nauk SSSR . En 1974, Shimon Even y (su entonces estudiante de doctorado) Alon Itai en el Technionen Haifa se mostraron muy curiosos e intrigados por el algoritmo de Dinitz, así como por la idea relacionada de bloqueo del flujo de Alexander V. Karzanov . Sin embargo, fue difícil para ellos descifrar estos dos documentos, cada uno limitado a cuatro páginas para cumplir con las restricciones de la revista Doklady Akademii Nauk SSSRIncluso no se rindió, y después de tres días de esfuerzo, logró comprender ambos documentos, excepto el problema de mantenimiento de la red en capas. Durante los siguientes dos años, Even dio conferencias sobre el "algoritmo de Dinic", pronunciando mal el nombre del autor y lo popularizó. Even e Itai también contribuyeron a este algoritmo al combinar BFS y DFS , que es la versión actual del algoritmo. [3]
Durante aproximadamente 10 años después de que se inventó el algoritmo Ford-Fulkerson, no se sabía si se podía hacer que terminara en tiempo polinomial en el caso general de capacidades de borde irracional. Esto causó la falta de cualquier algoritmo de tiempo polinómico conocido para resolver el problema de flujo máximo en casos genéricos. El algoritmo de Dinitz y el algoritmo de Edmonds-Karp (publicado en 1972) mostraron de forma independiente que, en el algoritmo de Ford-Fulkerson, si cada ruta de aumento es la más corta, entonces la longitud de las rutas de aumento no disminuye y el algoritmo siempre termina.

Definición editar ]

Dejar  ser una red con  y  La capacidad y el flujo del borde. respectivamente.
La capacidad residual es un mapeo. definido como,
  1. Si ,
  2.  de otra manera.
El gráfico residual es un gráfico no ponderado., dónde
.
Un camino de aumento es un ruta en el grafo residual .
Definir  para ser la longitud del camino más corto de  a  en Luego el gráfico de nivel de es la gráfica , dónde
.
Un flujo de bloqueo es un fluir  tal que la gráfica  con  no contiene camino. [4] [5]

Algoritmo editar ]

Algoritmo de Dinic
Entrada : una red.
Salida : Un fluir  de máximo valor.
  1. Conjunto  para cada .
  2. Construir  desde  de Siparada y salida .
  3. Encuentra un flujo de bloqueo  en .
  4. Añadir flujo de aumento  por  y volver al paso 2.

Análisis editar ]

Se puede mostrar que el número de capas en cada flujo de bloqueo aumenta en al menos 1 cada vez y, por lo tanto, hay como máximo Bloqueo de flujos en el algoritmo. Para cada uno de ellos:
  • la gráfica de nivel Se puede construir por primera búsqueda de amplitud en hora
  • Un flujo de bloqueo en el gráfico de nivel.  se puede encontrar en  hora
con el tiempo total de ejecución para cada capa. Como consecuencia, el tiempo de ejecución del algoritmo de Dinic es.
Usando una estructura de datos llamada árboles dinámicos , el tiempo de ejecución para encontrar un flujo de bloqueo en cada fase se puede reducir a y por lo tanto el tiempo de ejecución del algoritmo de Dinic se puede mejorar para .

Casos especiales editar ]

En redes con capacidades unitarias, se mantiene un límite de tiempo mucho más fuerte. Cada flujo de bloqueo se puede encontrar en tiempo, y se puede demostrar que el número de fases no excede  y Así el algoritmo se ejecuta enhora. [6]
En las redes que surgen del problema de coincidencia bipartita , el número de fases está limitado por, lo que lleva a la limitados en el tiempo. El algoritmo resultante también se conoce como algoritmo Hopcroft-Karp . De manera más general, este límite se mantiene para cualquier red unitaria : una red en la que cada vértice, a excepción de la fuente y el sumidero, tiene un solo borde de entrada de capacidad uno o un solo borde de salida de capacidad uno, y todas las demás capacidades son enteros arbitrarios . [5]

Ejemplo editar ]

Lo siguiente es una simulación del algoritmo de Dinic. En el gráfico de niveles., los vértices con etiquetas en rojo son los valores. Los caminos en azul forman un flujo de bloqueo.
1.Algoritmo Dinic G1.svgAlgoritmo Dinic Gf1.svgAlgoritmo Dinic GL1.svg
El flujo de bloqueo consiste en
  1.  con 4 unidades de flujo,
  2.  con 6 unidades de flujo, y
  3.  Con 4 unidades de flujo.
Por lo tanto, el flujo de bloqueo es de 14 unidades y el valor de flujo. es 14. Tenga en cuenta que cada ruta de aumento en el flujo de bloqueo tiene 3 bordes.
2.Algoritmo Dinic G2.svgAlgoritmo Dinic Gf2.svgAlgoritmo Dinic GL2.svg
El flujo de bloqueo consiste en
  1.  Con 5 unidades de flujo.
Por lo tanto, el flujo de bloqueo es de 5 unidades y el valor del flujo.  es 14 + 5 = 19. Tenga en cuenta que cada ruta de aumento tiene 4 bordes.
3.Algoritmo Dinic G3.svgAlgoritmo Dinic Gf3.svgAlgoritmo Dinic GL3.svg
Ya que  no puede ser alcanzado en , el algoritmo termina y devuelve un flujo con un valor máximo de 19. Tenga en cuenta que en cada flujo de bloqueo, el número de bordes en la ruta de aumento aumenta en al menos 1.










algoritmo Edmonds-Karp es una implementación del método Ford-Fulkerson para calcular el flujo máximo en una red de flujo enhora. El algoritmo fue publicado por primera vez por Yefim Dinitz en 1970 [1] [2] y publicado independientemente por Jack Edmonds y Richard Karp en 1972. [3] El algoritmo de Dinic incluye técnicas adicionales que reducen el tiempo de ejecución a.

Algoritmo editar ]

El algoritmo es idéntico al algoritmo Ford-Fulkerson , excepto que se define el orden de búsqueda al encontrar la ruta de aumento . La ruta encontrada debe ser una ruta más corta que tenga capacidad disponible. Esto se puede encontrar mediante una búsqueda en primer lugar , donde aplicamos un peso de 1 a cada borde. El tiempo de ejecución dese encuentra al mostrar que cada camino de aumento se puede encontrar en  tiempo, que cada vez al menos uno de los  los bordes se vuelven saturados (un borde que tiene el máximo flujo posible), que la distancia desde el borde saturado a la fuente a lo largo del camino de aumento debe ser más larga que la última vez que se saturó, y que la longitud es como máximo Otra propiedad de este algoritmo es que la longitud del camino de aumento más corto aumenta monótonamente. Hay una prueba accesible en Introducción a los Algoritmos . [4]

Pseudocódigo editar ]

entrada del algoritmo EdmondsKarp
     :
        gráfico    (gráfico [v] debe ser la lista de bordes que salen del vértice v en el 
                gráfico original y sus correspondientes bordes inversos construidos 
                que se utilizan para el flujo de retroceso. 
                Cada borde debe tener una capacidad, flujo, fuente y sumidero como parámetros , 
                así como un puntero al borde inverso.) 
        s        (vértice de fuente) 
        t        (vértice de sumidero) de 
    salida :
        flujo     (Valor del flujo máximo)
    
    flujo: = 0    (Inicializar flujo a cero) 
    repita 
        (Ejecute bfs para encontrar la ruta st más corta. 
        Usamos 'pred' para almacenar el borde tomado para llegar a cada vértice, 
        para poder recuperar la ruta más adelante) 
        q: = cola ()
        q.push (s)
        pred: = array (graph.length)
         mientras  no está vacío (q)
            cur: = q.pull ()
            para el borde e en el gráfico [cur]
                  if pred [et] = null  and et ≠ s y e.cap> e.flow
                    pred [et]: = e
                    q.push (et)
    
        si  no (pred [t] = nulo)         
             (Encontramos una ruta de aumento. 
            Vea cuánto flujo podemos enviar)  
            df: = 
            para (e: = pred [t]; e ≠ nulo; e: = pred [es] )
                df: = min (df, e.cap - e.flow)
             (Y actualizar los bordes en esa cantidad) 
            para (e: = pred [t]; e ≠ null; e: = pred [es])
                e.flow: = e.flow + df
                e.rev.flow: = e.rev.flow - df
            flujo: = flujo + df
    
    hasta que pred [t] = nulo   (es decir, hasta que no se haya encontrado una ruta de aumento) 
    devuelva el flujo

Ejemplo editar ]

Dada una red de siete nodos, fuente A, sumidero G y capacidades como se muestra a continuación:
Ejemplo de flujo de Edmonds-Karp 0.svg
En los pares  escrito en los bordes,  es el flujo de corriente, y es la capacidad La capacidad residual de a  es , la capacidad total, menos el flujo que ya se utiliza. Si el flujo neto de a Es negativo, contribuye a la capacidad residual.
CapacidadCaminoRed resultante
Ejemplo de flujo de Edmonds-Karp 1.svg
Edmonds-Karp flow ejemplo 2.svg
Ejemplo de flujo de Edmonds-Karp 3.svg
Ejemplo de flujo de Edmonds-Karp 4.svg
Observe cómo la longitud del camino de aumento encontrado por el algoritmo (en rojo) nunca disminuye. Los caminos encontrados son los más cortos posibles. El flujo encontrado es igual a la capacidad a través del corte mínimo en el gráfico que separa la fuente y el sumidero. Solo hay un corte mínimo en este gráfico, que divide los nodos en los conjuntos y , con la capacidad

No hay comentarios:

Publicar un comentario