algorithm - principiantes - introduccion a los algoritmos pdf

Diseño de algoritmo de problema de camarilla

Question

Una de las tareas en mi clase de algoritmos es diseñar un algoritmo de búsqueda exhaustivo para resolver el problema de la camarilla. Es decir, dado un gráfico de tamaño n , se supone que el algoritmo determina si hay una sub-gráfica completa de 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 subgráfico para encontrar.

salida : verdadero si existe un subgrafo, de lo contrario es falso

Algoritmo (en pseudocódigo tipo pitón):

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

Versión 2

entrada : una matriz de adyacencia 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 pensamientos, comentarios o sugerencias? 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 pseudocódigo que había escrito, sonrió y me dijo que había trabajado demasiado. Por un lado, no tuve que enviar pseudo-código; Solo tenía que demostrar que entendí el problema. Y dos, él quería la solución de fuerza bruta. Entonces, lo que entregué se parecía a esto:

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

salida : verdadero si existe una camarilla, de lo contrario es falso

Algoritmo :

1. Encuentre el producto cartesiano V ^k .
2. Para cada tupla en el resultado, prueba 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ó una 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:

• Solo necesita considerar combinaciones n-choose-k de vértices, no todas las k-tuplas (n ^ k de ellas).
• connected(tuple) no se ve bien. ¿No necesita reiniciar unconnected dentro del circuito?
• Como los otros han sugerido, hay mejores formas de forzar la fuerza de esto. 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. Puedes aplicar esto en dos direcciones:
  • Comience con una camarilla de 1 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 una camarilla, usando la relación recursiva. Configure una tabla de memorización para almacenar los resultados a lo largo del camino.
• (sugerencia de implementación) Use una matriz de adyacencia (0-1) para representar los bordes en el gráfico.
• (poda inicial) Tira todos los vértices con un grado menor que k.

Answer 2

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, considere lo siguiente:

1. Todos los vértices son de 1 camarilla.
2. Por cada 1 camarilla, cada vértice que se conecta con el vértice en la 1 camarilla contribuye a una 2 camarilla.
3. Por cada 2 clica, cada vértice que se conecta a cada vértice en la 2-clique contribuye a una 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-camarilla.

Esta idea puede conducir a un mejor enfoque.

Answer 3

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

debería ser esto:

P = A ^k // Producto cartesiano

¿Qué quieres decir con 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 solo un producto cartesiano de A tomado 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 4

Tal vez intente una técnica de programación dinámica .

Answer 5

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

Sin embargo, una cosa acerca de ese documento es que realmente creo que deberían haber llamado "no establecido" al "conjunto ya considerado" porque de otra manera es demasiado confuso.