2.1 ການສ້າງບັນຫາ ແລະ ພື້ນທີ່ສະຖານະ

ສະຖານະເລີ່ມຕົ້ນ, ຕົວດຳເນີນການ, ສະຖານະເປົ້າໝາຍ ແລະ ຕົ້ນທຶນ.

ບັນຫາການຄົ້ນຫາ

ບັນຫາຫຼາຍຢ່າງສາມາດປ່ຽນເປັນ ການຄົ້ນຫາ ໄດ້: ຊອກຄຳຕອບຂອງສົມຜົນ, ພິສູດທິດສະດີ, ຫຼື ຊອກເສັ້ນທາງຈາກ ວຽງຈັນ ໄປ ປາກເຊ ເທິງແຜນທີ່.

ບັນຫາແບບນີ້ມີ 4 ອົງປະກອບ:

ສະຖານະເລີ່ມຕົ້ນ (initial state)
ຕົວດຳເນີນການ (operators / actions) — ປ່ຽນສະຖານະໜຶ່ງໄປອີກສະຖານະໜຶ່ງ
ສະຖານະເປົ້າໝາຍ (goal states)
ຕົ້ນທຶນ ຂອງແຕ່ລະການປ່ຽນ (cost)

ພື້ນທີ່ສະຖານະ (state space)

ແມ່ນ ເຊັດຂອງທຸກສະຖານະ ທີ່ໄປຮອດໄດ້ຈາກສະຖານະເລີ່ມຕົ້ນ. ເຮົາສະແດງມັນເປັນ ກຣາຟມີທິດ: ແຕ່ລະຈຸດ (node) = 1 ສະຖານະ; ຖ້າຕົວດຳເນີນການ R ປ່ຽນ u → v ກໍມີລູກສອນ u → v ຕິດປ້າຍ R.

ຂະບວນການຄົ້ນຫາ = ສ້າງຕົ້ນໄມ້ຄົ້ນຫາ ທີ່ຮາກເປັນສະຖານະເລີ່ມຕົ້ນ.

ວັດແທກປະສິດທິພາບການຄົ້ນຫາ

ການຄົ້ນຫາ ຢຸດ ບໍ?
ພົບ ຄຳຕອບບໍ?
ຄຳຕອບນັ້ນ ດີທີ່ສຸດ (optimal) ບໍ?

ປະເພດການຄົ້ນຫາ

ການຄົ້ນຫາແບບບອດ (blind / uninformed) — ບໍ່ມີຄວາມຮູ້ຊ່ວຍນຳທາງ.
ການຄົ້ນຫາແບບ heuristic — ໃຊ້ປະສົບການສ້າງ ຟັງຊັນປະເມີນ ເພື່ອນຳທາງ.
ການຄົ້ນຫາທີ່ດີທີ່ສຸດ (optimal search)
ການຄົ້ນຫາມີຄູ່ແຂ່ງ (ເກມສອງຄົນ: ໝາກຮຸກ, ໝາກຈີນ...)

🎮 ຕົວຢ່າງ: ພື້ນທີ່ສະຖານະຂອງເກມ XO (tic-tac-toe) — ແຕ່ລະກະດານແມ່ນ 1 ສະຖານະ.