Kliek probleem algoritme ontwerp

Question

Een van die opdragte in my algoritmes klas is die ontwerp van'n omvattende soektog algoritme op te los die kliek probleem.Dit is, gegewe'n grafiek van die grootte n, die algoritme is veronderstel om te bepaal of daar is'n volledige sub-grafiek van die grootte k.Ek dink ek het die antwoord gekry, maar ek kan nie help nie, maar dink dit verbeter kan word.Hier is wat ek het:

Weergawe 1

insette:'n grafiek verteenwoordig deur'n verskeidenheid van'n[0,...n-1], die grootte k van die subgraph te vind.

uitset:Ware as'n subgraph bestaan, Valse anders

Algoritme (in python-soos pseudokode):

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

Weergawe 2

insette:'n adjacency matriks van grootte n deur n, en k die grootte van die subgraph te vind

uitset:Al voltooi subgraphs in'n van grootte k.

Algoritme (hierdie keer in funksionele/Python pseudokode):

//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

Het enige iemand enige gedagtes, kommentaar of voorstelle?Dit sluit foute wat ek dalk gemis het asook maniere om te maak dit meer leesbaar is (ek is nie gewoond is aan die gebruik van baie pseudokode).

Weergawe 3

Gelukkig, ek het met my professor voor die indiening van die opdrag.Wanneer ek het hom die pseudo-kode wat ek geskryf het, het hy geglimlag en vir my gesê wat ek gedoen het manier te veel werk.Vir een, ek het nie het om te dien pseudo-kode;Ek moes net om te demonstreer dat ek verstaan die probleem.En twee, het hy was wil die brute krag oplossing.So, wat ek het in lyk iets soos hierdie:

insette:'n grafiek G = (V,E), die grootte van die kliek om te vind k

uitset:Ware as'n kliek bestaan, valse anders

Algoritme:

1. Vind die Kartesiese Produk V^k.
2. Vir elke tuple in die gevolg, toets of elke hoekpunt is gekoppel aan elke ander.As alles is verbind, in die terugkeer waar die in-en uitgang.
3. Terugkeer valse en uitgang.

UPDATE:Bygevoeg tweede weergawe.Ek dink dit is beter alhoewel ek nie bygevoeg om enige fancy dinamiese programmering (wat ek ken).

UPDATE 2:Bygevoeg'n paar meer kommentaar te lewer en dokumentasie om weergawe 2 meer leesbaar is.Dit sal waarskynlik die weergawe wat ek draai in vandag.Dankie vir almal se hulp!Ek wens ek kon aanvaar nie meer as een antwoord, maar ek aanvaar die antwoord deur die persoon wat my gehelp het om uit die meeste.Ek sal jou laat julle weet wat my professor dink.

Answer 1

Sommige kommentaar:

• Jy hoef net te kyk na N-kies-k kombinasies van hoekpunte, nie almal k-tuples (n ^ k van hulle).
• connected(tuple) lyk nie reg nie. Hoef jy nie te unconnected herstel binne die lus?
• As die ander het voorgestel, daar is beter maniere om dit te brute-dwing. Oorweeg die volgende rekursiewe verhouding: A (k + 1) -subgraph is 'n kliek of die eerste k hoekpunte vorm 'n kliek en toppunt (k + 1) is aangrensend aan elk van die eerste k hoekpunte. Jy kan dit toepas in twee rigtings:
  • Begin met 'n 1-kliek en geleidelik uit te brei die kliek totdat jy die verlangde grootte te kry. Byvoorbeeld, as m is die grootste toppunt in die huidige kliek, probeer om toppunt {m + 1, m + 2, ..., n-1} voeg by 'n kliek wat is een hoekpunt groter te kry. (Dit is soortgelyk aan 'n diepte-eerste boom traversal, waar die kinders van 'n boom node is die hoekpunte groter as die grootste toppunt in die huidige kliek.)
  • Begin met 'n subgraph van die verlangde grootte en kyk of dit is 'n kliek, die gebruik van die rekursiewe verhouding. Stel 'n memoization tafel resultate stoor op die pad.
• (implementering voorstel) Gebruik 'n adjacency matrix (0-1) te rande in die grafiek verteenwoordig.
• (aanvanklike snoei) Gooi weg al hoekpunte met graad minder as k.

Answer 2

Ek het eenkeer geïmplementeer 'n algoritme om al maksimale druk in 'n grafiek, wat 'n soortgelyke probleem om joune te vind. Die manier wat ek dit gedoen het is gebaseer op hierdie vraestel gebruik: http://portal.acm.org /citation.cfm?doid=362342.362367 - dit beskryf 'n back tracking oplossing wat ek baie nuttig as 'n gids, hoewel ek nogal 'n baie van daardie vraestel verander. 'N Mens sou 'n inskrywing moet op daardie al te kry, maar ek vermoed jou Universiteit sou 'n mens beskikbaar te hê.

Een ding oor daardie vraestel al is ek regtig dink hulle moet die "nie ingestel" die "reeds beskou stel" genoem het, want dit is net te verwarrend anders.

Answer 3

Die algoritme "vir elke k-tal van hoekpunte, al is dit 'n kliek, dan terug te keer waar" werk vir seker. Dit is egter brute krag, wat waarskynlik nie wat 'n algoritmes kursus is op soek na. In plaas daarvan, kyk na die volgende:

1. Elke toppunt is 'n 1-kliek.
2. Vir elke 1-kliek, elke hoekpunt wat gekoppel is aan die toppunt in die 1-kliek dra by tot 'n 2-kliek.
3. Vir elke 2-kliek, elke hoekpunt wat gekoppel is aan elke hoekpunt in die 2-kliek dra by tot 'n 3-kliek.
4. ...
5. Vir elke (k-1) -clique, elke hoekpunt wat gekoppel is aan elke hoekpunt in die (k-1) kliek dra by tot 'n k-kliek.

Hierdie idee kan lei tot 'n beter benadering.

Answer 4

Miskien probeer 'n dinamiese programmering tegniek .

Answer 5

Dit is ongelooflik wat tik dinge af as'n vraag sal wys jy oor wat jy het net geskryf.Hierdie lyn:

P = A x A x A  //Cartesian product

moet hierdie:

P = A ^k //Kartesiese produk

Wat bedoel jy deur'n^k?Is jy die neem van'n matriks produk?As dit so is, is die adjacency matriks (jy het gesê dit was'n skikking van n+1 elemente)?

In setbuilder notasie, dit sou lyk iets soos hierdie:

P = {(x0, x1, ...xk) | x0 ∈ A en x1 ∈ 'n ...en xk ∈ N}

Dit is basies net'n Kartesiese produk van'n geneem k keer.Op papier, het ek dit af as k'n aanvaar van'n (ek het nou net uitgepluis het hoe om dit te doen met behulp van afprijzingsmanager).

Plus, 'n is net'n skikking van elke individuele toppunt sonder agting vir adjacency.