No trabajo en teoría, pero mi trabajo requiere leer (y comprender) documentos de teoría de vez en cuando. Una vez que entiendo un (conjunto de) resultados, discuto estos resultados con las personas con las que trabajo, la mayoría de las cuales tampoco trabajan en teoría. Durante una de esas discusiones, surgió la siguiente pregunta:
¿Cuándo se dice que dos algoritmos dados son "similares"?
¿Qué quiero decir con "similar"? Digamos que se dice que dos algoritmos son similares si puede hacer cualquiera de las siguientes afirmaciones en un documento sin confundir / molestar a ningún revisor (se aceptan mejores definiciones):
Reclamación 1. "El algoritmo , que es similar al algoritmo B , también resuelve el problema X "
Reclamación 2. "Nuestro algoritmo es similar al Algoritmo "
Déjame hacerlo un poco más específico. Supongamos que estamos trabajando con algoritmos gráficos. Primero, algunas condiciones necesarias para que los dos algoritmos sean similares:
- Deben estar resolviendo el mismo problema.
- Deben tener la misma idea intuitiva de alto nivel.
Por ejemplo, hablar sobre el recorrido del gráfico, el recorrido primero en anchura y primero en profundidad satisfacen las dos condiciones anteriores; para los cálculos de la ruta más corta, la amplitud primero y el algoritmo de Dijkstra satisfacen las dos condiciones anteriores (en gráficos no ponderados, por supuesto); etc.
¿Son estas también condiciones suficientes? Más específicamente, suponga que dos algoritmos satisfacen las condiciones necesarias para ser similares. ¿Realmente los llamarías similares si
- Tienen un rendimiento asintótico diferente?
- para una clase especial de gráficos, un algoritmo requiere tiempo, mientras que el otro requiere O ( n 1 / 3 ) tiempo?
- tienen diferentes condiciones de terminación? (recuerde, están resolviendo el mismo problema)
- El paso de preprocesamiento es diferente en los dos algoritmos?
- La complejidad de la memoria es diferente en los dos algoritmos?
Editar: La pregunta es claramente muy dependiente del contexto y es subjetiva. Sin embargo, esperaba que las cinco condiciones anteriores permitan obtener algunas sugerencias. Me complace modificar aún más la pregunta y dar más detalles, si es necesario para obtener una respuesta. ¡Gracias!
fuente
Respuestas:
Es un problema difícil dar incluso una definición coherente de "Algoritmo A es similar al Algoritmo B". Por un lado, no creo que "deben estar resolviendo el mismo problema" es una condición necesaria. A menudo, cuando uno dice en un documento que "el algoritmo del Teorema 2 es similar al algoritmo B en el Teorema 1 ", el algoritmo AA 2 B 1 A realidad está resolviendo un problema diferente al de , pero tiene algunas modificaciones menores para manejar el nuevo problema. .B
Incluso tratar de determinar qué significa que dos algoritmos sean iguales es un problema interesante y difícil. Consulte el documento "¿Cuándo son dos algoritmos iguales?"http://research.microsoft.com/~gurevich/Opera/192.pdf
fuente
Más a menudo que no, significa "No quiero escribir el Algoritmo B en detalle, porque todos los detalles interesantes son casi idénticos a los del Algoritmo A, y no quiero superar el límite de 10 páginas, y de todos modos el plazo de presentación es en tres horas ".
fuente
Si quiere decir "similar" en el sentido coloquial, creo que la respuesta de JeffE captura lo que algunas personas quieren decir.
Sin embargo, en un sentido técnico, depende de lo que le interese. Si lo único que le importa es la complejidad asintótica del tiempo, la diferencia entre recursión e iteración puede no importar. Si lo único que le importa es la capacidad de cálculo, la diferencia entre una variable de contador y una pila de un símbolo no importa.
En términos más generales, preguntaría: ¿qué le importa (en términos intuitivos), cuáles son los objetos matemáticos que representan estas propiedades intuitivas, cómo puedo mapear desde algoritmos a estos objetos y cuál es la estructura de este espacio? También preguntaría si el espacio de los objetos goza de una estructura suficiente para admitir una noción de similitud. Este es el enfoque que tomaría desde una perspectiva semántica del lenguaje de programación. No estoy seguro de si este enfoque le resulta atractivo, dadas las culturas muy diferentes del pensamiento en informática.
fuente
En la línea de la respuesta de Jeff, dos algoritmos son similares si el autor de uno de ellos espera que el autor del otro esté revisando su artículo.
Pero bromeando, en la comunidad de la teoría, diría que el problema que el algoritmo A está resolviendo es bastante tangencial a si es "similar" al algoritmo B, que podría estar resolviendo un problema completamente diferente. A es similar a B si "funciona" debido a la misma idea teórica principal. Por ejemplo, ¿es la idea principal en ambos algoritmos que puede proyectar los datos en un espacio dimensional mucho más bajo, preservar las normas con el lema de Johnson-Lindenstrauss y luego hacer una búsqueda de fuerza bruta? Entonces su algoritmo es similar a otros algoritmos que hacen esto, sin importar el problema que esté resolviendo. Hay un pequeño número de técnicas algorítmicas de servicio pesado que se pueden usar para resolver una amplia variedad de problemas, y creo que estas técnicas forman los centroides de muchos conjuntos de algoritmos "similares".
fuente
Muy interesante pregunta, y muy buen papel Ryan!
Definitivamente estoy de acuerdo con la idea de que hacer una evaluación de la similitud general entre algoritmos es principalmente un juicio de valor subjetivo. Si bien desde un punto de vista técnico hay una serie de características que se observan de cerca para decidir la similitud de los algoritmos, al final, también es una cuestión de gusto personal. Intentaré proporcionar una descripción de la importancia de ambas caras de la misma moneda mientras me refiero a los puntos particulares de su pregunta:
Desde un punto de vista técnico:
Entonces, ¿qué hace que los algoritmos sean similares / diferentes? Desde mi punto de vista (y esto es puramente especulativo), la principal diferencia está en lo que te sugieren. Muchos, muchos (¡muchos!) Algoritmos difieren solo en unos pocos tecnicismos cuando sirven para el mismo propósito, de modo que el caso típico es diferente para diferentes rangos de la entrada. Sin embargo, la mayor de todas las diferencias es (a mi parecer) lo que te sugieren. Los algoritmos tienen diferentes capacidades y, por lo tanto, sus propias fortalezas y debilidades. Si dos algoritmos parecen ser iguales pero pueden extenderse de diferentes maneras para hacer frente a diferentes casos, entonces concluiría que son diferentes. Sin embargo, a menudo, dos algoritmos son muy parecidos, por lo que consideraría que son iguales ... hasta que llegue alguien haciendo una distinción clave y, de repente, ¡son completamente diferentes!
Lo siento, mi respuesta fue al final tanto tiempo ...
Salud,
fuente
Cualquier mención de similitud sin definir una métrica de similitud no está bien definida. Hay muchas formas en que dos algoritmos pueden ser similares:
Quicksort y Mergesort resuelven problemas muy similares, pero utilizan diferentes algoritmos para hacerlo. Tienen una complejidad algorítmica similar (aunque su rendimiento en el peor de los casos y el uso de memoria pueden variar). Quicksort y Mergesort son similares a Bubblesort, sin embargo, Bubblesort tiene métricas de rendimiento muy diferentes. Si ignora las estadísticas de complejidad Quicksort, Mergesort y Bubblesort están en la misma clase de equivalencia. Sin embargo, si le importa la complejidad algorítmica, Quicksort y Mergesort son mucho más similares entre sí que con Bubblesort.
La programación dinámica de Smith-Waterman y la comparación de secuencias HMM intentan resolver el problema de alinear dos secuencias. Sin embargo, toman diferentes entradas. Smith-Waterman toma dos secuencias como entrada, y las comparaciones de secuencia HMM toman un HMM y una secuencia como entrada. Ambas alineaciones de secuencia de salida. En términos de ideas motivadoras, ambas son similares a la distancia de edición de Levenshtein , pero solo a un nivel muy alto.
Aquí hay algunos criterios por los cuales dos algoritmos podrían llamarse similares:
La decisión crítica sobre el significado de similitud permanece. A veces te importa la complejidad de un algoritmo, a veces no. Como la definición de similitud depende del contexto de la discusión, el término "algoritmo similar" no está bien definido.
fuente