Velocity Reviews - Computer Hardware Reviews

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

Reply
Thread Tools

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
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[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()
 
Reply With Quote
 
 
 
Reply

Thread Tools

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 Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
[ANN] release: a "which" command written in ruby--very useful forwindows users at least Roger Pack Ruby 2 08-18-2009 03:52 PM
Need regular expression for at least 7 characters and at least 1 special chatacter AAaron123 ASP .Net 0 10-03-2008 01:25 PM
'subset reduction algorithm' priya Java 3 08-30-2007 01:03 PM
New SIP/RTP VOIP Server software now available - Solves all NAT Traversal Problems. sales@lanscapecorp.com VOIP 0 01-03-2006 09:26 PM
subset algorithm Lee Garrington C++ 1 02-11-2004 12:46 AM



Advertisments