2.4 ການຄົ້ນຫາທີ່ດີທີ່ສຸດ: ອັລກໍຣິທຶມ A*

f(u) = g(u) + h(u), heuristic ທີ່ຍອມຮັບໄດ້ ແລະ ເສັ້ນທາງສັ້ນທີ່ສຸດ.

ບັນຫາເສັ້ນທາງສັ້ນທີ່ສຸດ

ແຕ່ລະລູກສອນ (u, v) ມີ ນ້ຳໜັກ k(u,v) ≥ 0 (ເຊັ່ນ ໄລຍະທາງເປັນກິໂລແມັດ). ເປົ້າໝາຍ: ເສັ້ນທາງທີ່ ຜົນບວກນ້ຳໜັກນ້ອຍສຸດ.

ຖ້າໃຊ້ການຄົ້ນຫາແບບບອດ ຊອກທຸກເສັ້ນທາງແລ້ວປຽບທຽບ → ຊ້າເກີນໄປສຳລັບພື້ນທີ່ໃຫຍ່. Best-first ຫຼື Hill-climbing ກໍບໍ່ຮັບປະກັນຄຳຕອບດີທີ່ສຸດ.

ຟັງຊັນປະເມີນລວມ

g(u) — ຄວາມຍາວເສັ້ນທາງ ຈິງ ຈາກຈຸດເລີ່ມ u₀ ຫາ u.
h(u) — ຄາດຄະເນ ຄວາມຍາວຈາກ u ຫາເປົ້າໝາຍ.
f(u) = g(u) + h(u) — ຄາດຄະເນເສັ້ນທາງທັງໝົດທີ່ຜ່ານ u.

h ເອີ້ນວ່າ ຍອມຮັບໄດ້ (admissible) ຖ້າ h(u) ≤ ໄລຍະຈິງທີ່ສັ້ນທີ່ສຸດ ຈາກ u ຫາເປົ້າໝາຍ ສຳລັບທຸກ u. ຕົວຢ່າງ: ໃນແຜນທີ່, h(u) = ໄລຍະເສັ້ນຊື່ (ນົກບິນ) ຫາເປົ້າໝາຍ.

ອັລກໍຣິທຶມ A*

Procedure A*;
1. L ← [u₀]
2. Loop:
   2.1 ຖ້າ L ຫວ່າງ → ລົ້ມເຫຼວ
   2.2 ເອົາ u ອອກຈາກຫົວ L
   2.3 ຖ້າ u ເປັນເປົ້າໝາຍ → ສຳເລັດ
   2.4 ສຳລັບທຸກ v ຕິດກັບ u:
         g(v) ← g(u) + k(u,v)
         f(v) ← g(v) + h(v)
         ໃສ່ v ເຂົ້າ L
   2.5 ຮຽງ L ຕາມ f ຈາກນ້ອຍຫາໃຫຍ່

ຄຸນສົມບັດ: ຖ້າ h ຍອມຮັບໄດ້ → A* ພົບ ເສັ້ນທາງສັ້ນທີ່ສຸດ ແນ່ນອນ.

ຕົວຢ່າງຈາກປຶ້ມ (ກຣາຟ A → B)

ຂະຫຍາຍ A (h=14): ລູກ C: g=9, f=9+15=24; D: g=7, f=7+6=13; E: g=13, f=13+8=21; F: g=20, f=20+7=27. → ເລືອກ D (f ນ້ອຍສຸດ) ຂະຫຍາຍຕໍ່ ... ຈົນຮອດ B.

🗺️ ໃນຫ້ອງທົດລອງ ລອງ A* ທຽບກັບ BFS: A* ສຳຫຼວດຊ່ອງໜ້ອຍກວ່າຫຼາຍ ແຕ່ຍັງໄດ້ເສັ້ນທາງສັ້ນທີ່ສຸດຄືກັນ.

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