Un dispositivo contiene una matriz de ubicaciones, algunas de las cuales contienen valores que queremos leer periódicamente.Algoritmo para encontrar grupos óptimos
Nuestra lista de ubicaciones que queremos leer periódicamente también especifica con qué frecuencia queremos leerlas. Se permite leer un valor con mayor frecuencia que la especificada, pero no con menos frecuencia.
Una sola operación de lectura puede leer una secuencia contigua de ubicaciones de la matriz, por lo que es posible devolver un grupo de valores múltiples desde una operación de lectura. El número máximo de ubicaciones contiguas que se pueden leer en una sola operación es M.
El objetivo es agrupar las ubicaciones para minimizar el número promediado en el tiempo de las operaciones de lectura. En el caso de que haya más de una forma de hacerlo, el desempate consiste en minimizar el número de ubicaciones promediado en el tiempo.
(puntos de bonificación se otorgan si el algoritmo para hacer esto permite que los cambios graduales en la lista de ubicaciones - es decir, agregar o quitar un lugar a/de la lista no requiere las agrupaciones que volver a calcular a partir de cero)
Trataré de aclarar esto con algunos ejemplos donde M = 6.
El siguiente diagrama muestra la matriz de ubicaciones. Los números representan el período de lectura deseado para esa ubicación.
| 1 | 1 | | | 1 | | | | | | 5 | | 2 |
\-------------------/ \-----------/
group A group B
En este primer ejemplo, el grupo A se lee cada segundo y el grupo B cada 2 segundos. Tenga en cuenta que la ubicación que debe leerse cada 5 segundos se lee realmente cada 2 segundos, lo cual está bien.
| 1 | | | | | 1 | 1 | | 1 |
\-----------------------/\----------/
group A group B (non-optimal!)
En este ejemplo se muestra un error de mi algoritmo simplista inicial, que consistía en llenar el primer grupo hasta la saciedad y luego comenzar otra. La siguiente agrupación es más óptima porque aunque el número de grupo lee por segundo es el mismo, el número de ubicaciones leer en esos grupos es menor:
| 1 | | | | | 1 | 1 | | 1 |
\---/ \---------------/
group A group B (optimal)
Finalmente, un ejemplo en el que tres grupos es mejor que dos:
| 5 | | | | | 1 | 1 | | | | | 5 |
\-----------------------/\----------------------/
group A group B (non-optimal)
Esta solución requiere dos lecturas grupales por segundo. Una mejor solución es la siguiente:
| 5 | | | | | 1 | 1 | | | | | 5 |
\---/ \-------/ \---/
group A group B group C
Esto requiere dos lecturas cada 5 segundos (grupos A y C) más uno cada segundo (grupo B): 1,4 grupo lee por segundo.
Editar: (Hay una solución aún mejor para este ejemplo si permite que las lecturas sean no periódicas. En el 1er segundo, lea los dos grupos de la primera solución. En los segundos 2, 3, 4 y 5 lea el grupo B de la segunda solución. Repita. Esto da como resultado 1.2 lecturas grupales por segundo. Pero no lo permitiré porque haría que el código sea responsable de programar las lecturas mucho más complicado.)
Busqué algoritmos de clústeres pero este no es un problema de agrupamiento También encontré Algorithm to allocate a list of numbers to N groups under certain condition, lo que apuntó al problema del "contenedor de basura", pero tampoco creo que sea esto.
Por cierto, perdón por el título vago. No puedo pensar en una descripción concisa, ni siquiera en palabras clave de búsqueda relevantes.
Nuevos ejemplos añadido 28 Septiembre 2010:
Esto es como el ejemplo anterior, pero todos los elementos de la actualización a la misma velocidad. Ahora dos grupos es mejor que tres:
| 1 | | | | | 1 | 1 | | | | | 1 |
\-----------------------/\----------------------/
group A group B (optimal)
He empezado a tratar de ver cómo se pueden implementar las mejoras iterativas. Supongamos que un algoritmo de agrupación se acercó con:
| 1 | | | | | 1 | 1 | | | | | 1 | 1 | | | | | 1 |
\---/ \-------/ \-------/ \---/
group A group B group C group D (non-optimal)
\-----------------------/\----------------------/\----------------------/
group A group B group C (optimal)
Esto puede ser mejorado a tres grupos adyacentes cada uno de 6. Rex sugirió (comentario a continuación) que podía probar la combinación de tripletes en parejas. Pero en este caso tendría que combinar un cuarteto en un triplete, porque no hay una disposición intermedia legal en la que A + B + C (o B + C + D) se pueda reorganizar en un par dejando D tal como está.
Originalmente pensé que esto era una indicación de que en el caso general no hay garantía de que se pueda crear una nueva solución válida a partir de una solución válida existente haciendo una modificación local. Esto habría significado algoritmos como el recocido simulado, algoritmos genéticos, etc., podrían usarse para tratar de refinar una solución subóptima.
Pero Rex señaló (comenta a continuación) que siempre puedes dividir un grupo existente en dos. A pesar de que esto siempre aumenta la función de costos, todo lo que significa es que la solución necesita salir de su mínimo local para alcanzar el mínimo global.
que iba a decir siempre se puede agrupar elementos adyacentes con el mismo tiempo (grupo B en su último ejemplo) pero eso puede no ser cierto es en casos de esquina donde M entra en juego. Señala una estrategia de construir progresivamente grupos más grandes con reglas sensatas.¿Qué tan grande es el tamaño de su problema? – phkahler
Parece que podría ser un problema NP-Completo o al menos un problema NP-Hard en el caso teóricamente óptimo. Puede intentar volver a publicarlo en [CS Theory Stack Exchange] (http://cstheory.stackexchange.com/). –
@phkahler: En mi caso particular, M es alrededor de 100, el tamaño de la matriz puede ser de 1 a 30000 o más, pero normalmente unos pocos cientos, y el número de ubicaciones quería algo entre 1 y 100 más o menos. –