Velocity Reviews > This algorithm written in Python solves at least a subset of theHamilton Circuit problem, which is NP complete, in n^3 time.

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

Martin
Guest
Posts: n/a

 03-20-2011
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 <(E-Mail Removed)>
#
# This program is free software; you may redistribute it and/or
modify
# it under the terms of the GNU General Public License as
# 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[b]
// nodes.initpos[b] = t
// for i in range(0, len(n)):
// for j in range(0, len(n[i])):
// if n[i][j] == a:
// n[i][j] = b
// elif n[i][j] == b:
// n[i][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][i] == grida - 2 or
nodes.connect[grida][i] == grida + 2:
// ascore+=1
//
// elif grida == 0:
// for i in range(0, len(nodes.connect[grida])):
// if nodes.connect[grida][i] == grida + 1 or
nodes.connect[grida][i] == grida + 2:
// ascore+=1
// elif grida == 1:
// for i in range(0, len(nodes.connect[grida])):
// if nodes.connect[grida][i] == grida - 1 or
nodes.connect[grida][i] == grida + 2:
// ascore+=1
// elif grida == numnodes:
// for i in range(0, len(nodes.connect[grida])):
// if nodes.connect[grida][i] == grida - 1 or
nodes.connect[grida][i] == grida - 2:
// ascore+=1
// elif grida == numnodes-1:
// for i in range(0, len(nodes.connect[grida])):
// if nodes.connect[grida][i] == grida + 1 or
nodes.connect[grida][i] == grida - 2:
// ascore+=1
// if gridb > 1 and gridb < numnodes-1:
// for i in range(0, len(nodes.connect[gridb])):
// if nodes.connect[gridb][i] == gridb - 2 or
nodes.connect[gridb][i] == gridb + 2:
// bscore+=1
// elif gridb == 0:
// 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 == 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()

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Roger Pack Ruby 2 08-18-2009 03:52 PM AAaron123 ASP .Net 0 10-03-2008 01:25 PM priya Java 3 08-30-2007 01:03 PM sales@lanscapecorp.com VOIP 0 01-03-2006 09:26 PM Lee Garrington C++ 1 02-11-2004 12:46 AM