2.3 ການຄົ້ນຫາໂດຍໃຊ້ຟັງຊັນປະເມີນ

Heuristic, ເກມ 8 ຕົວເລກ, Best-first search ແລະ Hill-climbing.

Heuristic ແມ່ນຫຍັງ?

ການຄົ້ນຫາແບບ heuristic ໃຊ້ ປະສົບການ, ຄວາມເຂົ້າໃຈ ແລະ ສັນຊາດຕະຍານ ເພື່ອຄາດຄະເນໃນແຕ່ລະກ້າວ. AI ໃຊ້ມັນໃນ 2 ສະຖານະການ:

ບັນຫານິຍາມຊັດເຈນ ແຕ່ ຄົ້ນຫາທັງໝົດບໍ່ໄຫວ (ເຊັ່ນ ໝາກຮຸກ — ພື້ນທີ່ລະເບີດ).
ຂໍ້ມູນ ຫຼື ຄວາມຮູ້ ບໍ່ແນ່ນອນ (ເຊັ່ນ ການວິນິດໄສພະຍາດ, ເຄື່ອງຈັກເພ).

ຂັ້ນຕອນຫຼັກ: (1) ເລືອກວິທີສະແດງສະຖານະ ແລະ ຕົວດຳເນີນການ, (2) ສ້າງ ຟັງຊັນປະເມີນ h, (3) ອອກແບບຍຸດທະສາດເລືອກສະຖານະ.

ຕົວຢ່າງ: ເກມ 8 ຕົວເລກ (8-puzzle)

ກະດານ 3×3 ມີເລກ 1–8 ແລະ ຊ່ອງຫວ່າງ 1 ຊ່ອງ. ຍ້າຍຊ່ອງຫວ່າງເພື່ອໃຫ້ກະດານກັບສູ່ສະຖານະເປົ້າໝາຍ.

h1 = ຈຳນວນແຜ່ນທີ່ ຢູ່ຜິດບ່ອນ.
h2 = ຜົນບວກໄລຍະທາງ (ຕາມແນວນອນ + ແນວຕັ້ງ, Manhattan) ຂອງແຕ່ລະແຜ່ນໄປຫາບ່ອນທີ່ຖືກ.

ໃນຕົວຢ່າງຂອງປຶ້ມ: h1 = 5, h2 = 1+2+3+1+1 = 8. ໂດຍທົ່ວໄປ h2 ນຳທາງໄດ້ດີກວ່າ h1.

ການຄົ້ນຫາດີທີ່ສຸດກ່ອນ (Best-First Search)

= BFS + ຟັງຊັນປະເມີນ: ໃສ່ v ເຂົ້າ L ໂດຍ ຮຽງ L ຕາມ h ຈາກນ້ອຍຫາໃຫຍ່ → ສະເໝີເລືອກສະຖານະທີ່ "ເບິ່ງຄືໃກ້ເປົ້າໝາຍທີ່ສຸດ".

ການຂຶ້ນພູ (Hill-Climbing)

= DFS + ຟັງຊັນປະເມີນ: ຂະຫຍາຍສະຖານະປັດຈຸບັນ, ຮຽງ ລູກ ຕາມ h (ລາຍການ L1), ແລ້ວເອົາ L1 ໄປໄວ້ ຫົວ L. ໄວ ແຕ່ອາດຕິດຢູ່ ຈຸດສູງສຸດທ້ອງຖິ່ນ (local optimum).

🧩 ລອງແກ້ເກມ 8 ຕົວເລກ ໃນຫ້ອງທົດລອງ ແລ້ວປຽບທຽບຈຳນວນສະຖານະທີ່ສຳຫຼວດ ເມື່ອໃຊ້ h1 ທຽບກັບ h2.

🧪 ເປີດຫ້ອງທົດລອງສຳລັບບົດນີ້