camarilla problema de diseño de algoritmos

Question

Una de las tareas en mi clase de algoritmos es diseñar un algoritmo de búsqueda exhaustiva para resolver el problema de la camarilla. Es decir, dado un gráfico de tamaño n , se supone que el algoritmo para determinar si hay una completa sub-gráfico de tamaño k . Creo que he recibido la respuesta, pero no puedo evitar pensar que se podría mejorar. Aquí 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 Python-como pseudocódigo):

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 matriz de adyacencia de tamaño n por n, y k el tamaño del subgrafo para encontrar

salida :. Todos los subgraphs completo en una de 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 perdido, así como maneras de hacer esto más fácil de leer (que no estoy acostumbrado a usar mucho pseudocódigo).

Version 3

Afortunadamente, hablé con mi profesor antes de enviar la tarea. Cuando le mostré el pseudo-código que había escrito, sonrió y me dijo que lo hice manera demasiado trabajo. Por un lado, yo no tenía que presentar pseudo-código; Sólo tenía que demostrar que entendía el problema. Y dos, que fue querer la solución de la fuerza bruta. Así que lo que parecía girar en algo como esto:

entrada : Un gráfico G = (V, E), el tamaño de la camarilla para encontrar k

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

Algoritmo

1. Encuentre el producto cartesiano V ^k .
2. Para cada tupla en el resultado, la prueba de si cada vértice está conectado a todos los demás. Si todos están conectados, de vuelta verdad y salir.
3. Vuelta falsa y salida.

Actualizar : Añadido segunda versión. Creo que esto es cada vez mejor, aunque no he añadido ningún tipo de programación dinámica de fantasía (que yo sepa).

ACTUALIZACIÓN 2 : Se ha añadido un poco más de comentar y documentación para hacer la versión 2 más legible. Esto probablemente será la versión enciendo en la actualidad. Gracias por la ayuda de todos! Me gustaría poder aceptar más de una respuesta, pero acepté la respuesta por la persona que me ha ayudado a la mayoría. Voy a dejar que ustedes saben lo que piensa mi profesor.

Answer 1

Algunos comentarios:

• Sólo es necesario tener en cuenta n-k-elegir combinaciones de vértices, no todos los k-tuplas (n ^ k de ellos).
• connected(tuple) no se ve bien. No es necesario restablecer unconnected dentro del bucle?
• Como los otros han sugerido, hay mejores maneras de fuerza bruta esto. Considere la siguiente relación recursiva: A (+ 1 k) -subgraph es un clique si los primeros k vértices forman un clique y el vértice (k + 1) es adyacente a cada uno de los primeros k vértices. Se puede aplicar esto en dos direcciones:
  • Comience con un 1-camarilla y ampliar gradualmente la camarilla hasta obtener el tamaño deseado. Por ejemplo, si m es el mayor vértice en la camarilla actual, tratar de añadir vértices {m + 1, m + 2, ..., n-1} para obtener una camarilla que es un vértice más grande. (Esto es similar a un recorrido de árbol de profundidad primero, donde los hijos de un nodo de árbol son los vértices más grande que el más grande de vértices en la camarilla actual.)
  • Comience con un subgrafo del tamaño deseado y comprobar si se trata de una camarilla, usando la relación recursiva. Establecer una mesa memoization para almacenar los resultados a lo largo del camino.
• (sugerencia aplicación) Utilizar una matriz de adyacencia (0-1) para representar los bordes de la gráfica.
• (poda inicial) Tire todos los vértices con grado menor que k.

Answer 2

Una vez implementado un algoritmo para encontrar todas las camarillas máxima 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 - que describe una solución retroceso que me pareció muy útil como guía, aunque he cambiado mucho desde ese papel. Se necesitaría una suscripción para llegar a eso, aunque, pero supongo que su Universidad tendría una disponible.

Una cosa acerca de ese papel, aunque es realmente pienso que deberían haber llamado el "no ajustada" el "conjunto ya se considera" porque es demasiado confuso lo contrario.

Answer 3

El algoritmo "para cada k-tupla de vértices, si se trata de una camarilla, y luego de vuelta verdad" trabaja con seguridad. Sin embargo, es la fuerza bruta, lo que probablemente no es lo que un curso de algoritmos está buscando. En su lugar, considere lo siguiente:

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

Esta idea podría conducir a un mejor enfoque.

Answer 4

Tal vez probar un dinámica técnica de programación .

Answer 5

Es increíble lo que a escribir cosas como una pregunta le mostrará en lo que acabas de escribir. Esta línea:

P = A x A x A  //Cartesian product

debería ser la siguiente:

P = A ^k // producto cartesiano

  

¿Qué quiere decir por A ^ k? ¿Está tomando un producto de la matriz? Si es así, es una matriz de la adyacencia (usted dijo que era un conjunto 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}

Es básicamente un producto cartesiano de A k veces tomadas. Sobre el papel, lo escribí como k ser un exponente de A (acabo ahora descubierto la manera de hacer que el uso de rebajas).

Plus, A es simplemente un conjunto de cada vértice individuo sin tener en cuenta adyacencia.