This algorithm written in Python solves at least a subset of theHamilton Circuit problem, which is N

Discussion in 'Python' started by Martin, Mar 20, 2011.

  1. Martin

    Martin Guest

    This algorithm written in Python solves at least a subset of the
    Hamilton Circuit problem, which is NP complete, in n^3 time.

    #!/usr/bin/env python
    #
    # hamiltoncircuit.python
    #
    # Copyright 2011 Martin Musatov <>
    #
    # This program is free software; you may redistribute it and/or
    modify
    # it under the terms of the GNU General Public License as
    published by
    # the Free Software Foundation; either version 2 of the License,
    or
    # (at your option) any later version.
    #
    # This program is distributed in the hope it is useful,
    # but WITHOUT ANY WARRANTY; without even the implied warranty of
    # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
    # GNU General Public License for more details.
    #
    # You may obtain a copy of the GNU General Public License
    # with this program from the Free Software
    # Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
    # MA 02110-1301, USA.

    // numnodes=10
    //
    // import random
    //
    // class allnodes():
    // connect = []
    // gridpos = []
    // initpos = []
    // def __init__(self, numnodes):
    // for i in range(0, numnodes):
    // self.gridpos.append(i)
    // self.initpos.append(i)
    // self.connect.append([])
    //
    // nodes=allnodes(numnodes)
    // def swapref(n, a, b):
    // t = nodes.initpos[a]
    // nodes.initpos[a] = nodes.initpos
    // nodes.initpos = t
    // for i in range(0, len(n)):
    // for j in range(0, len(n)):
    // if n[j] == a:
    // n[j] = b
    // elif n[j] == b:
    // n[j] = a
    // return n
    // def makeswap(grida, gridb):
    // ascore = 0
    // aswapscore = 0
    // bscore = 0
    // bswapscore = 0
    // if grida > 1 and grida < numnodes-1:
    // for i in range(0, len(nodes.connect[grida])):
    // if nodes.connect[grida] == grida - 2 or
    nodes.connect[grida] == grida + 2:
    // ascore+=1
    //
    // elif grida == 0:
    // for i in range(0, len(nodes.connect[grida])):
    // if nodes.connect[grida] == grida + 1 or
    nodes.connect[grida] == grida + 2:
    // ascore+=1
    // elif grida == 1:
    // for i in range(0, len(nodes.connect[grida])):
    // if nodes.connect[grida] == grida - 1 or
    nodes.connect[grida] == grida + 2:
    // ascore+=1
    // elif grida == numnodes:
    // for i in range(0, len(nodes.connect[grida])):
    // if nodes.connect[grida] == grida - 1 or
    nodes.connect[grida] == grida - 2:
    // ascore+=1
    // elif grida == numnodes-1:
    // for i in range(0, len(nodes.connect[grida])):
    // if nodes.connect[grida] == grida + 1 or
    nodes.connect[grida] == grida - 2:
    // ascore+=1
    // if gridb > 1 and gridb < numnodes-1:
    // for i in range(0, len(nodes.connect[gridb])):
    // if nodes.connect[gridb] == gridb - 2 or
    nodes.connect[gridb] == gridb + 2:
    // bscore+=1
    // elif gridb == 0:
    // for i in range(0, len(nodes.connect[gridb])):
    // if nodes.connect[gridb] == gridb + 1 or
    nodes.connect[gridb][i] == gridb + 2:
    // bscore+=1
    // elif gridb == 1:
    // for i in range(0, len(nodes.connect[gridb])):
    // if nodes.connect[gridb][i] == gridb - 1 or
    nodes.connect[gridb][i] == gridb + 2:
    // bscore+=1
    // elif gridb == numnodes:
    // for i in range(0, len(nodes.connect[gridb])):
    // if nodes.connect[gridb][i] == gridb - 1 or
    nodes.connect[gridb][i] == gridb - 2:
    // bscore+=1
    // elif gridb == numnodes-1:
    // for i in range(0, len(nodes.connect[gridb])):
    // if nodes.connect[gridb][i] == gridb + 1 or
    nodes.connect[gridb][i] == gridb - 2:
    // bscore+=1
    // tempnodes = []
    // tempnodes.extend(nodes.connect)
    // t = tempnodes[grida]
    // tempnodes[grida]=tempnodes[gridb]
    // tempnodes[gridb]=t
    //
    // if grida > 1 and grida < numnodes-1:
    // for i in range(0, len(tempnodes[grida])):
    // if tempnodes[grida][i] == grida - 2 or
    tempnodes[grida][i] == grida + 2:
    // aswapscore+=1
    //
    // elif grida == 0:
    // for i in range(0, len(tempnodes[grida])):
    // if tempnodes[grida][i] == grida + 1 or
    tempnodes[grida][i] == grida + 2:
    // aswapscore+=1
    // elif grida == 1:
    // for i in range(0, len(tempnodes[grida])):
    // if tempnodes[grida][i] == grida - 1 or
    tempnodes[grida][i] == grida + 2:
    // aswapscore+=1
    // elif grida == numnodes:
    // for i in range(0, len(tempnodes[grida])):
    // if tempnodes[grida][i] == grida - 1 or
    tempnodes[grida][i] == grida - 2:
    // aswapscore+=1
    // elif grida == numnodes-1:
    // for i in range(0, len(tempnodes[grida])):
    // if tempnodes[grida][i] == grida + 1 or
    tempnodes[grida][i] == grida - 2:
    // aswapscore+=1
    // if gridb > 1 and gridb < numnodes-1:
    // for i in range(0, len(tempnodes[gridb])):
    // if tempnodes[gridb][i] == gridb - 2 or
    tempnodes[gridb][i] == gridb + 2:
    // bswapscore+=1
    // elif gridb == 0:
    // for i in range(0, len(tempnodes[gridb])):
    // if tempnodes[gridb][i] == gridb + 1 or
    tempnodes[gridb][i] == gridb + 2:
    // bswapscore+=1
    // elif gridb == 1:
    // for i in range(0, len(tempnodes[gridb])):
    // if tempnodes[gridb][i] == gridb - 1 or
    tempnodes[gridb][i] == gridb + 2:
    // bswapscore+=1
    // elif gridb == numnodes:
    // for i in range(0, len(tempnodes[gridb])):
    // if tempnodes[gridb][i] == gridb - 1 or
    tempnodes[gridb][i] == gridb - 2:
    // bswapscore+=1
    // elif gridb == numnodes-1:
    // for i in range(0, len(tempnodes[gridb])):
    // if tempnodes[gridb][i] == gridb + 1 or
    tempnodes[gridb][i] == gridb - 2:
    // bswapscore+=1
    //
    // if (ascore+bscore) < (aswapscore+bswapscore):
    // return True
    // else:
    // return False
    //
    // def gengraph(numnodes):
    // connectedness = False
    // connectfail = False
    // while(connectedness == False):
    // connectfail=False
    // same = True
    // while(same == True):
    // m = random.randrange(0, numnodes)
    // p = random.randrange(0, numnodes)
    // if m != p:
    // check = False
    // for i in range(0, len(nodes.connect[m])):
    // if nodes.connect[m][i] == p:
    // check=True
    // if check==False:
    // same = False
    // nodes.connect[m].append(p)
    // nodes.connect[p].append(m)
    // for i in range(0, numnodes):
    // if len(nodes.connect[i]) < 2:
    // connectfail=True
    // if connectfail == False:
    // connectedness = True
    // def swapall():
    // cont = True
    // foundswap=False
    // while (cont == True):
    // foundswap = False
    // for i in range(0, numnodes-1):
    // for j in range(i+1, numnodes):
    // if makeswap(i, j) == True:
    // foundswap = True
    // t = nodes.connect[i]
    // nodes.connect[i]=nodes.connect[j]
    // nodes.connect[j]=t
    // nodes.connect=swapref(nodes.connect, i, j)
    // break
    // if foundswap==True:
    // break
    // if foundswap == False:
    // cont = False
    // def pathify():
    //
    // for i in range(0, numnodes-2, 2):
    // check = False
    // print(nodes.initpos[i])
    // for j in range(0, len(nodes.connect[i])):
    // if nodes.connect[i][j] == i+2:
    // check = True
    // print("-")
    // break
    // if check == False :
    // print("x")
    // print(nodes.initpos[numnodes-2])
    // check = False
    // for j in range(0, len(nodes.connect[numnodes-2])):
    // if nodes.connect[numnodes-2][j] == numnodes-1:
    // check = True
    // print(".")
    // break
    // if check == False:
    // print("x")
    //
    // for i in range(numnodes -1,1 , -2):
    // check = False
    // print(nodes.initpos[i])
    // for j in range(0, len(nodes.connect[i])):
    // if nodes.connect[i][j] == i-2:
    // check = True
    // print("-")
    // break
    // if check == False:
    // print("x")
    // print(nodes.initpos[1])
    // check = False
    // for j in range(0, len(nodes.connect[1])):
    // if nodes.connect[1][j] == 0:
    // check = True
    // print("-")
    // break
    // if check == False:
    // print("x")
    //
    //
    // def main():
    // gengraph(numnodes)
    //
    // for i in range(0, numnodes):
    // print(nodes.initpos[i], nodes.connect[i])
    // swapall()
    // print("Best path")
    // pathify()
    //
    // main()[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
     
    Martin, Mar 20, 2011
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Tomer Levinboim

    pointer to function solves bug ?

    Tomer Levinboim, May 21, 2004, in forum: C Programming
    Replies:
    1
    Views:
    314
    Default User
    May 21, 2004
  2. Saurabh Aggrawal
    Replies:
    4
    Views:
    302
    Gianni Mariani
    Dec 1, 2005
  3. Replies:
    4
    Views:
    329
    mlimber
    Dec 5, 2006
  4. AAaron123
    Replies:
    0
    Views:
    615
    AAaron123
    Oct 3, 2008
  5. Roger Pack
    Replies:
    2
    Views:
    91
    Roger Pack
    Aug 18, 2009
Loading...

Share This Page