2.3 การออกแบบขั้นตอนวิธี

2.3 การออกแบบขั้นตอนวิธี

ขั้นตอนวิธี หรือ อัลกอริทึม (algorithm) หมายถึงกระบวนการแก้ปัญหาที่สามารถเข้าใจได้ มีลำดับหรือวิธีการในการแก้ไขปัญหาใดปัญหาหนึ่งอย่างเป็นขั้นเป็นตอนและชัดเจน เมื่อนำเข้าอะไร แล้วจะต้องได้ผลลัพธ์เช่นไร ซึ่งแตกต่างจากการแก้ปัญหาแบบสามัญสำนึก หรือฮิวริสติก (heuristic)โดยทั่วไป ขั้นตอนวิธี จะประกอบด้วย วิธีการเป็นขั้นๆ และมีส่วนที่ต้องทำแบบวนซ้ำ (iterate) หรือ เวียนเกิด (recursive) โดยใช้ตรรกะ (logic) และ/หรือ ในการเปรียบเทียบ (comparison) ในขั้นตอนต่างๆ จนกระทั่งเสร็จสิ้นการทำงาน ในการทำงานอย่างเดียวกัน อาจจะเลือกขั้นตอนวิธีที่ต่างกันเพื่อแก้ปัญหาได้ โดยที่ผลลัพธ์ที่ได้ในขั้นสุดท้ายจะออกมาเหมือนกันหรือไม่ก็ได้ และจะมีความแตกต่าง ที่จำนวนและชุดคำสั่งที่ใช้ต่างกันซึ่งส่งผลให้ เวลา (time) , และขนาดหน่วยความจำ (space) ที่ต้องการต่างกัน หรือเรียกได้อีกอย่างว่ามีความซับซ้อน (complexity) ต่างกัน การนำขั้นตอนวิธีไปใช้ ไม่จำกัดเฉพาะการเขียนโปรแกรมคอมพิวเตอร์ แต่สามารถใช้กับปัญหา

อื่น ๆ ได้เช่น การออกแบบวงจรไฟฟ้า, การทำงานเครื่องจักรกล, หรือแม้กระทั่งปัญหาในธรรมชาติ เช่น วิธีของสมองมนุษย์ในการคิดเลข หรือวิธีการขนอาหารของแมลง

คำว่า Algorithm มีที่มาจากชื่อของนักคณิตศาสตร์ชาวเปอร์เซียในยุคศตวรรษที่ 9 อะบู อับดิลลาหฺ อิบน มูซา อัลคอวาริซมีย์ (Abu Abdillah Muhammad ibn Musa al-Khawarizmi) คำว่า al-Khawarizmi ได้เพี้ยนเป็น Algoritmi เมื่องานเขียนของเขาได้รับการแปลเป็นภาษาละติน แล้วกลายเป็น Algorithm อัลกอริทึม ซึ่งใช้หมายถึงกฎที่ใช้ในการคิดคำนวณเลขคณิต และได้กลายมาเป็นคำ ขั้นตอนวิธี ในช่วงศตวรรษที่ 18. ในปัจจุบัน คำนี้ได้มีความหมายที่กว้างขึ้น หมายรวมถึง ขั้นตอนวิธีการในการแก้ปัญหาต่างๆ ขั้นตอนวิธีแรกสำหรับคอมพิวเตอร์นั้น เขียนขึ้นในปี ค.ศ. 1842 โดย เอดา ไบรอน ใน notes on the analytical engine ทำให้ถือกันว่า เอดาเป็นนักพัฒนาโปรแกรมหรือนักเขียนโปรแกรมคนแรกของโลก แต่เนื่องจาก ชาร์ลส แบบเบจ ไม่ได้สร้าง analytical engine จนเสร็จ ขั้นตอนวิธีของเอดานั้นจึงไม่ได้มีการใช้จริง

การตัดสินใจรดน้ําต้นไม้ของระบบรดน้ําต้นไม้อัตโนมัติ

ตัวอย่าง การตัดสินใจรดน้ำต้นไม้ของระบบรดนำต้นไม้อัตโนมัติ ระบบจะต้องอ่านข้อมูลความชื้นของดิน แล้วเปรียบเทียบกับค่าที่กำหนดไว้ (สมมติค่าความชื้นที่กำหนดเป็น 0.1 หน่วย) หากค่าความชื้นต่ำกว่าค่าที่กำหนด ระบบจะส่งสัญญาณเปิดน้ำ และหากค่าความชื้นเกินกว่าหรือเท่ากับค่าที่กำหนดไว้ ระบบจะส่งสัญญาณปิดน้ำ มีขั้นตอนวิธีดังนี้

ขั้นตอนวิธี: ควบคุมการเปิดปิดน้ําาของเครื่องรดน้ําาต้นไม้

1. อ่านค่าความชื้นของดิน

2. ให้ H แทนค่าความชื้น

3. ถ้า H < 0.1 แล้ว

3.1 ส่งสัญญาณเปิดน้ำ

ถ้าเงื่อนไขไม่เป็นจริง

3.2 ส่งสัญญาณปิดน้ำ

ขั้นตอนวิธีดังกล่าวเป็นการตัดสินใจเพียงครั้งเดียว เพื่อความสมบูรณ์ของขั้นตอนวิธี จะต้องให้ระบบรดน้ำต้นไม้มีการอ่านค่าและส่งสัญญาณควบคุมสม่ำเสมอ จึงต้องให้มีการทำงานซ้ำๆ ต่อเนื่องกันไป ดังนี้

ขั้นตอนวิธี: ควบคุมการเปิดปิดน้ําาของเครื่องรดน้ําาต้นไม้

ข้อมูลเข้า : ค่าความชื้นของดิน

ข้อมูลออก : สัญญาณเปิดปิดน้ํา

1. ทำซ้ำทุก ๆ 1 วินาที

1.1 อ่านค่าความชื้นของดิน

1.2 ให้ H แทนค่าความชื้น

1.3 ถ้า H < 0.1 แล้ว

1.3.1 ส่งสัญญาณเปิดน้ํา

ถ้าเงื่อนไขไม่เป็นจริง

1.3.2 ส่งสัญญาณปิดน้ำ