Camino Hamiltoniano

2011
03.22

Camino Hamiltoniano

Categoría: Ciencias Informáticas, Divertimática, Matemáticas, Programación, General / Etiqueta: Ciencias Informáticas, Matemáticas, Programación, Python / Añadir Comentario

Ayer a medianoche se cumplió el plazo para enviar la solución del camino hamiltoniano del concurso de El País. Efectivamente no tiene solución. Un amigo del trabajo me comentó la demostración (elegante y sencilla al a vez) que es la que se comenta en el vídeo. Te animo a que lo veas, porque resulta fácil de comprender.

Este pequeño programa en python busca caminos hamiltonianos en grafos e imprime la solución (o None si no existe, como es en el ejemplo del concurso):

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# vim:ts=4:et:sw=4

class Vertex(object):
    def __init__(self, node, *nodeList):
        self.i = node
        self.nodeList = list(nodeList)

    def __hash__(self):
        return self.i

    def reaches(self, vertex):
        ''' Can receive an integer or a Vertex
        '''
        if isinstance(vertex, int):
            return vertex in self.nodeList

        return self.reaches(vertex.i)

    def __str__(self):
        return '< ' + str(self.i) + '>'

    def __repr__(self):
        return self.__str__()


class Graph(object):
    def __init__(self):
        self.vList = {}

    def add(self, node, *nodeList):
        vertex = Vertex(node, *nodeList)
        self.vList[node] = vertex

    def hamiltonian(self, current = None, pending = None, destiny = None):
        ''' Returns a list of nodes which represent
        a hamiltonian path, or None if not found
        ''' 
        if pending is None:
            pending = self.vList.values()

        result = None

        if current is None:
            for current in pending:
                result = self.hamiltonian(current, [x for x in pending if x is not current], current)
                if result is not None:
                    break
        else:
            if pending == []: 
                if current.reaches(destiny):
                    return [current]
                else:
                    return None

            for x in [self.vList[v] for v in current.nodeList]:
                if x in pending:
                    result = self.hamiltonian(x, [y for y in pending if y is not x], destiny)
                    if result is not None:
                        result = [current] + result
                        break    

        return result

if __name__ == '__main__':
    G = Graph() 
    G.add(1, 2, 8, 11)
    G.add(2, 1, 6, 9)
    G.add(3, 6, 7, 9, 10)
    G.add(4, 5, 7, 10)
    G.add(5, 4, 8, 11)
    G.add(6, 2, 3, 8)
    G.add(7, 3, 4, 8)
    G.add(8, 1, 6, 7, 5)
    G.add(9, 2, 3, 11)
    G.add(10, 3, 4, 11)
    G.add(11, 1, 9, 10, 5)
    print G.hamiltonian()

#!/usr/bin/env python

# -*- coding: utf-8 -*-

# vim:ts=4:et:sw=4

class Vertex(object):

def __init__(self, node, *nodeList):

self.i = node

self.nodeList = list(nodeList)

def __hash__(self):

return self.i

def reaches(self, vertex):

''' Can receive an integer or a Vertex

'''

if isinstance(vertex, int):

return vertex in self.nodeList

return self.reaches(vertex.i)

def __str__(self):

return '< ' + str(self.i) + '>'

def __repr__(self):

return self.__str__()

class Graph(object):

def __init__(self):

self.vList = {}

def add(self, node, *nodeList):

vertex = Vertex(node, *nodeList)

self.vList[node] = vertex

def hamiltonian(self, current = None, pending = None, destiny = None):

''' Returns a list of nodes which represent

a hamiltonian path, or None if not found

'''

if pending is None:

pending = self.vList.values()

result = None

if current is None:

for current in pending:

result = self.hamiltonian(current, [x for x in pending if x is not current], current)

if result is not None:

break

else:

if pending == []:

if current.reaches(destiny):

return [current]

else:

return None

for x in [self.vList[v] for v in current.nodeList]:

if x in pending:

result = self.hamiltonian(x, [y for y in pending if y is not x], destiny)

if result is not None:

result = [current] + result

break

return result

if __name__ == '__main__':

G = Graph()

G.add(1, 2, 8, 11)

G.add(2, 1, 6, 9)

G.add(3, 6, 7, 9, 10)

G.add(4, 5, 7, 10)

G.add(5, 4, 8, 11)

G.add(6, 2, 3, 8)

G.add(7, 3, 4, 8)

G.add(8, 1, 6, 7, 5)

G.add(9, 2, 3, 11)

G.add(10, 3, 4, 11)

G.add(11, 1, 9, 10, 5)

print G.hamiltonian()

Boriel dijo2011.04.25 13:54

En enlace del vídeo está puesto (en naranja) en la primera línea del primer párrafo del artículo.

Like or Dislike: 0 0
LanderTaker dijo2011.04.25 13:48

Hola!

Te falta poner el enlace al video!

Saludos

Like or Dislike: 0 0
LanderTaker dijo2011.04.25 13:44

Hola

Dices algo de un video ¿Podrias poner el enlace?

Like or Dislike: 0 0

boriel.com