# ====== Implementasi A* di Grid ======
import math, heapq, time, random
import networkx as nx
import matplotlib.pyplot as plt

# 1. Bangun graf grid
W, H = 10, 8
start, goal = (0,0), (H-1,W-1)
G = nx.grid_2d_graph(H, W)

random.seed(5)
remove_ratio = 0.18
edges = list(G.edges())
random.shuffle(edges)
for e in edges[:int(len(edges)*remove_ratio)]:
    G.remove_edge(*e)

# Pastikan tetap terhubung
if not nx.has_path(G, start, goal):
    for e in edges[int(len(edges)*remove_ratio)//2:]:
        G.add_edge(*e)
        if nx.has_path(G, start, goal):
            break

# 2. Definisi heuristik

def manhattan(a,b):
    (x1,y1),(x2,y2)=a,b
    return abs(x1-x2)+abs(y1-y2)

def euclidean(a,b):
    (x1,y1),(x2,y2)=a,b
    return math.sqrt((x1-x2)**2+(y1-y2)**2)

# 3. Algoritma A*

def astar(G, start, goal, h):
    pq = [(0,start)] # (f,node)
    parent={start:None}
    g_cost={start:0}
    expanded=0
    t0=time.perf_counter()

    while pq:
        f,u = heapq.heappop(pq)
        expanded += 1
        if u==goal:
            dt=time.perf_counter()-t0
            return u,parent,g_cost,expanded,dt
        for v in G.neighbors(u):
            ng=g_cost[u]+1  # biaya 1 per langkah
            if v not in g_cost or ng<g_cost[v]:
                g_cost[v]=ng
                f=ng+h(v,goal)
                heapq.heappush(pq,(f,v))
                parent[v]=u
    return None,parent,g_cost,expanded,time.perf_counter()-t0


def reconstruct(parent, goal):
    path=[]; cur=goal
    while cur is not None:
        path.append(cur)
        cur=parent.get(cur)
    return list(reversed(path))

# 4. Jalankan A* dengan dua heuristik
node_m,parent_m,g_cost_m,exp_m,tm = astar(G,start,goal,manhattan)
node_e,parent_e,g_cost_e,exp_e,te = astar(G,start,goal,euclidean)

path_m=reconstruct(parent_m,goal)
path_e=reconstruct(parent_e,goal)

print(f"Manhattan: expanded={exp_m}, waktu={tm:.5f}s, panjang={len(path_m)-1}")
print(f"Euclidean: expanded={exp_e}, waktu={te:.5f}s, panjang={len(path_e)-1}")

# 5. Visualisasi
pos={(r,c):(c,-r) for r,c in G.nodes()}
plt.figure(figsize=(6,4))
nx.draw(G,pos,node_size=60,width=1,with_labels=False)
nx.draw_networkx_nodes(G,pos,nodelist=path_m,node_size=80)
nx.draw_networkx_edges(G,pos,edgelist=list(zip(path_m,path_m[1:])),width=3)
plt.title('A* dengan heuristik Manhattan')
plt.show()

plt.figure(figsize=(6,4))
nx.draw(G,pos,node_size=60,width=1,with_labels=False)
nx.draw_networkx_nodes(G,pos,nodelist=path_e,node_size=80)
nx.draw_networkx_edges(G,pos,edgelist=list(zip(path_e,path_e[1:])),width=3)
plt.title('A* dengan heuristik Euclidean')
plt.show()

Catatan: Ubah W,H,remove_ratio,seed untuk melihat dampak pada jumlah node dieksplorasi & waktu.

# ====== Perbandingan dengan UCS (biaya seragam) ======
import heapq, time, math

# UCS (Uniform-Cost Search) dengan biaya 1 per edge

def ucs(G, start, goal, cost=lambda u,v:1):
    pq=[(0,start)]  # (g,node)
    best={start:0}
    parent={start:None}
    expanded=0
    t0=time.perf_counter()
    while pq:
        g,u = heapq.heappop(pq)
        expanded+=1
        if u==goal:
            dt=time.perf_counter()-t0
            return u,parent,best,expanded,dt
        for v in G.neighbors(u):
            ng=g+cost(u,v)
            if v not in best or ng<best[v]:
                best[v]=ng
                parent[v]=u
                heapq.heappush(pq,(ng,v))
    return None,parent,best,expanded,time.perf_counter()-t0

node_u,parent_u,g_u,exp_u,tu = ucs(G,start,goal)

# Rekonstruksi path

def reconstruct(parent, goal):
    path=[]; cur=goal
    while cur is not None:
        path.append(cur)
        cur=parent.get(cur)
    return list(reversed(path))

path_u = reconstruct(parent_u, goal)

print(f"UCS : expanded={exp_u}, waktu={tu:.5f}s, panjang={len(path_u)-1}")

# Catatan: Pada graf tak berbobot, UCS setara shortest path. Bandingkan nilai expanded/waktu dengan A* di atas.

# ====== Kuis 4 (cek mandiri) ======
qs=[
  ("Fungsi evaluasi A* adalah...",{"a":"f(n)=g(n)*h(n)","b":"f(n)=g(n)+h(n)","c":"f(n)=h(n)-g(n)","d":"f(n)=g(n)/h(n)"},"b"),
  ("Heuristik disebut admissible jika...",{"a":"Tidak melebih-lebihkan biaya sebenarnya ke goal","b":"Selalu nol","c":"Tidak tergantung tujuan","d":"Melebihkan jarak agar cepat"},"a"),
  ("Heuristik konsisten berarti...",{"a":"h(n) ≤ c(n,m) + h(m) untuk setiap edge (n,m)","b":"h=0 selalu","c":"h(n) ≥ h(m)","d":"h(n) tidak bergantung graf"},"a"),
]
print('Kunci jawaban:')
for i,(_,__,ans) in enumerate(qs,1):
    print(f'Q{i}: {ans}')