Project: Lesson Graph ပေါ်က Pathfinding

နားလည်ထားရမယ့် အချက်

Related-lessons data က သဘာဝအရ graph တစ်ခု ဖြစ်တယ်: lesson တစ်ခုစီက node ဖြစ်ပြီး၊ lesson တစ်ခုကနေ တခြားတစ်ခုဆီ edge ရှိတယ်ဆိုရင် 'ဒါက ဒီကို သဘာဝအရ ဆက်နွှယ်တယ်' လို့ ဆိုလိုတယ်၊ difficulty jump ဒါမှမဟုတ် estimated time နဲ့ weight ချိန်လို့ရတယ်။ learner ရဲ့ လက်ရှိ lesson ကနေ goal ဆီ အကောင်းဆုံးလမ်းကြောင်း ရှာတာက shortest-path problem တစ်ခုပါပဲ၊ Dijkstra's algorithm က မှန်ကန်တဲ့ tool ဖြစ်တာက edge weight တွေက negative မဖြစ်နိုင်လို့ (lesson transition တစ်ခုမှာ 'negative cost' ဆိုတာ ဘယ်တော့မှ မရှိဘူး) ပြီးတော့ minimum-cost path စစ်စစ်ကို လိုချင်တာကြောင့်ပါ၊ path ဟာသလောက် မလိုချင်ဘူး။ naive alternative ဖြစ်တဲ့ plain breadth-first search ကတော့ edge weight အားလုံး တူညီမှသာ အလုပ်လုပ်တယ်၊ lesson cost တွေ ကွဲပြားလာတာနဲ့ (conceptual leap ကြီးတစ်ခုက refinement သေးသေးလေးထက် cost ပိုများတယ်) BFS ရဲ့ 'edge အနည်းဆုံး' ဆိုတဲ့ အဖြေက hop နည်းပေမယ့် real cost ပိုများတဲ့ path ကို ရွေးမိလို့ မှားသွားနိုင်တယ်။ Dijkstra က frontier node ထဲက total cost အနည်းဆုံးကို priority queue (`heapq`) သုံးပြီး အမြဲဦးဆုံး expand လုပ်ခြင်းနဲ့ ဒါကို ဖြေရှင်းတယ်၊ settled node တွေကို ပြန်စစ်ဖို့ မလိုတော့ဘဲ O((V+E) log V) မှာ weighted shortest path အမှန်ကို ပေးနိုင်တယ်။

လက်တွေ့ scenario နဲ့ ချိတ်ကြည့်မယ်

ဒါက real 'recommended learning path' feature တစ်ခုကို model လုပ်တာပါ: Python intro lesson ပြီးသွားတဲ့ learner တစ်ယောက်က 'Building REST APIs' ဆီ ရောက်ချင်နေတယ်ဆိုရင်၊ platform က catalog တစ်ခုလုံးကို ပစ်ပေးတာ ဒါမှမဟုတ် random order နဲ့ list ချတာအစား ဒီနှစ်ခုကို ဆက်နွှယ်ပေးတဲ့ prerequisite lesson အတိုဆုံး sequence ကို အကြံပြုပေးရမယ်။ edge weight တစ်ခုစီက estimated minutes-to-complete ဒါမှမဟုတ် difficulty delta ကို ကိုယ်စားပြုနိုင်တယ်၊ ဒါကြောင့် shortest path က click အနည်းဆုံးမက curriculum ကို ဖြတ်တဲ့ အမြန်ဆုံး ယုတ္တိကျတဲ့ လမ်းကြောင်း တကယ့်ကို ဖြစ်တယ်။ graph တစ်ခုတည်းကိုပဲ site ရဲ့ per-tutorial chapter structure က implied လုပ်ထားတဲ့ 'Related Lessons' sidebar အတွက်လည်း သုံးလို့ရတယ်၊ လက်ရှိ ဖွင့်ထားတဲ့ lesson ကနေ path cost အလိုက် suggestion တွေကို rank လုပ်ပေးနိုင်တယ်။

• Related-lessons ကို weighted graph အနေနဲ့ model လုပ်တယ် — node တွေက lesson, weighted edge တွေက transition cost
• Dijkstra က edge weight non-negative မို့ frontier ကို priority queue နဲ့ lowest-cost order အတိုင်း expand လုပ်တယ်
• BFS က edge weight အားလုံး တူညီမှသာ shortest path မှန်တယ် — weighted graph မှာ BFS သုံးရင် ရလဒ် မှားနိုင်တယ်

အတူတူ စမ်းရေးကြည့်မယ်

import heapq

def shortest_path(graph, start, goal):
    """graph: {node: [(neighbor, cost), ...]}. Returns (path, total_cost)."""
    # (cumulative_cost, node, path_so_far)
    frontier = [(0, start, [start])]
    visited = set()

    while frontier:
        cost, node, path = heapq.heappop(frontier)  # always pop lowest cost
        if node == goal:
            return path, cost
        if node in visited:
            continue
        visited.add(node)

        for neighbor, edge_cost in graph.get(node, []):
            if neighbor not in visited:
                heapq.heappush(frontier, (cost + edge_cost, neighbor, path + [neighbor]))

    return None, float("inf")  # goal unreachable

# Small "related lessons" graph: edge weight = estimated extra minutes needed
lesson_graph = {
    "python-basics": [("python-functions", 10), ("python-oop", 25)],
    "python-functions": [("python-oop", 12), ("python-decorators", 15)],
    "python-oop": [("rest-apis", 20)],
    "python-decorators": [("rest-apis", 8)],
    "rest-apis": [],
}

path, cost = shortest_path(lesson_graph, "python-basics", "rest-apis")
print("Path:", " -> ".join(path))
print("Total estimated minutes:", cost)

`Path: python-basics -> python-functions -> python-decorators -> rest-apis` နဲ့ `Total estimated minutes: 33` ကို print ထုတ်တယ် — `python-oop` ကို ဖြတ်တဲ့ ပိုကုန်ကျတဲ့ လမ်းကြောင်းထက် ဒါက ပိုသက်သာတယ်။

Wikipedia — A* search algorithm — Data Structures & Algorithms