-
Notifications
You must be signed in to change notification settings - Fork 0
/
algo.py
72 lines (56 loc) · 1.65 KB
/
algo.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
import pygame as py, colors, main as m, sys
mini= 1000000009
minimumpath=[]
# globals
city_states = {}
cities = {}
adj = []
edges = []
def cost(nodes,costmatrix):
cst=0
for i in range(1,len(nodes)):
cst+=costmatrix[nodes[i-1]][nodes[i]]
cst+=costmatrix[nodes[len(nodes)-1]][nodes[0]]
return cst
def init_globals(x, y, z):
global city_states
global cities
global adj
city_states = x
cities = y
adj = z
def permute(start,end,nodes,costmatrix):
global mini
global minimumpath
if start==end:
fps=cost(nodes,costmatrix)
if fps<mini:
mini=fps
minimumpath=nodes[:]
else:
for i in range(start,end):
nodes[start],nodes[i]=nodes[i],nodes[start]
city_states[nodes[start]] = colors.LIGHT_PURPLE
m.update_screen(cities, city_states,1)
city_states[nodes[start]] = colors.GREEN
m.update_screen(cities, city_states, 1)
permute(start+1,end,nodes,costmatrix)
city_states[nodes[start]] = colors.RED
nodes[start],nodes[i]=nodes[i],nodes[start]
m.update_screen(cities, city_states, 1)
# def main():
# global mini
# global minimumpath
# # print(sys.maxint)
# n=4
# nodes= [x for x in range(0,n)]
# costmatrix=[[ 0, 10, 15, 20 ],
# [ 10, 0, 35, 25 ],
# [ 15, 35, 0, 30 ],
# [ 20, 25, 30, 0 ]]
# permute(0,n,nodes,costmatrix)
# print(mini)
# for i in range(n):
# minimumpath[i]=minimumpath[i]+1
# if __name__=="__main__":
# main()