Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Encontrando ciclos hamiltonianos de um grafo não direcionado usando backtracking

+2 votos
98 visitas

1 Resposta

+3 votos
respondida Jun 11 por Pablo Castro (286 pontos)  
editado Jun 12 por Pablo Castro

Definição: um caminho hamiltoniano é um caminho que passa por todos os vértices de um grafo uma única vez sem repetir nenhum. Caso seja possível descrever um ciclo com este caminho, chamamos de ciclo hamiltoniano. Ou seja, um ciclo hamiltoniano é um caminho que começa e termina no mesmo ponto.

Para resolver ao exercício, primeiro foi criada uma função que retorna os caminhos hamiltonianos de um grafo, caso haja. Os argumentos dessa função são: o grafo, o tamanho do grafo e o ponto inicial. O que o algoritmo faz basicamente é:

  1. Dado um ponto \(p\) (vértice do grafo), o adicionamos à uma lista no qual ficará registrado o caminho percorrido;
  2. Analisamos todos os outros pontos \(p'\) ligados à \(p\);
  3. Seja um \(p'\) arbitrário, criamos uma lista auxiliar com o caminho e chamamos novamente a função para \(p'\) e essa nova lista (aqui começa o backtracking).

Assim, se algum \(p''\) ligado a \(p'\) é tal que \(p'' = p\), paramos a verificação, já que não se trata de um caminho hamiltoniano e voltamos um passo.

Após isso, caso haja caminhos hamiltonianos, basta verificarmos se o último ponto do caminho possui ligação com o primeiro, se sim, temos um ciclo hamiltoniano.

Note que, por se tratar de um ciclo, não importa para qual ponto inicial começamos o backtraking. A construção das ligações do grafo foi feita com um dicionário, associando a cada vértice uma lista com os outros vértices no qual ele é ligado.

Segue implementação (os comentários foram os print's usados para ver o que estava acontecendo):

def caminho_hamiltoniano(grafo, size, ponto, path=[]):
    # print(f'Caminho hamiltoniano ligado ao ponto={ponto}, caminho={path}')
    if ponto not in set(path):
        path.append(ponto)
        if len(path) == size:
            return path
        # inicio do backtracking
        todos_candidatos = []
        for prox_ponto in grafo.get(ponto, []):
            res_path = [i for i in path]
            # print(res_path)
            candidatos = caminho_hamiltoniano(grafo, size, prox_ponto, res_path)
            if candidatos is not None:  # sai do loop ou termina caminho
                todos_candidatos.extend(candidatos)
                # print(todos_candidatos)
            else:
                # print(f'Caminho {path} termina')
                pass
        return todos_candidatos
    else:
        # print(f'Ponto {ponto} já está no caminho {path}')
        return None


if __name__ == '__main__':
    ponto = 1
    size = 4
    grafo = {1: [2, 3], 2: [1, 3, 4], 3: [1, 2, 4], 4: [2, 3]}
    path = caminho_hamiltoniano(grafo, size, ponto)
    # print(path)  # retorna uma única lista com todos os pontos que formam os caminhos
    # Abaixo separo path em sublistas, cada uma é um caminho diferente gerado por caminho_hamiltoniano()
    lista_candidados = []
    for j in range(size):
        while j*size < len(path):
            start = int(j*size)
            end = int((j+1)*size)
            lista_candidados.append(path[start:end])
            break
    print(f'Os candidatos a ciclos hamiltonianos são: {lista_candidados}')

    # verificação se o caminho é um ciclo hamiltoniano
    if len(lista_candidados) == 0:
        print('Nesse grafo não há caminho hamiltoniano, logo, não há ciclo hamiltoniano')
    else:
        for candidato in lista_candidados:
            if ponto in grafo[candidato[-1]]:
                print(f'O caminho {candidato} é um ciclo hamiltoniano')
            else:
                print(f'O caminho {candidato} não é um ciclo hamiltoniano')

Output:

Os candidatos a ciclos hamiltonianos são: [[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2]]
O caminho [1, 2, 3, 4] não é um ciclo hamiltoniano 
O caminho [1, 2, 4, 3] é um ciclo hamiltoniano
O caminho [1, 3, 2, 4] não é um ciclo hamiltoniano 
O caminho [1, 3, 4, 2] é um ciclo hamiltoniano

Outros exemplos:

Grafo com caminhos, porém sem ciclo hamiltoniano:

grafo = {1: [2], 2: [1, 3, 4], 3: [2, 4], 4: [2, 3]}
# Output:
Os candidatos a ciclos hamiltonianos são: [[1, 2, 3, 4], [1, 2, 4, 3]]
O caminho [1, 2, 3, 4] não é um ciclo hamiltoniano
O caminho [1, 2, 4, 3] não é um ciclo hamiltoniano

Grafo sem caminhos e nem ciclos hamiltonianos:

grafo = {1: [2], 2: [1, 4], 4: [2]}
# Output:
Os candidatos a ciclos hamiltonianos são: []
Nesse grafo não há caminho hamiltoniano, logo, não há ciclo hamiltoniano

Grafos direcionados com ciclos hamiltonianos:

grafo = {1: [2], 2: [3, 4], 3: [1, 4], 4: [3]}
# Output:
Os candidatos a ciclos hamiltonianos são: [[1, 2, 3, 4], [1, 2, 4, 3]] 
O caminho [1, 2, 3, 4] não é um ciclo hamiltoniano
O caminho [1, 2, 4, 3] é um ciclo hamiltoniano

Grafos direcionados sem ciclos hamiltonianos:

grafo = {1: [2], 2: [3, 4], 3: [1, 4], 4: [2]}
# Output:
Os candidatos a ciclos hamiltonianos são: [[1, 2, 3, 4]]
O caminho [1, 2, 3, 4] não é um ciclo hamiltoniano
comentou Jul 8 por Monica Guo (41 pontos)  
Oi, Pablo! Muito legal a sua implementação e o fato de você ter utilizado *set* ao invés de lista, dado que é mais aplicável à situação (em que cada elemento deve aparecer apenas uma vez na estrutura). Testei vários exemplos de grafos não direcionados e a sua implementação funcionou perfeitamente em todos eles, inclusive sempre que não havia caminho ou ciclo Hamiltoniano, o algoritmo retornava que não havia mesmo.

Contudo, vi que você testou o algoritmo com grafos direcionados. Nesse caso, acabei encontrando situações em que o algoritmo não identifica que não há caminho ou ciclo Hamiltoniano (dá um erro no programa). Por exemplo, tente rodar o grafo direcionado dado por {1:[2], 2:[3,4], 4:[3]}.
comentou Jul 9 por Pablo Castro (286 pontos)  
Obrigado pelo comentário.

O erro se dá pq não colocamos nenhuma informação à respeito do ponto 3 do grafo. Se testarmos o grafo {1:[2], 2:[3,4], 3:[], 4:[3]} que é equivalente a do comentário, teremos o seguinte output:

Os candidatos a ciclos hamiltonianos são: [[1, 2, 4, 3]]
O caminho [1, 2, 4, 3] não é um ciclo hamiltoniano
...