การค้นหาในปริภูมิสภานะโดยใช้อัลกอริทึ่มปีนเขา (Hill-Climbing)

21 Feb
hill-climbing1

เตรียมการสอนเรื่อง Heuristic Search โดยเรื่องแรกที่จะสอนคือ การค้นหาในปริภูมิสภานะโดยใช้อัลกอริทึ่มปีนเขา หรือ Hill Climbing ซึ่งเป็นอัลกอริทึ่มอย่างง่ายที่สุด โดยกระบวนการสอนยังใช้ปัญหาเป็นฐานในการสอน คือ ปัญหาเรื่อง Travelling Sealsman Problem เช่นเดิม แต่เพิ่มจำนวนของเมืองให้มากขึ้น เพื่อให้ปริภูมิสถานะมีขนาดใหญ่มากๆ จนไม่สามารถค้นหาแบบแจกแจงสถานะทั้งหมดในปริภูมิได้ หรือ ไม่สามารถใช้การค้นหาแบบ Exhaustive Search ได้ จากตัวอย่างที่ยกขึ้นมานั้นเพิ่มจำนวนเมืองให้เป็น 10 เมือง ซึ่งจำนวนเส้นทางที่เป็นไปได้ที่เกิดจาการสับเปลี่ยนตำแหน่ง หรือ permutations จะสามารถคำนวนได้จาก 10! ซึ่งเป็นจำนวนมหาศาล ลักษณะการทำงานของอัลกอริทึ่มปีนเขา คือการนำเอาค่าฮิวริสติกเข้ามาช่วยตัดสินใจ โดยจะตัดสินใจเลือกเส้นทางการค้นหาว่าจะดำเนินไปในทิศทางใด โดยจะเลือกจากตำแหน่งที่มีค่าฮิวริสติกที่ดีขึ้นจากสถานะปัจจุบันเท่านั้น ซึ่งเปรียบเสมือนการปีนเขา คือจะมีการปีนขึ้นไปยังจุดที่มีความสูงกว่าตำแหน่งปัจจุบันเท่านั้น การเรียนรู้จากอัลกอริทึ่มปีนเขา … Read More »

ตัวอย่างการค้นหาในปริภูมิสภานะแบบค้นหาทั้งหมด (exhaustive search)

8 Feb
16285282530_9e1b217ee8_b

บทเรียนต่อไปที่ต้องเตรียมการสอนคือ การค้นหาในปริภูมิสภานะ หรือ state space เรื่องของการค้นหาฟังดูแล้วเหมือนจะไม่ยากแต่จริงๆ มีประเด็นที่น่าสนใจมากมายในฟิลด์นี้ และน่าจะเป็นเรื่องยากสำหรับนักศึกษาที่ไม่มีพื้นฐานเรื่องการคิด ระบบอัลกอลิทึ่ม และมีพื้นฐานการเขียนโปรแกรมที่ไม่ดีพอสมควร การปูพื้นฐานกระบวนการค้นหาพื้นฐาน จากวิธีที่ง่ายๆ เพื่อเชื่อมโยงไปสู่กระบวนการค้นหาแบบฮิวริสติก จึงเป็นเรื่องที่จำเป็นอย่างมาก ดังนั้นในเคสแบบนี้การจะสอนให้นักศึกษาเข้าใจพื้นฐานและต่อยอดไปสู่ระดับที่สูงขึ้นคงต้องใจเย็นกันสักหน่อย และการนำเอาวิธีการสอนแบบใช้ปัญหาเป็นฐาน (Problem Based Learning) ดูจะเป็นเรื่องที่เหมาะสมและน่าจะเป็นไปได้ที่สุด เลยเลือกปัญหาที่เป็นหาที่ง่ายที่สุดสำหรับฟิลด์ทางด้น AI มาคือ ปัญหาการเดินทางของพนักงานขาย หรือ Traveling Salesman Problem เริ่มจากการจำลองเมืองต่างๆ ให้อยู่ในรูปของพิกัด X และ Y บนระนาบ 2 มิติ และสอนวิธีการค้นหาระยะทางระหว่างจุดด้วยสูตรการคำนวนทางคณิตศาสตร์ ซึ่งผู้สนใจสามารถเข้าไปดูสูตรคำนวนได้ที่ calculate distance … Read More »

Python : Permutations Generator

31 Jan
16382058086_fcd6f25222_b

ภาษาไพทอนเป็นภาษาที่เพียบพร้อมในด้วยเครื่องมือสำหรับ Scientific Programming จริงๆ วันนี้เตรียมการสอนในรายวิชา ปัญญาประดิษฐ์ (AI) สิ่งที่ต้องอธิบายให้นักศึกษาอย่างชัดเจนและมองเห็นภาพในบทเรียนเรื่อง การแก้ปัญหา (Problem Solving) คือ ปริภูมิสถานะ (State Space) หากนักศึกษาไม่สามารถมองเห็นว่า ปริภูมิสถานะคืออะไร สถานะคืออะไร สถานะที่เป็นไปได้ทั้งหมดคืออะไร ย่อมยากต่อการสอนต่อยอดไปถึงเรื่องของเทคนิคการค้นหาต่อไป ดังนั้นประเด็นเรื่องนี้เป็นส่ิงที่ต้องเน้นในการสอนก่อนเป็นอันดับแรก วิธีการสอนให้บรรลุผลที่ง่ายที่สุด น่าจะเป็นการใช้ปัญหาเป็นฐานในการเรียนรู้ เลยยกตัวอย่างปัญหาที่เป็นปัญหาคลาสสิคอีกปัญหาหนึ่งทางด้าน AI คือ Traveling Salman Problem มาเป็นตัวอย่าง ให้นักษาจำลองการเดินทางไปยังเมืองต่างๆ สัก 3 – 5 เมือง กำหนดปริภูมิสภานะว่าคืออะไร และสถานะที่เป็นไปได้ทั้หมดคืออะไร และมองให้เห็นถึงการขยายตัวของขนาดของปริภูมิสถานะว่าสำหรับปัญหานี้ ขนาดของปริภูมิสภานะมีการขยายตัวแบบแฟคทอร์เรียลได้อย่างไร … Read More »