Viajero vendedor y mapa/Reducir: Abandonar canal

Question

Esta es una pregunta académica más que práctica. En el Problema del Viajero Vendedor, o cualquier otro que implique encontrar una optimización mínima ... si uno estuviera usando un enfoque de mapa/reducir, parece que sería útil contar con algunos medios para que el resultado mínimo actual sea transmitido a todos los nodos computacionales de alguna manera que les permite abandonar los cálculos que exceden eso.

En otras palabras, si correlacionamos el problema, nos gustaría que cada nodo sepa cuándo renunciar a un resultado parcial dado antes de que se complete, pero cuando ya se haya excedido alguna otra solución.

Un enfoque que viene inmediatamente a la mente sería si el reductor tenía un medio para proporcionar retroalimentación al asignador. Considere si teníamos 100 nodos y millones de caminos alimentados por el mapeador. Si el reductor proporciona el mejor resultado al asignador, ese valor podría incluirse como argumento junto con cada nueva ruta (subconjunto de problemas). En este enfoque, la granularidad es bastante difícil ... los 100 nodos seguirán reduciéndose en su partición del problema hasta su finalización y solo obtendrán el nuevo mínimo con su próxima solicitud del asignador. (Para un pequeño número de nodos y una gran cantidad de particiones problema/subconjuntos para trabajar en esta granularidad sería inconsecuente, también es probable que uno podría aplicar heurística a la secuencia en la que las posibles rutas o subconjuntos de problemas se alimentan a los nodos para obtener una convergencia rápida hacia el óptimo y así minimizar la cantidad de computación "desperdiciada" realizada por los nodos).

Otro enfoque que se le viene a la mente sería que los nodos se suscriban activamente a algún tipo de canal, o multidifusión o incluso difusión desde la que puedan obtener nuevos mínimos de su bucle computacional. En ese caso, podrían abandonar inmediatamente un mal cálculo cuando se les notifique una mejor solución (por uno de sus pares).

Por lo tanto, mis preguntas son:

• Es este concepto cubierta por cualquiera de los términos de arte en relación con el mapa existente/reducir discusiones
• hacer cualquiera del mapa actual/reducen los marcos proporcionan características para apoyar esta tipo de respuesta dinámica?
• ¿Hay alguna falla con esta idea ... alguna razón por la que es estúpido?

Answer 1

ese es un tema genial, que no tiene tanta literatura, que se hizo antes. Así que esto es más o menos un puesto de intercambio de ideas, en lugar de una respuesta a todos sus problemas;)

Así que cada TSP se puede expresar como un gráfico, que se ve posiblemente como ésta: (tomado del alemán Wikipedia)

Ahora puede ejecutar un algoritmo de gráfico en él. MapReduce puede usarse para el procesamiento de gráficos bastante bien, aunque tiene mucha sobrecarga.
Necesita un paradigma que se denomina "Mensaje que pasa". Fue descrito en este documento aquí: Paper.
Y publiqué sobre esto en términos de exploración de gráficos, dice bastante simple cómo funciona. My Blogpost

Esta es la forma en que puede decirle al asignador cuál es el resultado mínimo actual (tal vez solo para el vértice mismo).

Con todo el conocimiento en el fondo de la mente, debería ser bastante estándar pensar en un algoritmo branch and bound (que usted describió) para llegar a la meta. Como tener un vértice de inicio aleatorio y una ramificación en cada vértice adyacente. Esto hace que se envíe un mensaje a cada uno de estos adyacentes con el costo que se puede alcanzar desde el vértice de inicio (Paso del mapa). El vértice en sí mismo solo actualiza su costo si es menor que el costo actualmente almacenado (Reducir paso). Inicialmente, esto debe establecerse en infinito.
Estás haciendo esto una y otra vez hasta que hayas alcanzado el vértice de inicio nuevamente (obviamente después de haber visitado cada uno). Entonces, de alguna manera debe hacer un seguimiento de la mejor forma de alcanzar un vértice, esto también se puede almacenar en el vértice mismo. Y de vez en cuando tiene que enlazar esta ramificación y cortar ramas que son demasiado costosas, esto se puede hacer en el paso de reducir después de leer los mensajes. Básicamente esto es solo una combinación de algoritmos de gráficos en MapReduce y una especie de rutas más cortas.
Tenga en cuenta que esto no cederá a la forma óptima entre los nodos, todavía es una cosa heurística. Y estás paralizando el problema de NP-Hard.

PERO un poco de auto-publicidad de nuevo, tal vez ya lo haya leído en la publicación de blog que he vinculado, existe una abstracción de MapReduce, que tiene mucho menos sobrecarga en este tipo de procesamiento de gráficos. Se llama BSP (Bulk synchonous parallel). Es más libre en la comunicación y su modelo de computación. Así que estoy seguro de que esto se puede implementar mucho mejor con BSP que con MapReduce. Puede darse cuenta de estos canales de los que ha hablado mejor con él.

Actualmente estoy involucrado en un proyecto Summer of Code que se dirige a estos problemas SSSP con BSP. Quizás quieras visit if you're interested. Esto podría ser una solución parcial, también se describe muy bien en mi blog. SSSP's in my blog

Estoy emocionado de escuchar algunos comentarios;)

Answer 2

Parece que Storm implementa lo que estaba pensando. Básicamente es una topología computacional (piense en cómo cada nodo de cálculo podría ser resultados de enrutamiento basados ​​en una función de clave/hash para los reductores específicos).

Esto no es exactamente lo que describí, pero podría ser útil si tuviera una latencia suficientemente baja para propagar el límite actual (es decir, información óptima local) que cada nodo de la topología podría actualizar/recibir para saber cuál resultados para descartar.