-
Notifications
You must be signed in to change notification settings - Fork 1
/
functions.py
191 lines (136 loc) · 7.39 KB
/
functions.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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
# Function definitions file
from classes import *
# Returns heuristic value of cost from current node to goal node
def heuristic(client, graph):
heu_results = uniform_cost(client, graph, ifHeuristics=True)
if heu_results == -1:
return -1
elif client.optimCrit == 'tempo':
# return total time for relaxed problem
return heu_results[-2]
else:
# return total cost for relaxed problem
return heu_results[-1]
# Get path from start to goal
def get_path(current, start, closed_list):
"""Traces path from current node back to start."""
total_path = [current]
while current in closed_list and current != start:
total_path.append(closed_list[current][1])
total_path.append(closed_list[current][0])
current = closed_list[current][0]
total_path.append(closed_list[current][1])
total_path.append(closed_list[current][0])
# Reverse order and get rid of None (the parent of the start node)
return total_path[::-1][2:]
# Uninformed search algorithm
def uniform_cost(client, graph, ifHeuristics = False):
"""Searches the state space for the optimal path from the initial state to the goal state by selecting the node with
the lowest path value first."""
start = client.startCity
goal = client.goalCity
# Initialize open list, closed list and path value, which can be either cost or time
open_list = PriorityQueue()
open_list.add(start, 0)
closed_list = {}
current_best_value = {}
# Note: closed list contains nodes and means of transportation used to get to the nodes
closed_list[start] = (None, None)
current_best_value[start] = 0
# Initialize total time and cost. Note that one of these is a duplicate of path value, depending on whether the
# optimization criterion is time or cost
totalTime = {}
totalTime[start] = 0
totalCost = {}
totalCost[start] = 0
# Run algorithm until no more nodes left to explore (i.e. until open list is empty)
while not open_list.empty():
# Get next node in priority queue and remove from the queue
current = open_list.pop()
# Check if current node is goal node
if current == goal:
return get_path(current, start, closed_list), totalTime[current] - client.timeAvailable, totalCost[current]
# Let client expand current node according to specified constraints
successors = client.expandNode(current, totalTime[current], graph, ifHeuristics)
# Loop through successors to find the best next node
for successor in successors:
# Compute path value (g value) from start to successor of current, via current
new_value = current_best_value[current] + successor.value
# Compute total time and cost for successor
tmpTotalTime = totalTime[current] + successor.time
tmpTotalCost = totalCost[current] + successor.cost
# Discard if total time or total cost exceeds constraints
if tmpTotalTime - client.timeAvailable > client.maxTotalTime or tmpTotalCost > client.maxTotalCost:
continue
# If successor node not visited yet or if the new path value is better than the previously obtained value,
# set or update the current best value for that node
elif successor.cityNo not in current_best_value or new_value < current_best_value[successor.cityNo]:
current_best_value[successor.cityNo] = new_value
# Set priority equal to the path value g(n)
priority = new_value
# Add successor to open list with specified priority
open_list.add(successor.cityNo, priority)
# Add the current node to the closed list. Note that it was already removed from the open list
closed_list[successor.cityNo] = (current, successor.vehicle)
# Store total time and cost for successor node
totalTime[successor.cityNo] = tmpTotalTime
totalCost[successor.cityNo] = tmpTotalCost
# Return -1 if no path was found
return -1
# Informed search algorithm
def a_star(client, graph):
"""Searches the state space for the optimal path from the initial state to the goal state, minimizing the value
function f(n) = g(n) + h(n), where g(n) is the value from the initial node to the current node n and h(n) is the
estimated value to reach the goal state from the current node, i.e. the heuristic value."""
if heuristic(client, graph) == -1:
return -1
start = client.startCity
goal = client.goalCity
# Initialize open list, closed list and path value (estimate)
open_list = PriorityQueue()
open_list.add(start, 0)
closed_list = {}
current_best_value = {}
# Note: closed list contains nodes and means of transportation used to get to the nodes
closed_list[start] = (None, None)
current_best_value[start] = 0
# Initialize total time and cost. Note that one of these is a duplicate of path value, depending on whether the
# optimization criterion is time or cost
totalTime = {}
totalTime[start] = 0
totalCost = {}
totalCost[start] = 0
# Run algorithm until no more nodes left to explore (i.e. until open list is empty)
while not open_list.empty():
# Get next node in priority queue and remove from the queue
current = open_list.pop()
# Check if current node is goal node
if current == goal:
return get_path(current, start, closed_list), totalTime[current] - client.timeAvailable, totalCost[current]
# Let client expand current node according to specified constraints
successors = client.expandNode(current, totalTime[current], graph)
# Loop through successors to find the best next node
for successor in successors:
# Compute path value (g value) from start to successor of current, via current
new_value = current_best_value[current] + successor.value
# Compute total time and cost for successor
tmpTotalTime = totalTime[current] + successor.time
tmpTotalCost = totalCost[current] + successor.cost
# Discard if total time or total cost exceeds constraints
if tmpTotalTime - client.timeAvailable > client.maxTotalTime or tmpTotalCost > client.maxTotalCost:
continue
# If successor node not visited yet or if the new path value is better than the previously obtained value,
# set or update the current best value for that node
elif successor.cityNo not in current_best_value or new_value < current_best_value[successor.cityNo]:
current_best_value[successor.cityNo] = new_value
# Set priority equal to value function f(n) = g(n) + h(n)
priority = new_value + heuristic(client, graph)
# Add successor to open list with specified priority
open_list.add(successor.cityNo, priority)
# Add the current node to the closed list. Note that it was already removed from the open list
closed_list[successor.cityNo] = (current, successor.vehicle)
# Compute and store total time and cost for successor node
totalTime[successor.cityNo] = tmpTotalTime
totalCost[successor.cityNo] = tmpTotalCost
# Return -1 if no path was found
return -1