M
Martin
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 <[email protected]>
#
# 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] == gridb + 2:
// bscore+=1
// elif gridb == 1:
// for i in range(0, len(nodes.connect[gridb])):
// if nodes.connect[gridb] == gridb - 1 or
nodes.connect[gridb] == gridb + 2:
// bscore+=1
// elif gridb == numnodes:
// for i in range(0, len(nodes.connect[gridb])):
// if nodes.connect[gridb] == gridb - 1 or
nodes.connect[gridb] == gridb - 2:
// bscore+=1
// elif gridb == numnodes-1:
// for i in range(0, len(nodes.connect[gridb])):
// if nodes.connect[gridb] == gridb + 1 or
nodes.connect[gridb] == 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] == grida - 2 or
tempnodes[grida] == grida + 2:
// aswapscore+=1
//
// elif grida == 0:
// for i in range(0, len(tempnodes[grida])):
// if tempnodes[grida] == grida + 1 or
tempnodes[grida] == grida + 2:
// aswapscore+=1
// elif grida == 1:
// for i in range(0, len(tempnodes[grida])):
// if tempnodes[grida] == grida - 1 or
tempnodes[grida] == grida + 2:
// aswapscore+=1
// elif grida == numnodes:
// for i in range(0, len(tempnodes[grida])):
// if tempnodes[grida] == grida - 1 or
tempnodes[grida] == grida - 2:
// aswapscore+=1
// elif grida == numnodes-1:
// for i in range(0, len(tempnodes[grida])):
// if tempnodes[grida] == grida + 1 or
tempnodes[grida] == grida - 2:
// aswapscore+=1
// if gridb > 1 and gridb < numnodes-1:
// for i in range(0, len(tempnodes[gridb])):
// if tempnodes[gridb] == gridb - 2 or
tempnodes[gridb] == gridb + 2:
// bswapscore+=1
// elif gridb == 0:
// for i in range(0, len(tempnodes[gridb])):
// if tempnodes[gridb] == gridb + 1 or
tempnodes[gridb] == gridb + 2:
// bswapscore+=1
// elif gridb == 1:
// for i in range(0, len(tempnodes[gridb])):
// if tempnodes[gridb] == gridb - 1 or
tempnodes[gridb] == gridb + 2:
// bswapscore+=1
// elif gridb == numnodes:
// for i in range(0, len(tempnodes[gridb])):
// if tempnodes[gridb] == gridb - 1 or
tempnodes[gridb] == gridb - 2:
// bswapscore+=1
// elif gridb == numnodes-1:
// for i in range(0, len(tempnodes[gridb])):
// if tempnodes[gridb] == gridb + 1 or
tempnodes[gridb] == 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] == 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) < 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
// nodes.connect=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)
// for j in range(0, len(nodes.connect)):
// if nodes.connect[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)
// for j in range(0, len(nodes.connect)):
// if nodes.connect[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, nodes.connect)
// swapall()
// print("Best path")
// pathify()
//
// main()
Hamilton Circuit problem, which is NP complete, in n^3 time.
#!/usr/bin/env python
#
# hamiltoncircuit.python
#
# Copyright 2011 Martin Musatov <[email protected]>
#
# 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] == gridb + 2:
// bscore+=1
// elif gridb == 1:
// for i in range(0, len(nodes.connect[gridb])):
// if nodes.connect[gridb] == gridb - 1 or
nodes.connect[gridb] == gridb + 2:
// bscore+=1
// elif gridb == numnodes:
// for i in range(0, len(nodes.connect[gridb])):
// if nodes.connect[gridb] == gridb - 1 or
nodes.connect[gridb] == gridb - 2:
// bscore+=1
// elif gridb == numnodes-1:
// for i in range(0, len(nodes.connect[gridb])):
// if nodes.connect[gridb] == gridb + 1 or
nodes.connect[gridb] == 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] == grida - 2 or
tempnodes[grida] == grida + 2:
// aswapscore+=1
//
// elif grida == 0:
// for i in range(0, len(tempnodes[grida])):
// if tempnodes[grida] == grida + 1 or
tempnodes[grida] == grida + 2:
// aswapscore+=1
// elif grida == 1:
// for i in range(0, len(tempnodes[grida])):
// if tempnodes[grida] == grida - 1 or
tempnodes[grida] == grida + 2:
// aswapscore+=1
// elif grida == numnodes:
// for i in range(0, len(tempnodes[grida])):
// if tempnodes[grida] == grida - 1 or
tempnodes[grida] == grida - 2:
// aswapscore+=1
// elif grida == numnodes-1:
// for i in range(0, len(tempnodes[grida])):
// if tempnodes[grida] == grida + 1 or
tempnodes[grida] == grida - 2:
// aswapscore+=1
// if gridb > 1 and gridb < numnodes-1:
// for i in range(0, len(tempnodes[gridb])):
// if tempnodes[gridb] == gridb - 2 or
tempnodes[gridb] == gridb + 2:
// bswapscore+=1
// elif gridb == 0:
// for i in range(0, len(tempnodes[gridb])):
// if tempnodes[gridb] == gridb + 1 or
tempnodes[gridb] == gridb + 2:
// bswapscore+=1
// elif gridb == 1:
// for i in range(0, len(tempnodes[gridb])):
// if tempnodes[gridb] == gridb - 1 or
tempnodes[gridb] == gridb + 2:
// bswapscore+=1
// elif gridb == numnodes:
// for i in range(0, len(tempnodes[gridb])):
// if tempnodes[gridb] == gridb - 1 or
tempnodes[gridb] == gridb - 2:
// bswapscore+=1
// elif gridb == numnodes-1:
// for i in range(0, len(tempnodes[gridb])):
// if tempnodes[gridb] == gridb + 1 or
tempnodes[gridb] == 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] == 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) < 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
// nodes.connect=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)
// for j in range(0, len(nodes.connect)):
// if nodes.connect[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)
// for j in range(0, len(nodes.connect)):
// if nodes.connect[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, nodes.connect)
// swapall()
// print("Best path")
// pathify()
//
// main()