Diseño de algoritmo de problema de camarilla

Question

Una de las asignaciones en mi clase de algoritmos es diseñar un algoritmo de búsqueda exhaustivo para resolver el problema de camarilla. Es decir, dado un gráfico de tamaño n, se supone que el algoritmo determina si hay una sub-gráfica completa del tamaño k. Creo que he obtenido la respuesta, pero no puedo evitar pensar que se puede mejorar. Esto es lo que tengo:

Versión 1

entrada: Un gráfico representado por una matriz A [0, ... n -1], el tamaño k del subgrafo de encontrar.

salida: Verdadero si existe un subgrafo, False en caso contrario

Algoritmo (en pseudocódigo pitón-like):

def clique(A, k): 
    P = A x A x A //Cartesian product 
    for tuple in P: 
     if connected(tuple): 
      return true 
    return false 

def connected(tuple): 
    unconnected = tuple 
    for vertex in tuple: 
     for test_vertex in unconnected: 
      if vertex is linked to test_vertex: 
       remove test_vertex from unconnected 
    if unconnected is empty: 
     return true 
    else: 
     return false 

Version 2

entrada: una adyacencia matriz de tamaño n por n, y k el tamaño del subgrafo para encontrar

salida: Todos los subgrafos completos en A del tamaà ± o k.

Algoritmo (esta vez en pseudocódigo funcional/Python):

//Base case: return all vertices in a list since each 
//one is a 1-clique 
def clique(A, 1): 
    S = new list 
    for i in range(0 to n-1): 
     add i to S 
    return S 

//Get a tuple representing all the cliques where 
//k = k - 1, then find any cliques for k 
def clique(A,k): 
    C = clique(A, k-1) 
    S = new list 
    for tuple in C: 
     for i in range(0 to n-1): 
      //make sure the ith vertex is linked to each 
      //vertex in tuple 
      for j in tuple: 
       if A[i,j] != 1: 
        break 
      //This means that vertex i makes a clique 
      if j is the last element: 
       newtuple = (i | tuple) //make a new tuple with i added 
       add newtuple to S 
    //Return the list of k-cliques 
    return S 

¿Alguien tiene alguna idea, comentario o sugerencia? Esto incluye errores que podría haber pasado por alto, así como formas de hacerlo más legible (no estoy acostumbrado a usar mucho pseudocódigo).

Versión 3

Afortunadamente, hablé con mi profesor antes de enviar la tarea. Cuando le mostré el pseudo-código que había escrito, me sonrió y me dijo que hice manera demasiado trabajo. Por un lado, no tuve que enviar pseudo-código; Solo tenía que demostrar que entendí el problema. Y dos, él era queriendo la solución de fuerza bruta. Así que lo que ha entregado la veía algo como esto:

entrada: Un grafo G = (V, E), el tamaño de la camarilla de encontrar k

salida: Verdadero si una camarilla existe, falso en caso contrario

Algoritmo:

1. Encuentre el producto cartesiano V ^k.
2. Para cada tupla del resultado, compruebe si cada vértice está conectado entre sí. Si todos están conectados, devuelva verdadero y salga.
3. Devuelve falso y sale.

ACTUALIZACIÓN: Se agregó la segunda versión. Creo que esto está mejorando, aunque no he agregado ninguna programación dinámica elegante (que yo sepa).

ACTUALIZACIÓN 2: Se agregaron más comentarios y documentación para hacer que la versión 2 sea más legible. Esta será probablemente la versión que entregue hoy. Gracias por la ayuda de todos! Desearía poder aceptar más de una respuesta, pero acepté la respuesta de la persona que me ayudó más. Les dejaré saber lo que piensa mi profesor.

Answer 1

Algunos comentarios:

• Sólo se necesitan considerar n-k-elegir combinaciones de vértices, no todos los k-tuplas (n^k de ellos).
• connected(tuple) no se ve bien. ¿No necesita reiniciar unconnected dentro del lazo?
• Como han sugerido los otros, hay mejores formas de forzarlo brutalmente. Considere la siguiente relación recursiva: A (k + 1) -subgraph es una camarilla si los primeros k vértices forman una camarilla y el vértice (k + 1) es adyacente a cada uno de los primeros k vértices. Puede aplicar esto en dos direcciones:
  • Comience con 1 camarilla y amplíe gradualmente la camarilla hasta que obtenga el tamaño deseado. Por ejemplo, si m es el vértice más grande en la camarilla actual, intente agregar vértice {m + 1, m + 2, ..., n-1} para obtener una camarilla que tenga un vértice más grande. (Esto es similar a un cruce de árbol en profundidad, donde los hijos de un nodo de árbol son los vértices más grandes que el vértice más grande en la camarilla actual).
  • Comience con un subgrafo del tamaño deseado y verifique si es un camarilla, usando la relación recursiva. Configure una tabla memoization para almacenar los resultados en el camino.
• (sugerencia de implementación) Utilice una matriz de adyacencia (0-1) para representar los bordes en el gráfico.
• (poda inicial) Deseche todos los vértices con un grado menor que k.

Answer 2

Es sorprendente lo que escribir cosas como una pregunta le mostrará lo que acaba de escribir. Esta línea:

P = A x A x A //Cartesian product 

debe ser la siguiente:

P = A ^k // producto cartesiano

¿Qué quiere decir por A^k? ¿Estás tomando un producto de matriz? Si es así, ¿es A la matriz de adyacencia (dijiste que era una matriz de n + 1 elementos)?

En la notación setbuilder, se vería algo como esto:

P = {(x0, x1, ... xk) | x0 ∈ A y x1 ∈ A ... y xk ∈ A}

Básicamente es un producto cartesiano de A tomada k veces. En papel, lo escribí como k siendo un superíndice de A (ahora descubrí cómo hacerlo usando el descuento).

Además, A es solo una matriz de cada vértice individual sin tener en cuenta la adyacencia.

Answer 3

Quizás pruebe dynamic programming technique.

Answer 4

Una vez implementé un algoritmo para encontrar todas las camarillas máximas en un gráfico, que es un problema similar al suyo. La forma en que lo hice se basó en este documento: http://portal.acm.org/citation.cfm?doid=362342.362367 - describió una solución de retroceso que me pareció muy útil como guía, aunque cambié bastante de ese documento. Sin embargo, necesitaría una suscripción para obtener eso, pero supongo que su Universidad tendría uno disponible.

Una cosa sobre ese papel es que realmente creo que deberían haber llamado "no establecido" al "conjunto ya considerado" porque de otra manera es demasiado confuso.

Answer 5

El algoritmo "para cada k-tupla de vértices, si es una camarilla, luego devuelve verdadero" funciona con seguridad. Sin embargo, es fuerza bruta, que probablemente no es lo que está buscando un curso de algoritmos. En su lugar, tenga en cuenta lo siguiente:

1. Cada vértice es de 1 camarilla.
2. Por cada 1 camarilla, cada vértice que se conecta al vértice en la 1 camarilla contribuye a una camarilla de 2 camarillas.
3. Por cada 2 camarilla, cada vértice que se conecta a cada vértice en la 2-camarilla contribuye a una 3 camarilla.
4. ...
5. Para cada (k-1) -clique, cada vértice que se conecta a cada vértice en la (k-1) camarilla contribuye a una k-camarilla.

Esta idea podría conducir a un mejor enfoque.