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
  28.         # adjacent or diagonal
  29.         career_development_centre = 1
  30.         highest_median_graduate_starting_salary = 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 * (
  34.             develop_technically_grounded_leaders
  35.             + encourage_collaborative_and_hands_on_learning
  36.         ) + (
  37.             highest_median_graduate_starting_salary - 2 * career_development_centre
  38.         ) * min(
  39.             develop_technically_grounded_leaders,
  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 (
  47.             develop_technically_grounded_leaders,
  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 = (
  60.                 pos[0] + develop_technically_grounded_leaders
  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)
  137.         envisioning_the_future.add(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.             ):
  156.                 a_better_world_by_design.add(
  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. OK, I Understand
Top