Stuart Russell နဲ့ Peter Norvig တို့ ရေးသားတဲ့၊ “Artificial Intelligence: A Modern Approach, Fourth Edition” စာအုပ် ရဲ့၊ "CHAPTER 4 SEARCH IN COMPLEX ENVIRONMENTS" အခန်းမှာ ပါတဲ့ "Hill-climbing Algorithm" ကို "8-queens problem" နဲ့ ပေါင်းစပ်ပြီး အပြည့်အစုံ ရှင်းလင်းတင်ပြပေးပါမယ်။
Figure 4.3 (က) ဘုရင်မ ၈-ပါးပြဿနာ။ ဘုရင်မ ၈-ပါးကို စစ်တုရင်ဘုတ်ပေါ်တွင် ဘုရင်မတစ်ပါးနှင့်တစ်ပါး မတိုက်ခိုက်စေရန် ထားပါ။ (ဘုရင်မသည် အတန်း၊ ကော်လံ သို့မဟုတ် ထောင့်ဖြတ် ပေါ်ရှိ မည်သည့် အရာကိုမဆို တိုက်ခိုက်နိုင်ပါသည်။) ပုံတွင် ထောင့်ဖြတ်မျဉ်းတစ်လျှောက်တွင် တစ်ခုနှင့်တစ်ခု တိုက်ခိုက်နေသော စတုတ္ထနှင့် သတ္တမကော်လံရှိ ဘုရင်မနှစ်ပါးမှလွဲ၍ ဤအနေအထားသည် အဖြေတစ်ခု ရလုနီးပါးအဆင့်ဖြစ်သည်။
(ခ) heuristic cost estimate [current state အတွက်၊ ကျန်ရှိနေသေးတဲ့ ပဋိပက္ခ conflicts အရေအတွက် ကို တိုင်းတာတဲ့ဖန်ရှင်] h = 17 ပါသော ဘုရင်မ ၈-ပါးအခြေအနေ။ လက်ရှိအခြေအနေ။ စစ်တုရင်ဘုတ်သည် ၎င်း၏ကော်လံအတွင်း ဘုရင်မတစ်ပါးကို ရွှေ့ခြင်းဖြင့် ရရှိနိုင်သော ဆက်ခံသူတိုင်းအတွက် h ၏တန်ဖိုးကို ပြသည်။ h = 12 ဖြင့် အကောင်းဆုံးတွဲဖက်ထားသော ရွေ့လျားမှု ၈-ခုရှိသည်။ hill-climbing algorithm သည် ဤအရာများထဲမှ တစ်ခုကို ရွေးပါမည်။
(နည်းသစ်ဉာဏ်ရည်တုပညာမိတ်ဆက်, စာ-၁၆၀)
ပြီးပြည့်စုံသောအခြေအနေ တည်ဆောက်ခြင်း (Complete-state Formulation)
8-queens ပြဿနာကို ဖြေရှင်းရာမှာ နည်းလမ်းအမျိုးမျိုးရှိပါတယ်။ ဥပမာ - ဘုတ်ပြားအလွတ်ကနေ စပြီး ဘုရင်မ တစ်ပါးချင်းစီကို အဆင့်လိုက် နေရာချသွားတဲ့ နည်းလမ်းရှိသလို၊ ယခု ကျွန်တော်တို့ အသုံးပြုမယ့် Complete-state formulation လိုမျိုး နည်းလမ်းလည်း ရှိပါတယ်။
Complete-state formulation ဆိုတာ အစကတည်းက စစ်တုရင်ဘုတ်ပြားပေါ်မှာ ကော်လံ (Column) တစ်ခုကို ဘုရင်မတစ်ပါးစီနှုန်းနဲ့ ၈ ပါးလုံးကို နေရာချထားလိုက်ခြင်းပါ။ ဆိုလိုတာက အခြေအနေတိုင်းမှာ အဖြေတစ်ခု ဖြစ်လာဖို့ လိုအပ်တဲ့ "အစိတ်အပိုင်းများ အားလုံး (ဘုရင်မ ၈ ပါးလုံး)" ပါရှိနေပြီးသား ဖြစ်ပါတယ်။ ဒါပေမဲ့ ၎င်းတို့ဟာ အချင်းချင်း တိုက်ခိုက်နိုင်တဲ့ (စားနိုင်တဲ့) နေရာတွေမှာ ရှိနေနိုင်တဲ့အတွက် အားလုံးက မှန်ကန်တဲ့ နေရာမှာတော့ ရှိမနေသေးပါဘူး။ ကျွန်တော်တို့ရဲ့ အဓိက ရည်ရွယ်ချက်က အဲဒီ ပဋိပက္ခ (Conflicts) တွေကို တစ်ဆင့်ချင်း လျှော့ချသွားဖို့ပဲ ဖြစ်ပါတယ်။
Heuristic Cost Estimate
# -*- coding: utf-8 -*-
"""
Created on Sat Feb 21 20:59:50 2026
@author: kks
"""
import random
# ဘုရင်မ ၈ ပါးရဲ့ အခြေအနေကို list တစ်ခုအနေနဲ့ ဖော်ပြပါမယ်။
# ဥပမာ - state = [3, 0, 4, 7, 5, 2, 6, 1] ဆိုပါစို့။
# index (0 မှ 7 အထိ) က ကော်လံ (Column) ကို ကိုယ်စားပြုပြီး၊
# ထိုနေရာရှိ တန်ဖိုးက အဲဒီကော်လံမှာရှိတဲ့ ဘုရင်မရဲ့ အတန်း (Row) ကို ကိုယ်စားပြုပါတယ်။
# ဒါဟာ Complete-state formulation ကို ကိုယ်စားပြုတဲ့ အကောင်းဆုံး Data Structure ဖြစ်ပါတယ်။
def calculate_conflicts(state):
"""
Heuristic cost estimate function ပါ။
လက်ရှိ board အခြေအနေ (state) မှာ အချင်းချင်း တိုက်ခိုက်နိုင်တဲ့ ဘုရင်မ စုံတွဲ အရေအတွက်ကို တွက်ချက်ပေးပါတယ်။
"""
conflicts = 0
n = len(state)
for i in range(n):
for j in range(i + 1, n):
# တိုက်ခိုက်နိုင်ခြေ (၂) မျိုးကို စစ်ဆေးရပါမယ်။
# ၁။ အတန်း (Row) တူနေသလား စစ်ဆေးခြင်း -> state[i] == state[j]
# ၂။ ထောင့်ဖြတ် (Diagonal) တူနေသလား စစ်ဆေးခြင်း -> abs(state[i] - state[j]) == abs(i - j)
# မှတ်ချက် - ကော်လံ (Column) ကတော့ Array ရဲ့ Index မတူတဲ့အတွက် အမြဲတမ်း ကွဲပြားနေပြီးသားပါ။
if state[i] == state[j] or abs(state[i] - state[j]) == abs(i - j):
conflicts += 1
return conflicts
def get_best_neighbor(state):
"""
လက်ရှိအခြေအနေကနေ သွားနိုင်တဲ့ အိမ်နီးချင်း (Neighbors) ၅၆ ခုထဲက
conflicts အနည်းဆုံးဖြစ်မယ့် အကောင်းဆုံး အိမ်နီးချင်းကို ရှာဖွေပေးပါတယ်။
(ကော်လံ ၈ ခုမှာရှိတဲ့ ဘုရင်မတွေကို ကိုယ်ပိုင်ကော်လံအတွင်း အခြား row ၇ ခုဆီ တစ်ပါးချင်း ရွှေ့ကြည့်ခြင်းဖြစ်ပါတယ်၊ ၈ x ၇ = ၅၆)
"""
best_neighbors = []
# လက်ရှိ cost ကို အနည်းဆုံး cost အဖြစ် အရင်သတ်မှတ်ထားပါမယ်။
min_conflicts = calculate_conflicts(state)
n = len(state)
for col in range(n):
for row in range(n):
if state[col] == row:
continue # လက်ရှိရှိနေတဲ့နေရာကို ရွှေ့စရာမလိုလို့ ကျော်သွားပါမယ်
# အိမ်နီးချင်း အခြေအနေသစ် တစ်ခု ဖန်တီးပါမယ်
neighbor = list(state)
neighbor[col] = row
# အိမ်နီးချင်းအသစ်ရဲ့ Heuristic cost (conflicts) ကို တွက်ချက်ပါမယ်
neighbor_conflicts = calculate_conflicts(neighbor)
if neighbor_conflicts < min_conflicts:
# ပိုကောင်းတဲ့ အခြေအနေ (conflicts ပိုနည်းတဲ့ အခြေအနေ) ကို တွေ့ရင်
min_conflicts = neighbor_conflicts
best_neighbors = [neighbor] # တွေ့ထားသမျှ အကောင်းဆုံး list ကို အသစ်ပြန်စပါမယ်
elif neighbor_conflicts == min_conflicts:
# တူညီတဲ့ အကောင်းဆုံး အခြေအနေတွေကို list ထဲ ထပ်ထည့်ပါမယ်
best_neighbors.append(neighbor)
# အကောင်းဆုံး အိမ်နီးချင်းတွေထဲက တစ်ခုကို ကျပန်းရွေးချယ်ပါမယ်
if best_neighbors:
return random.choice(best_neighbors), min_conflicts
else:
return state, min_conflicts # ပိုကောင်းတဲ့ အိမ်နီးချင်း မရှိရင် လက်ရှိကိုပဲ ပြန်ပေးပါမယ်
def hill_climbing(initial_state):
"""
Steepest-ascent Hill-climbing algorithm ရဲ့ အဓိက အပိုင်းဖြစ်ပါတယ်။
"""
current_state = initial_state
current_conflicts = calculate_conflicts(current_state)
step = 0
print(f"Step {step}: Initial State = {current_state}, Conflicts = {current_conflicts}")
while True:
# အကောင်းဆုံး အိမ်နီးချင်းကို ရှာပါမယ်
neighbor, neighbor_conflicts = get_best_neighbor(current_state)
# Hill-climbing ရဲ့ အားနည်းချက် သဘောတရားအရ၊ ပိုကောင်းတဲ့ အိမ်နီးချင်း မရှိတော့ရင် (သို့)
# လက်ရှိထက် ပဋိပက္ခ မနည်းတော့ဘူးဆိုရင် တောင်ထိပ် (Local Maxima သို့မဟုတ် Global Maxima) ကို ရောက်ပြီဖြစ်လို့ ဆက်မရှာဘဲ ရပ်ပါမယ်။
if neighbor_conflicts >= current_conflicts:
print(f"\nSearch stopped. Reached a peak (cost cannot be decreased further).")
break
# အခြေအနေသစ်ကို ပြောင်းလဲပါမယ်
current_state = neighbor
current_conflicts = neighbor_conflicts
step += 1
print(f"Step {step}: Moved to = {current_state}, Conflicts = {current_conflicts}")
return current_state, current_conflicts
# ပရိုဂရမ် စတင်ခြင်း
if __name__ == "__main__":
# Complete-state formulation အရ ဘုရင်မ ၈ ပါးကို ကျပန်း နေရာချပါမယ်
# (ကော်လံတစ်ခုစီအတွက် row 0 ကနေ 7 အထိ ကျပန်းရွေးချယ်ပါမယ်)
initial_board = [random.randint(0, 7) for _ in range(8)]
print("--- Hill-Climbing Algorithm for 8-Queens ---")
final_state, final_cost = hill_climbing(initial_board)
print("\n--- Final Result ---")
print(f"Final State: {final_state}")
print(f"Remaining Conflicts: {final_cost}")
if final_cost == 0:
print("Success! A complete solution without any conflicts was found.")
else:
print("Failed to find a perfect solution. Got stuck in a Local Maximum.")
print("(မှတ်ချက် - ရိုးရှင်းသော Hill-climbing သည် တောင်ကုန်းငယ်များ (Local Maxima) တွင် ပိတ်မိလေ့ရှိပါသည်။ ၎င်းသည် ဤ Algorithm ရဲ့ သဘာဝ အားနည်းချက်ဖြစ်ပါသည်။)")
ပရိုဂရမ် အနှစ်ချုပ်
ဒီပရိုဂရမ်က၊ ဘုရင်မ ၈ ပါးကို ကျပန်းချထားခြင်းမှ စတင်ပြီး၊ တစ်ဆင့်ချင်းစီမှာ၊ အချင်းချင်းတိုက်ခိုက်မှု (Conflicts) အနည်းဆုံးဖြစ်စေမဲ့ အိမ်နီးချင်းအခြေအနေဆီသို့ ရွှေ့လျားသွားပါတယ်။ တိုက်ခိုက်မှု လုံးဝမရှိတော့သည့် အခြေအနေ (သို့မဟုတ်) ထပ်မံ၍ လျှော့ချ၍ မရနိုင်တော့သည့် အခြေအနေ (Local Maxima) သို့ရောက်သောအခါ ရပ်တန့်သွားမှာဖြစ်ပါတယ်။
နောက် ပို့စ်မှာ Hill-Climbing ရဲ့ အဓိကပြဿနာဖြစ်တဲ့ "Local Maxima မှာ ပိတ်မိတတ်ခြင်း" ကို ဖြေရှင်းပေးနိုင်တဲ့ "Random-restart hill-climbing" အကြောင်းကိုဆက်လက်တင်ပြပေးပါမယ်။



