-
Notifications
You must be signed in to change notification settings - Fork 1
/
queen for 8.py
69 lines (57 loc) · 2.09 KB
/
queen for 8.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
import random
def randomSolution(queen):
cities = list(range(len(queen)))
solution = []
for i in range(len(queen)):
randomCity = cities[random.randint(0, len(cities) - 1)]
solution.append(randomCity)
cities.remove(randomCity)
return solution
def routeLength(queen, solution):
routeLength = 0
for i in range(len(solution)):
routeLength += queen[solution[i - 1]][solution[i]]
return routeLength
def getNeighbours(solution):
neighbours = []
for i in range(len(solution)):
for j in range(i + 1, len(solution)):
neighbour = solution.copy()
neighbour[i] = solution[j]
neighbour[j] = solution[i]
neighbours.append(neighbour)
return neighbours
def getBestNeighbour(queen, neighbours):
bestRouteLength = routeLength(queen, neighbours[0])
bestNeighbour = neighbours[0]
for neighbour in neighbours:
currentRouteLength = routeLength(queen, neighbour)
if currentRouteLength < bestRouteLength:
bestRouteLength = currentRouteLength
bestNeighbour = neighbour
return bestNeighbour, bestRouteLength
def hillClimbing(queen):
currentSolution = randomSolution(queen)
currentRouteLength = routeLength(queen, currentSolution)
neighbours = getNeighbours(currentSolution)
bestNeighbour, bestNeighbourRouteLength = getBestNeighbour(queen, neighbours)
while bestNeighbourRouteLength < currentRouteLength:
currentSolution = bestNeighbour
currentRouteLength = bestNeighbourRouteLength
neighbours = getNeighbours(currentSolution)
bestNeighbour, bestNeighbourRouteLength = getBestNeighbour(queen, neighbours)
return currentSolution, currentRouteLength
def main():
queen = [
[1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0]
]
print(hillClimbing(queen))
if __name__ == "__main__":
main()