3 Missionaries and 3 Cannibals

 

နည်းသစ်ဉာဏ်ရည်တုပညာမိတ်ဆက်၊ အခန်း (၃)၊ စာမျက်နှာ-၁၅၀, Problem 3.7 နှင့်
စာ-၄၅၉၊ အသေးစားဉာဏ်ရည်တုပရိုဂရမ် (၁) 3 Missionaries and 3 Cannibals
ကိုကြည့်ပါ။

ဒီပြဿနာကို ဖြေရှင်းဖို့အတွက် Python ဘာသာစကားကို အသုံးပြုပြီး၊ AI သဘောတရားများဖြစ်တဲ့ Search Problem Formulation အတိုင်း စနစ်တကျ တည်ဆောက်ပြပါမယ်။ အခြေခံ BFS (Breadth-First Search) အပြင်၊ ဖြေရှင်းနည်း (Solution Path) ကို ပြန်လည် ဖော်ထုတ်တဲ့ Backtracking စနစ်ကိုပါ ထည့်သွင်းရေးသားပေးပါမယ်။

---

၁။ ပြဿနာကို ပုံဖေါ်ခြင်း (Problem Formulation)

ကုဒ်မရေးခင် AI အတွက် လိုအပ်တဲ့ အစိတ်အပိုင်းတွေကို အရင်ဆုံး သတ်မှတ်ကြရအောင်။

• State Representation (အခြေအနေ ဖော်ပြချက်): အခြေအနေတစ်ခုကို (m_left, c_left, boat_pos) ပုံစံ Tuple ဖြင့် မှတ်သားပါမယ်။

  • m_left: ဘယ်ဖက်ကမ်းမှာ ရှိတဲ့ Missionary အရေအတွက်။

  • c_left: ဘယ်ဖက်ကမ်းမှာ ရှိတဲ့ Cannibal အရေအတွက်။

  • boat_pos: လှေရှိနေတဲ့နေရာ (0 = ဘယ်ဖက်ကမ်း၊ 1 = ညာဖက်ကမ်း)။

  • (ညာဖက်ကမ်းက လူအရေအတွက်ကို တွက်ချင်ရင် စုစုပေါင်း ၃ ယောက်ထဲက ဘယ်ဖက်ကမ်းအရေအတွက်ကို နှုတ်လိုက်ရုံပါပဲ)

• Initial State (စ ဦး အခြေအနေ): (3, 3, 0) -> Missionary ၃၊ Cannibal ၃၊ လှေက ဘယ်ဖက်ကမ်း (0) မှာ ရှိနေသည်။

• Goal State (ပန်းတိုင် အခြေအနေ): (0, 0, 1) -> Missionary ၀၊ Cannibal ၀ (အားလုံး ညာဖက်ရောက်ကုန်ပြီ)၊ လှေက ညာဖက်ကမ်း (1) မှာ ရောက်နေသည်။

• Actions (ပြုလုပ်နိုင်သော အရာများ): လှေပေါ်တွင် လူ ၁ ဦး သို့မဟုတ် ၂ ဦး လိုက်နိုင်သည်။ ဖြစ်နိုင်သော လှေရွှေ့ပြောင်းမှုများ (Missionary, Cannibal) = (1, 0), (2, 0), (0, 1), (0, 2), (1, 1)

• Constraints (စည်းကမ်းချက်များ): ကမ်းနှစ်ဖက်စလုံးတွင် မည်သည့်အချိန်၌မဆို Cannibal အရေအတွက်သည် Missionary အရေအတွက်ထက် မများရပါ (Missionary > 0 ဖြစ်လျှင်)။

• Search Strategy: အဖြေအမြန်ဆုံး ရှာတွေ့နိုင်မည့် Breadth-First Search (BFS) ကို အသုံးပြုပါမယ်။

---

၂။ Python Program (AI Solution)

အောက်ပါ Python ကုဒ်ကို Object-Oriented ပုံစံဖြင့် ရေးသားထားပြီး AIMA ပါ ဖွဲ့စည်းပုံအတိုင်း တည်ဆောက်ထားပါတယ်။

Python

import collections

# ---------------------------------------------------------
# အပိုင်း (၁) - ပြဿနာ၏ အခြေအနေနှင့် စည်းမျဉ်းများကို သတ်မှတ်ခြင်း
# ---------------------------------------------------------

class MCState:
    def __init__(self, m_left, c_left, boat_pos):
        self.m_left = m_left        # ဘယ်ဖက်ကမ်းမှ Missionary
        self.c_left = c_left        # ဘယ်ဖက်ကမ်းမှ Cannibal
        self.boat = boat_pos        # 0 = Left Bank, 1 = Right Bank
        self.parent = None          # အဖြေပြန်ထုတ်ရန် လမ်းကြောင်း (Parent node)
        self.action = None          # ဒီအခြေအနေရောက်အောင် ဘာလုပ်ခဲ့လဲ (Action)

    def is_valid(self):
        """
        စည်းကမ်းချက်များနှင့် ကိုက်ညီမှု ရှိမရှိ စစ်ဆေးခြင်း
        (Missionaries တွေကို Cannibals တွေက မစားမိအောင် ကာကွယ်ခြင်း)
        """
        # ၁။ လူအရေအတွက်သည် ၀ အောက်မငယ်ရ၊ ၃ ထက် မများရ
        if self.m_left < 0 or self.c_left < 0 or self.m_left > 3 or self.c_left > 3:
            return False

        # ညာဖက်ကမ်းရှိ လူအရေအတွက်ကို တွက်ချက်ခြင်း
        m_right = 3 - self.m_left
        c_right = 3 - self.c_left

        # ၂။ ဘယ်ဖက်ကမ်း စစ်ဆေးခြင်း (Missionary ရှိမှသာ Cannibal ထက်များလား စစ်မယ်)
        if self.m_left > 0 and self.c_left > self.m_left:
            return False

        # ၃။ ညာဖက်ကမ်း စစ်ဆေးခြင်း
        if m_right > 0 and c_right > m_right:
            return False

        return True

    def is_goal(self):
        """ပန်းတိုင် (0, 0, 1) ရောက်မရောက် စစ်ဆေးခြင်း"""
        return self.m_left == 0 and self.c_left == 0 and self.boat == 1

    def __eq__(self, other):
        """Object နှိုင်းယှဉ်မှုအတွက်"""
        return (self.m_left, self.c_left, self.boat) == (other.m_left, other.c_left, other.boat)

    def __hash__(self):
        """Repeated States များကို ဖယ်ရှားရန် Set ထဲထည့်ရာတွင် သုံးသည်"""
        return hash((self.m_left, self.c_left, self.boat))

    def get_successors(self):
        """
        Successor Function / Transition Model:
        လက်ရှိအခြေအနေမှ သွားနိုင်သော နောက်ထပ် အခြေအနေများကို ရှာဖွေခြင်း
        """
        successors = []
        # လှေပေါ်ပါသွားနိုင်သော ပေါင်းစပ်မှုများ (Missionary, Cannibal)
        moves = [(1, 0), (2, 0), (0, 1), (0, 2), (1, 1)]

        # အကယ်၍ လှေက ဘယ်ဖက်(0) မှာ ရှိရင် -> ညာဖက်ကို သွားမယ် (လူနှုတ်မယ်)
        if self.boat == 0:
            direction = -1
            new_boat_pos = 1
            action_name = "Cross from Left to Right"
        # အကယ်၍ လှေက ညာဖက်(1) မှာ ရှိရင် -> ဘယ်ဖက်ကို ပြန်လာမယ် (လူပေါင်းမယ်)
        else:
            direction = 1
            new_boat_pos = 0
            action_name = "Return from Right to Left"

        for m, c in moves:
            # လှေသွားမည့် အရပ်ကို လိုက်ပြီး လူအရေအတွက် ပြောင်းလဲခြင်း
            new_m = self.m_left + (direction * m)
            new_c = self.c_left + (direction * c)

            new_state = MCState(new_m, new_c, new_boat_pos)
            new_state.parent = self  # ဘယ်ကလာလဲ မှတ်ထားမယ် (For Backtracking)
            new_state.action = f"{action_name} with {m}M, {c}C"

            # Valid ဖြစ်မှသာ List ထဲ ထည့်မယ်
            if new_state.is_valid():
                successors.append(new_state)

        return successors

# ---------------------------------------------------------
# အပိုင်း (၂) - ရှာဖွေရေး အယ်လဂိုရီသမ် (BFS - Breadth-First Search)
# ---------------------------------------------------------

def solve_missionaries_cannibals():
    # ၁။ Initial State (စဦး အခြေအနေ) သတ်မှတ်
    initial_state = MCState(3, 3, 0)
    
    # ၂။ Goal check (ကံကောင်းထောက်မစွာ စဖွင့်ဖွင့်ချင်း ပြီးနေလား စစ်)
    if initial_state.is_goal():
        return initial_state

    # ၃။ Frontier (ရှာဖွေရန် စောင့်ဆိုင်းနေသော တန်းစီဇယား - Queue)
    # BFS ဖြစ်တဲ့အတွက် FIFO (First-In-First-Out) Queue ကို သုံးပါတယ်
    frontier = collections.deque([initial_state])

    # ၄။ Explored Set (Avoiding Repeated States)
    # ရှာဖွေပြီးသား အခြေအနေတွေကို ထပ်မရှာမိအောင် မှတ်သားထားခြင်း
    explored = set()
    explored.add(initial_state)

    while frontier:
        # Queue ရှေ့ဆုံးမှ အခြေအနေတစ်ခုကို ထုတ်ယူခြင်း
        current_state = frontier.popleft()

        # Successor Function ဖြင့် နောက်ဆက်တွဲများကို ရှာခြင်း
        children = current_state.get_successors()

        for child in children:
            # အကယ်၍ child က မရောက်ဖူးသေးရင်
            if child not in explored:
                # ပန်းတိုင်ရောက်ပြီလား စစ်ဆေး (Goal Test)
                if child.is_goal():
                    return child # အဖြေတွေ့ပြီ
                
                # မရောက်သေးရင် Queue ထဲထည့်၊ မှတ်တမ်းတင်
                frontier.append(child)
                explored.add(child)
    
    return None # အဖြေရှာမတွေ့ပါ

# ---------------------------------------------------------
# အပိုင်း (၃) - အဖြေထုတ်ပြခြင်း (Solution Reconstruction)
# ---------------------------------------------------------

def print_solution(solution_node):
    if not solution_node:
        print("No solution found!")
        return

    # နောက်ဆုံး node ကနေ အစ node ကို ပြန်ကောက် (Backtracking)
    path = []
    current = solution_node
    while current:
        path.append(current)
        current = current.parent
    
    # ပြောင်းပြန်လှန်လိုက်မှ အစ -> အဆုံး ဖြစ်မည်
    path.reverse()

    print(f"{'Step':<5} | {'Left Bank (M,C)':<15} | {'Boat':<10} | {'Right Bank (M,C)':<15} | {'Action'}")
    print("-" * 75)

    for i, state in enumerate(path):
        boat_loc = "LEFT" if state.boat == 0 else "RIGHT"
        
        # ညာဖက်ကမ်း လူအရေအတွက် တွက်ခြင်း
        m_right = 3 - state.m_left
        c_right = 3 - state.c_left
        
        action = state.action if state.action else "Start"
        
        print(f"{i:<5} | {state.m_left}M, {state.c_left}C {' ':<8} | {boat_loc:<10} | {m_right}M, {c_right}C {' ':<8} | {action}")

# ---------------------------------------------------------
# Main Execution
# ---------------------------------------------------------

if __name__ == "__main__":
    print("Missionaries and Cannibals Problem Solver (using AI BFS)")
    print("=======================================================\n")
    
    solution = solve_missionaries_cannibals()
    print_solution(solution)

---

၃။ AI သဘောတရား ရှင်းလင်းချက်များ

ဒီပရိုဂရမ်မှာ အသုံးပြုထားတဲ့ အဓိက သဘောတရားတွေကို အသေးစိတ် ပြန်လည်ရှင်းပြလိုပါတယ်။

၁. State Representation (အခြေအနေ ဖော်ပြချက်)

ကွန်ပျူတာ နားလည်စေဖို့ တကယ့်ကမ္ဘာ့ပြဿနာကို Data အဖြစ်ပြောင်းရာမှာ (M, C, B) ဆိုတဲ့ ကိန်းဂဏန်း ၃ လုံးကို သုံးထားပါတယ်။ ဒါက အရှင်းဆုံးနဲ့ အထိရောက်ဆုံး နည်းလမ်းဖြစ်ပါတယ်။

၂. Successor Function (Transition Model)

get_successors function ဟာ လက်ရှိအခြေအနေကနေ ဖြစ်နိုင်တဲ့ အခြေအနေအားလုံးကို ဖြန့်ထွက်ရှာဖွေပေးပါတယ်။ ဒီနေရာမှာ အရေးကြီးတာက is_valid function ပါ။ ဥပဒေ/စည်းမျဉ်း/ကန့်သတ်ချက် (Constraints) နဲ့ မညီတဲ့ အခြေအနေတွေ (ဥပမာ- လူစားခံရမယ့် အခြေအနေ) ကို ဒီအဆင့်မှာကတည်းက စစ်ဆေးပြီး ဖယ်ထုတ်လိုက်တာကြောင့် မလိုအပ်တဲ့ လမ်းကြောင်းတွေကို ဆက်မသွားတော့ပါဘူး။

၃. Breadth-First Search (BFS)

ဒီပြဿနာအတွက် BFS ကို ရွေးချယ်ရတဲ့ အကြောင်းရင်းကတော့-

• Optimality: BFS ဟာ အဆင့်အလိုက် (Layer by layer) ရှာဖွေတာဖြစ်လို့ အဖြေတွေ့ရင် အဲဒီအဖြေဟာ အဆင့်အနည်းဆုံး (Shortest Path) ဖြစ်မယ်ဆိုတာ သေချာပါတယ်။

• Uninformed Search: ဒီပြဿနာက အဆင့် (State Space) နည်းတဲ့အတွက် Heuristic (မှန်းဆချက်) မလိုဘဲ ရှာဖွေလည်း မြန်ဆန်ပါတယ်။

၄. Avoiding Repeated States (ထပ်နေသော အခြေအနေများကို ရှောင်ရှားခြင်း)

explored = set() ကို အသုံးပြုထားပါတယ်။ လှေက ဟိုဘက်ကမ်းသွား၊ ဒီဘက်ကမ်းပြန်လာ နဲ့ မူလနေရာပြန်ရောက်နေတဲ့ သံသရာလည် (Cycle) တွေကို ရှောင်ရှားဖို့အတွက် အလွန်အရေးကြီးပါတယ်။ ဒါမပါရင် ပရိုဂရမ်က အဆုံးမရှိ (Infinite Loop) ဖြစ်သွားနိုင်ပါတယ်။

၅. Path Reconstruction (လမ်းကြောင်း ပြန်လည်ဖော်ထုတ်ခြင်း)

AI က ပန်းတိုင် (Goal) ကို ရောက်သွားတဲ့အခါ၊ ပန်းတိုင်ရောက်တယ် ဆိုတာပဲ သိပြီး ဘယ်လိုရောက်လာလဲ မသိတတ်ကြပါဘူး။ ဒါကြောင့် parent ဆိုတဲ့ variable လေးနဲ့ “ငါ့ကို ဒီနေရာရောက်အောင် ဘယ်သူပို့လိုက်တာလဲ” ဆိုတာကို Node တိုင်းမှာ မှတ်ထားပါတယ်။ နောက်ဆုံးမှ Goal ကနေ Start ကို ပြန်ကောက် (Backtrack) ပြီး အဖြေထုတ်ပေးတာ ဖြစ်ပါတယ်။

အနှစ်ချုပ်

ဒီပရိုဂရမ်သည် Search Problem တစ်ခုကို ဖြေရှင်းရာမှာ လိုအပ်သော အခြေခံအုတ်မြစ်များအားလုံး ပါဝင်ပြီး၊ State Space Tree ကို စနစ်တကျ ဖြန့်ခင်းရှာဖွေပေးသော AI Program တစ်ပုဒ်ဖြစ်ပါတယ်။