mbah_bejo

Astar

Apr 18th, 2021 (edited)
474
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. def aSiap(start_node, goal_node):
  2.     open_set = set(start_node) # berisi node terbuka artinya node yang masih dipakai
  3.     closed_set = set() # berisi node tertutup, artinya udah dilewati
  4.     g = {} # menyimpan jarak tempuh dari node start
  5.     parents = {} # menyimpan posisi parent yang sedang digunakan
  6.  
  7.     # jarak awal dari node start dimulai dari nol
  8.     g[start_node] = 0
  9.     # node start pasti menjadi root, karena tak punya parent
  10.     # maka node start menjadi parent node sebagai awalan
  11.     parents[start_node] = start_node
  12.  
  13.     # program berjalan selama open_set memiliki isi / mencapai node goal
  14.     while len(open_set) > 0:
  15.         n = None # set n ke None
  16.  
  17.         # mencari node dengan f(node) terkecil
  18.         for v in open_set:
  19.             # membandingan f(node) child yang ada (belum di-close)
  20.             if n == None or g[v] + heuristic(v) < g[n] + heuristic(n):
  21.                 n=v #menyimpan node dengan f(node) terkecil ke n
  22.                 print('Choosen:', v, '; f({}):'.format(v), g[v], '+', heuristic(v), '=', g[v] + heuristic(v), '\n')
  23.  
  24.         # jika n merupakan node goal atau node tersebut buntu, maka pass
  25.         if n == goal_node or Graph_nodes[n] == None:
  26.             pass
  27.         else:
  28.             for(m, jarak) in get_child(n):
  29.                 # n merupakan parent sekarang
  30.                 # jika m berupa node yg belum ada di open_set / closed_set,
  31.                 # m dimasukkan ke open_set dan menyimpan jarak yang ditempuh
  32.                 if m not in open_set and m not in closed_set:
  33.                     open_set.add(m) # memasukkan m ke node terbuka
  34.                     parents[m] = n # maka parent dari m adalah n
  35.                     print('parent:', parents[m])
  36.                     g[m] = g[n] + jarak # menyimpan jarak
  37.                     print('Visited:', m, '; Jarak sekarang:', g[m])
  38.  
  39.                 # membandingkan jarak node m dari g(start) hingga g(n)
  40.                 else:
  41.                     if g[m] > g[n] + jarak:
  42.                         # update g[m]
  43.                         g[m] = g[n] + jarak
  44.                         # mengganti parent dari m dengan node n
  45.                         parents[m] = n
  46.  
  47.                         # jika node m ada di closed_set,
  48.                         # maka hapus dan tambahkan ke open_set
  49.                         if m in closed_set:
  50.                             closed_set.remove(m)
  51.                             open_set.add(m)
  52.  
  53.         # jika n merupakan node kosong
  54.         if n == None:
  55.             print('Jalan tidak ada!')
  56.             return None
  57.  
  58.         # jika node sekarang adalah goal_node
  59.         # maka mulai menyusun jalan dari start ke goal
  60.         if n == goal_node:
  61.             solusi = []
  62.  
  63.             print("menyusun path:")
  64.             # melakukan traceback untuk menyusun path
  65.             while parents[n] != n:
  66.                 solusi.append(n)
  67.                 print(solusi)
  68.                 n = parents[n]
  69.             solusi.append(start_node)
  70.             solusi.reverse()
  71.  
  72.             print('Solusi ditemukan: {}'.format(solusi))
  73.             return solusi
  74.  
  75.  
  76.         # menghapus n dari open_set dan memasukkan ke closed_set
  77.         # karena semua child dari n telah diperiksa
  78.         open_set.remove(n)
  79.         closed_set.add(n)
  80.         print('calon path:',closed_set)
  81.  
  82.  
  83.     print('Solusi tidak ada!')
  84.     return None
  85.  
  86. # fungsi untuk me-return child dan jaraknya dari posisi parent yang sekarang
  87. def get_child(v):
  88.     if v in Graph_nodes:
  89.         return Graph_nodes[v]
  90.     else:
  91.         return None
  92.  
  93. def heuristic(n):
  94.     H_dist = {
  95.         'S': 11,
  96.         'A': 10.4,
  97.         'B': 6.7,
  98.         'C': 4,
  99.         'D': 8.9,
  100.         'E': 6.9,
  101.         'F': 3,
  102.         'G': 0
  103.     }
  104.     return H_dist[n]
  105.  
  106. # Graph dari setiap node dan jarak
  107. Graph_nodes = {
  108.     'S': [('A', 3), ('D', 4)],
  109.     'A': [('B', 4), ('D', 5)],
  110.     'B': [('C', 4), ('E', 5)],
  111.     'C': None,
  112.     'D': [('A',5),('E', 2)],
  113.     'E': [('B',5),('F', 4)],
  114.     'F': [('G', 3)]
  115. }
  116.  
  117. if __name__ == "__main__": aSiap('S', 'G')
RAW Paste Data