team.py (5342B)
1 CAPACITY = 10 2 FLOORS_TOTAL = 5 #total number of FLOORS_TOTAL 3 4 #WORLD OF PROBLEM:elevator capacity, floors, residents 5 #CONSTRAINTS: 6 #1.The elevator has maximum capacity of 10 7 #2.The total number of FLOORS_TOTAL is 5 8 #3.In the beginning the elevator is empty in floor 0 9 #4.Each floor has a specific number of residents in the beginning 10 11 # function to point where the elevator goes next 12 def go_to_floor(state, floor): 13 # if the elevator position is less than its capacity and the elevator 14 # is not on the ground then the new state enters the list of states 15 if floor == 0: 16 new_state = list(state).copy() 17 new_state[0] = 0 18 new_state[FLOORS_TOTAL] = 0 19 return tuple(new_state) 20 if state[FLOORS_TOTAL] < CAPACITY and state[floor] > 0: 21 new_state = list(state).copy() 22 if state[floor] > CAPACITY - state[FLOORS_TOTAL]: 23 # we exclude the last floor 24 new_state[floor] = state[floor] + state[FLOORS_TOTAL] - CAPACITY 25 new_state[0] = floor 26 new_state[FLOORS_TOTAL] = CAPACITY 27 else: 28 new_state[floor] = 0 29 new_state[0] = floor 30 new_state[FLOORS_TOTAL] = state[floor] + state[FLOORS_TOTAL] 31 return tuple(new_state) 32 else: 33 return None 34 35 # state: ( elevator position={0,1,2,3,4}, floor1, floor2, floor3, floor4, elevator ) 36 # initial: ( 0, 12, 3, 7, 8, 0 ) 37 # final: ( 0, 0, 0, 0, 0, 0 ) 38 def bfs(initial_state, final_state): 39 visited = {} 40 frontier = [initial_state] 41 42 while len(frontier) > 0: 43 # print(frontier) 44 state = frontier.pop(0) 45 print(state) 46 # if the elevator has reached the final state all previously visited 47 # states are printed 48 if state == final_state: 49 print(f"\n\nBFS: states visited = {len(visited)}") 50 return final_state 51 visited[state] = 1 52 #the state must be immutable in order to become key to the dict 53 # print(state) 54 55 # anakalypsh paidiwn 56 current_floor = state[0] 57 current_capacity = state[-1] 58 59 if current_capacity == CAPACITY or current_floor == FLOORS_TOTAL - 1: 60 new_state = go_to_floor(state, 0) 61 #putting the new state to the frontier 62 if new_state not in visited: 63 frontier.append(new_state) 64 continue 65 66 return_to_0 = True 67 68 for floor in range(1, FLOORS_TOTAL): 69 # in case the elevator is over the ground and the floor 70 # (in frontier) is over the current position of the elevator go up 71 if floor <= current_floor: 72 continue 73 # in case the floor (in frontier) is not the last and the elevator 74 # position is on the ground go up 75 elif floor < FLOORS_TOTAL - 1 and state[floor] == 0: 76 continue 77 # in case the last floor is visited,the next floor in frontier is 4 and 78 # the elevator is not in 0 the new state is added to the list 79 elif (floor == FLOORS_TOTAL - 1 and state[FLOORS_TOTAL - 1] == 0 and current_floor != 0 and return_to_0): 80 new_state = go_to_floor(state, 0) 81 # in case the elevator carries less than 10 people and the next floor 82 # in frontier is over the current floor the elevator goes up 83 elif current_capacity < CAPACITY and floor > current_floor: 84 return_to_0 = False 85 new_state = go_to_floor(state, floor) 86 if new_state is None: 87 continue 88 # in case there is no new state continue 89 else: 90 continue 91 92 # BFS: bazw paidia (new states) sto TELOS tou frontier 93 if new_state not in visited: 94 frontier.append(new_state) 95 return None 96 97 def heuristic(state): 98 return sum(state) 99 100 def bestfs(initial_state, final_state): 101 visited = {} 102 state = initial_state 103 104 while state != final_state: 105 print(state) 106 # initialize available states 107 avail_states = [] 108 current_floor = state[0] 109 current_capacity = state[-1] 110 111 # test all states 112 for floor in range(1, FLOORS_TOTAL): 113 if floor == current_floor: 114 continue 115 new_state = go_to_floor(state, floor) 116 if new_state == None: 117 continue 118 # only add states not already visited 119 if new_state not in visited: 120 avail_states.append(new_state) 121 # mark state as visited 122 visited[new_state] = 1 123 124 # sort combinations according to heuristic value 125 avail_states.sort(key=heuristic) 126 127 if avail_states: 128 # get best path 129 state = avail_states.pop(0) 130 avail_states.clear() 131 132 if current_capacity == CAPACITY or current_floor == FLOORS_TOTAL - 1: 133 state = go_to_floor(state, 0) 134 135 print(f"\n\nBestFS: states visited: {len(visited)}") 136 return final_state 137 138 def main(): 139 initial = (0, 12, 3, 7, 8, 0) 140 final = (0, 0, 0, 0, 0, 0) 141 method = "BestFS" 142 143 if method == "BFS": 144 state = bfs(initial, final) 145 elif method == "BestFS": 146 state = bestfs(initial, final) 147 print(state) 148 149 if __name__ == "__main__": 150 main()