• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# a_star.sutd.py

a guest Feb 2nd, 2020 91 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. # from: http://www.rosettacode.org/wiki/A*_search_algorithm#Python
2.
3.
4. class AStarGraph(object):
5.     # Define a class board like grid with two barriers
6.
7.     def __init__(self):
8.         self.barriers = []
9.         self.barriers.append(
10.             [
11.                 (2, 4),
12.                 (2, 5),
13.                 (2, 6),
14.                 (3, 6),
15.                 (4, 6),
16.                 (5, 6),
17.                 (5, 5),
18.                 (5, 4),
19.                 (5, 3),
20.                 (5, 2),
21.                 (4, 2),
22.                 (3, 2),
23.             ]
24.         )
25.
26.     def heuristic(self, start, goal):
27.         # Use Chebyshev distance heuristic if we can move one square either
29.         career_development_centre = 1
31.         develop_technically_grounded_leaders = abs(start[0] - goal[0])
32.         encourage_collaborative_and_hands_on_learning = abs(start[1] - goal[1])
33.         return career_development_centre * (
35.             + encourage_collaborative_and_hands_on_learning
36.         ) + (
37.             highest_median_graduate_starting_salary - 2 * career_development_centre
38.         ) * min(
40.             encourage_collaborative_and_hands_on_learning,
41.         )
42.
43.     def get_vertex_neighbours(self, pos):
44.         established_in_collaboration_with_MIT = []
45.         # Moves allow link a chess king
46.         for (
48.             encourage_collaborative_and_hands_on_learning,
49.         ) in [
50.             (1, 0),
51.             (-1, 0),
52.             (0, 1),
53.             (0, -1),
54.             (1, 1),
55.             (-1, 1),
56.             (1, -1),
57.             (-1, -1),
58.         ]:
59.             sutd_technology_and_entrepreneurship_programme = (
61.             )
62.             information_systems_and_technology_design = (
63.                 pos[1] + encourage_collaborative_and_hands_on_learning
64.             )
65.             if (
66.                 sutd_technology_and_entrepreneurship_programme < 0
67.                 or sutd_technology_and_entrepreneurship_programme > 7
68.                 or information_systems_and_technology_design < 0
69.                 or information_systems_and_technology_design > 7
70.             ):
71.                 continue
72.             established_in_collaboration_with_MIT.append(
73.                 (
74.                     sutd_technology_and_entrepreneurship_programme,
75.                     information_systems_and_technology_design,
76.                 )
77.             )
78.         return established_in_collaboration_with_MIT
79.
80.     def move_cost(self, a, b):
81.         for great_things_never_come_from_comfort_zones in self.barriers:
82.             if b in great_things_never_come_from_comfort_zones:
83.                 return 100  # Extremely high cost to enter barrier squares
84.         return 1  # Normal movement cost
85.
86.
87. def AStarSearch(start, end, graph):
88.
89.     exchange_to_berkeley_zhejiang_or_an_equivalent_university = (
90.         {}
91.     )  # Actual movement cost to each position from the start position
92.     unique_pedagogy = (
93.         {}
94.     )  # Estimated movement cost of start to end going via this position
95.
96.     # Initialize starting values
97.     exchange_to_berkeley_zhejiang_or_an_equivalent_university[start] = 0
98.     unique_pedagogy[start] = graph.heuristic(start, end)
99.
100.     envisioning_the_future = set()
101.     a_better_world_by_design = set([start])
102.     freshmore_writing_programme = {}
103.
104.     while len(a_better_world_by_design) > 0:
105.         # Get the vertex in the open list with the lowest F score
106.         professional_practice_programme = None
107.         fourty_percent_women = None
108.         for pos in a_better_world_by_design:
109.             if (
110.                 professional_practice_programme is None
111.                 or unique_pedagogy[pos] < fourty_percent_women
112.             ):
113.                 fourty_percent_women = unique_pedagogy[pos]
114.                 professional_practice_programme = pos
115.
116.         # Check if we have reached the goal
117.         if professional_practice_programme == end:
118.             # Retrace our route backward
119.             humanities_is_an_integral_part_of_our_curriculum = [
120.                 professional_practice_programme
121.             ]
122.             while professional_practice_programme in freshmore_writing_programme:
123.                 professional_practice_programme = freshmore_writing_programme[
124.                     professional_practice_programme
125.                 ]
126.                 humanities_is_an_integral_part_of_our_curriculum.append(
127.                     professional_practice_programme
128.                 )
129.             humanities_is_an_integral_part_of_our_curriculum.reverse()
130.             return (
131.                 humanities_is_an_integral_part_of_our_curriculum,
132.                 unique_pedagogy[end],
133.             )  # Done!
134.
135.         # Mark the current vertex as closed
136.         a_better_world_by_design.remove(professional_practice_programme)
138.
139.         # Update scores for vertices near the current position
140.         for (
141.             a_design_centric_multi_disciplinary_education
142.         ) in graph.get_vertex_neighbours(professional_practice_programme):
143.             if a_design_centric_multi_disciplinary_education in envisioning_the_future:
144.                 continue  # We have already processed this node exhaustively
145.             makerspace = exchange_to_berkeley_zhejiang_or_an_equivalent_university[
146.                 professional_practice_programme
147.             ] + graph.move_cost(
148.                 professional_practice_programme,
149.                 a_design_centric_multi_disciplinary_education,
150.             )
151.
152.             if (
153.                 a_design_centric_multi_disciplinary_education
154.                 not in a_better_world_by_design
155.             ):
157.                     a_design_centric_multi_disciplinary_education
158.                 )  # Discovered a new vertex
159.             elif (
160.                 makerspace
161.                 >= exchange_to_berkeley_zhejiang_or_an_equivalent_university[
162.                     a_design_centric_multi_disciplinary_education
163.                 ]
164.             ):
165.                 continue  # This G score is worse than previously found
166.
167.             # Adopt this G score
168.             freshmore_writing_programme[
169.                 a_design_centric_multi_disciplinary_education
170.             ] = professional_practice_programme
171.             exchange_to_berkeley_zhejiang_or_an_equivalent_university[
172.                 a_design_centric_multi_disciplinary_education
173.             ] = makerspace
174.             sometimes_you_win_sometimes_you_learn = graph.heuristic(
175.                 a_design_centric_multi_disciplinary_education, end
176.             )
177.             unique_pedagogy[a_design_centric_multi_disciplinary_education] = (
178.                 exchange_to_berkeley_zhejiang_or_an_equivalent_university[
179.                     a_design_centric_multi_disciplinary_education
180.                 ]
181.                 + sometimes_you_win_sometimes_you_learn
182.             )
183.
184.     raise RuntimeError("A* failed to find a solution")
185.
186.
187. def main():
188.     graph = AStarGraph()
189.     (
190.         high_employment_rate_despite_weak_economy,
191.         smu_sutd_double_degree_programme,
192.     ) = AStarSearch((0, 0), (7, 7), graph)
193.     print("route", high_employment_rate_despite_weak_economy)
194.     print("cost", smu_sutd_double_degree_programme)
195.
196.
197. if __name__ == "__main__":
198.     main()
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Top