Algoritmo / aproximación para set / distancia de Hamming independiente combinado

Question

Entrada: Gráfico G Salida: varios conjuntos independientes, por lo que la composición de un nodo a todos los conjuntos independientes es único. Por tanto, un nodo no tiene conexiones a cualquier nodo en su propio juego. Aquí es una ruta de ejemplo.

Desde la aclaración fue llamado por aquí otra rephrasal:

Divide un gráfico dado en conjuntos de modo que

1. i puede decir un nodo de todos los demás por su pertenencia a los conjuntos, por ejemplo, si el nodo i está presente sólo en conjunto A ningún otro nodo debe estar presente en un conjunto solamente

   si el nodo j está presente en el conjunto A y B entonces ningún otro nodo debe estar presente en el conjunto A y B solamente. si el número de miembros de nodos está codificada por un patrón de bits, entonces estos patrones de bits han distancia de Hamming al menos un

2. si dos nodos son adyacentes en el gráfico, no deben estar presentes en el mismo conjunto, por lo tanto, ser un conjunto independiente

Ejemplo: B no tiene nodos adyacentes D => A, A => D

Solución:

1. A B /
2. / B D

A tiene patrón de bits 10 y ningún nodo adyacente en su conjunto. B tiene patrón de bits 11 y ningún nodo adyacente, D tiene 01 por lo tanto, todos los nodos han distancia de Hamming al menos 1 un no adyacente nodos => correcta

incorrecto, porque D y A están conectados:

1. A D B
2. / D B

A tiene patrón de bits 10 y D en su conjunto, que son adyacentes. B tiene patrón de bits 11 y ningún nodo adyacente, D tiene 11 como tiene B, por lo que hay dos errores en esta solución y por lo tanto no se acepta.

Por supuesto, esto debe extenderse a más conjuntos como el número de nodos en el gráfico aumenta, ya que se necesita por lo menos conjuntos log(n).

Ya escribió una transformación en MAX-SAT, utilizar un solucionador se sentó para esto. pero el número de cláusulas es simplemente demasiado grande. Un enfoque más directo sería bueno. Hasta ahora tengo una aproximación, pero me gustaría una solución exacta o, al menos, una mejor aproximación.

I han intentado un enfoque donde solía un enjambre de partículas para optimizar partir de una solución arbitraria hacia una mejor. Sin embargo, el tiempo de ejecución es bastante horrible y los resultados están lejos de ser grande. Busco a un algoritmo dinámico o algo, sin embargo, no puedo entender cómo dividir y conquistar este problema.

Answer 1

No es una respuesta completa, y no sé lo útil que será para usted. Pero aquí va:

La distancia de Hamming me parece una cortina de humo. Su planteamiento del problema dice que debe ser de al menos 1, pero podría ser 1000. Baste decir la codificación de bits para la pertenencia de ajuste de cada nodo es único.

Su planteamiento del problema no lo dicen claramente, pero su solución anterior sugiere que cada nodo debe ser un miembro de al menos 1 set. es decir. un poco codifica de los 0 de no está permitido para la pertenencia conjunto de cualquier nodo.

Haciendo caso omiso de nodos conectados por un momento, nodos disjuntos son fáciles: Simplemente número ellos secuencialmente con una codificación bit no utilizado. Guardar los de la última.

Su ejemplo anterior usos dirigida bordes, pero de nuevo, que me parece una cortina de humo. Si A no puede estar en el mismo conjunto como D porque A => D, D no puede ser en el mismo conjunto como A, independientemente de si D => A.

Usted menciona que necesitan por lo menos log (n) conjuntos. También tendrá en la mayoría de los conjuntos N. Un gráfico completamente conectado (con (N ^ 2-N) / 2 bordes no dirigidos) requerirá N establece que contienen cada uno un solo nodo.

De hecho, si el gráfico contiene una simplex totalmente conectada de dimensiones M (M en 1..N-1) con m + 1 vértices y (M ^ 2 + M) / 2 bordes no dirigidos, se requerirá por lo menos M + 1 conjuntos.

En su ejemplo anterior, que tiene uno de tales simplex (M = 1) con 2 vértices {A, D} y 1 borde (no dirigida) {(A, D)}.

Parece que el problema se reduce a encontrar las mayores simplex totalmente conectados en su gráfico. Dicho de otra manera, usted tiene un problema de enrutamiento: ¿Cuántas dimensiones Qué se necesita para enrutar sus bordes por lo que ninguno cruz? No suena como un problema muy escalable.

El primer grande que se encuentra simplex es fácil. Cada nodo de vértice consigue un nuevo conjunto con su propio bits.

Los nodos disjuntos son fáciles. Una vez que los nodos conectados se tratan, simplemente Número de los nodos disjuntos omitiendo secuencialmente cualquier patrones de bits previamente usados. De su ejemplo anterior, ya que A y D tienen 01 y 10, el siguiente patrón de bits disponible para B es 11.

La parte difícil se convierte entonces en cómo doblar cualquier simplex restantes tanto como sea posible en la gama existente antes de crear nuevos conjuntos con nuevos bits. Cuando doble, hay que utilizar 2 o más bits (juegos) para cada nodo, y los bits (conjuntos) no debe de intersección con los bits (juegos) para cualquier nodo adyacente.

Considere lo que sucede a su ejemplo anterior, cuando se añade otro nodo, C, para el ejemplo:

Si C se conecta directamente a ambos A y D, entonces el problema inicial se convierte en la búsqueda de la 2-simplex con 3 vértices {A, C, D} y 3 bordes {(A, C), (A, D), ( DISCOS COMPACTOS)}. Una vez que A, C y D tienen los patrones de bits 001, 010 y 100, el patrón de bits disponible bajo para disjuntos B es 011.

Si, por el contrario, C se conecta directamente A o D, pero no ambos, el gráfico tiene dos 1-simplexes. Suponiendo que nos encontramos con el 1-simplex con vértices {A, D} primero que les dan los patrones de bits 01 y 10, el problema se convierte entonces en cómo doblar C en ese rango. El único patrón de bits con al menos 2 bits es 11, pero que se cruza con cualquier conecta el nodo C a lo que tenemos que crear un nuevo conjunto y poner C en ella. En este punto, la solución es similar a la anterior.

Si C es disjunta, B o C se obtienen el patrón de bits 11 y los restantes uno necesitará un nuevo conjunto y obtener el patrón de bits 100.

Conexiones C supone que B pero no a una o D. De nuevo, el gráfico tiene dos 1-simplexes pero esta vez disjuntos. Supongamos {A, D} se encuentra primero como anteriormente dando A y D los patrones de bits 10 y 01. Podemos doblar B o C en la gama existente. El patrón de bits sólo está disponible en el rango es de 11 y, o bien B o C podría conseguir que el patrón ya que ni es adyacente a una o D. Una vez que se utiliza 11, no hay patrones de bits con 2 o más bits puestos permanecer, y tendrá que crear un nuevo conjunto para el nodo restante dándole el patrón de bits 100.

Conexiones Supongamos que C a todos los 3 A, B y D. En este caso, el gráfico tiene un 2-simplex con 3 vertexes {A, C, D} y un 1-simplex con 2 vértices {B, C}. Procediendo como anteriormente, después de procesar el más grande simplex, A, C y D tendrán patrones de bits 001, 010, 100. Por plegable B en este rango, los patrones de bits disponibles con 2 o más bits puestos son: 011, 101, 110 y 111. Todos ellos, excepto 101 se cruzan con C de modo B conseguiría el patrón de bits 101.

La pregunta entonces es:? ¿Cómo se puede encontrar de manera eficiente las mayores simplex totalmente conectados

Si la búsqueda de la mayor simplex totalmente conectado es demasiado caro , se podría poner un aproximado de límite superior en el potencial simplex totalmente conectados mediante la búsqueda de mínimos máximos en términos de conexiones:

1. barrido a través de los bordes de la actualización vértices con un recuento de la bordes de conexión.

2. Para cada nodo conectado, crear una matriz de Cn cuenta inicialmente cero donde Cn es el recuento de los bordes conectado al nodo n.

3. barrido a través de los bordes de nuevo, para los nodos conectados n1 y n2, incrementar la cuenta en n1 correspondiente a Cn2 y viceversa. Si Cn2> Cn1, actualizar el último recuento en la matriz de n1 y viceversa.

4. barrido a través de los nodos conectados de nuevo, el cálculo de un límite superior en el mayor simplex cada nodo pudiera ser una parte de. Se puede construir una matriz casillero con una lista de vértices para cada una cota superior a medida que barre a través de los nodos.

5. El trabajo a través de la matriz casillero de mayor a menor extracción y nodos plegable en conjuntos únicos.

Si los nodos están en un conjunto de N y sus bordes en un conjunto E, la complejidad será: O (| N | + | E | + O (Paso 5))

Si los basta aproximación anterior, la pregunta es:? ¿Cómo se puede plegar de manera eficiente los nodos existentes en rangos dados los requisitos

Answer 2

Esto quizás no sea la respuesta que podría esperar, pero no puedo encontrar un lugar para añadir un comentario. Así lo escribo directamente aquí. No puedo entender completamente su pregunta. O es necesario un conocimiento específico de entender? ¿Qué es este conjunto independiente? Como sé un nodo en un conjunto independiente de un grafo dirigido tener un camino de dos vías a cualquier otro nodo en este conjunto. Es el concepto de la misma?

Si este problema es como lo que supongo, conjuntos independientes se pueden encontrar mediante este algoritmo: 1. hacer búsqueda en profundidad en el gráfico dirigido, registra el tiempo de árbol arraigado por este nodo está atravesado. 2. luego revertir todos los bordes en este gráfico 3. hacer la búsqueda en profundidad Frist de nuevo en el gráfico modificado. El algorihtm se explica precisamente por el libro "introducción a alogrithm"