D E A P T H F I R S T S E A R C H
การค้นหาตามแนวลึก ( Deapth first Search ) เป็นวิธีการค้นหาในระดับที่ลึงลงไปเรื่อย ๆ
ไม่มีการกวาดหาตามแนวกว้าง หรือ กวาดหาทุกค่าในระดับความลึกเดียวกัน
จนกว่าจะถึงระดับความลึกตามที่กำหนด หรือ ลึกถึงที่สุด จึงย้อนกลับ มาค้นหา ค่าใหม่ ต่อไป
ตัวอย่างที่ง่ายที่สุดสำหรับการค้นหาในลักษณะวิธีนี้คือการค้นหา แบบ Preorder ใน Tree
เพื่อให้เข้าใจยิ่งขึ้น เราจะมาศึกษาปัญหาการเปิด/เปิด หลอดไฟ
( ข้อสอบ คอมพิวเตอร์ โอลิมปิก วิชาการ นานาชาติ ) ซึ่งมีรายละเอียด ดังนี้
- ถ้ามีหลอดไฟ N หลอดที่กำลังเปิดอยู่ (เปิด ให้สถานะเป็น 1, ปิด ให้สถานะเป็น 0)
- การ ปิด/เปิด มีด้วยกัน 4 วิธี
1. เปลี่ยนสถานะดวงไฟในลักษณะตรงกันข้ามทุกดวง
2. เปลี่ยนสถานะดวงไฟในลักษณะตรง เฉพาะดวงไฟหมายเลขคี่
3. เปลี่ยนสถานะดวงไฟในลักษณะตรง เฉพาะดวงไฟหมายเลขคู่
4. เปลี่ยนสถานะดวงไฟในลักษณะตรง เฉพาะดวงไฟหมายเลข 1, 3, 7 . . .
- ถ้ากำหนดการ ปิด/เปิด C ครั้ง ซึ่งจะเลือก ปิด/เปิด จาก 4 วิธีข้างต้น เพื่อให้สอดคล้อง กับเงื่อนไขสุดท้าย
เช่น หลอดที่ 1, 4 และ 5 ปิด หลอดที่ 3 เปิด จะเห็นว่าการค้นหาด้วยวิธี Deapth first Search จะเหมาะสมที่สุด
สำหรับกรณีนี้ เพราะสถานะสุดท้ายคือ สถานะ ที่ ต้องการ ดังนั้นจึงไม่ จำเป็นต้อง ขยาย ทุกค่า ทุกระดับ
ซึ่งจะทำ ให้ Search space มีขนาดใหญ่ขึ้น และเป็นสาเหตุทำให้หน่วยความจำ เต็ม
ถ้าให้ N = 10, C = 3 และสถานะสุดท้ายที่ต้องการ คือ หลอดที่ 1 และ 2 ปิด, หลอดที่ 3 เปิด
การค้นหาตามแนวลึก ครั้งที่ 1
| หลอดที่ | (1) | (2) | (3) | (4) | (5) | (6) |
(7) | (8) | (9) | (10) | |
| สถานะ เริ่มต้น | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |
| ปิด/เปิดด้วยวิธีที่ 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ครั้งที่ 1 |
| ปิด/เปิดด้วยวิธีที่ 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | ครั้งที่ 2 |
| ปิด/เปิดด้วยวิธีที่ 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ครั้งที่ 3 |
ไม่มีคำตอบ
การค้นหาตามแนวลึก ครั้งที่ 2
| หลอดที่ | (1) | (2) | (3) | (4) | (5) | (6) | (7) | (8) | (9) | (10) | |
| สถานะ เริ่มต้น | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |
| ปิด/เปิดด้วยวิธีที่ 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ครั้งที่ 1 |
| ปิด/เปิดด้วยวิธีที่ 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | ครั้งที่ 2 |
| ปิด/เปิดด้วยวิธีที่ 2 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | ครั้งที่ 3 |
ไม่มีคำตอบ
การค้นหาตามแนวลึก ครั้งที่ 3
| หลอดที่ | (1) | (2) | (3) | (4) | (5) | (6) | (7) | (8) | (9) | (10) | |
| สถานะ เริ่มต้น | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |
| ปิด/เปิดด้วยวิธีที่ 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ครั้งที่ 1 |
| ปิด/เปิดด้วยวิธีที่ 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | ครั้งที่ 2 |
| ปิด/เปิดด้วยวิธีที่ 3 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | ครั้งที่ 3 |
ไม่มีคำตอบ
การค้นหาตามแนวลึก ครั้งที่ 4
| หลอดที่ | (1) | (2) | (3) | (4) | (5) | (6) | (7) | (8) | (9) | (10) | |
| สถานะ เริ่มต้น | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |
| ปิด/เปิดด้วยวิธีที่ 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ครั้งที่ 1 |
| ปิด/เปิดด้วยวิธีที่ 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | ครั้งที่ 2 |
| ปิด/เปิดด้วยวิธีที่ 4 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | ครั้งที่ 3 |
ไม่มีคำตอบ
o o o
การค้นหาตามแนวลึก ครั้งที่ i
| หลอดที่ | (1) | (2) | (3) | (4) | (5) | (6) | (7) | (8) | (9) | (10) | |
| สถานะ เริ่มต้น | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |
| ปิด/เปิดด้วยวิธีที่ 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ครั้งที่ 1 |
| ปิด/เปิดด้วยวิธีที่ 4 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | ครั้งที่ 2 |
| ปิด/เปิดด้วยวิธีที่ 2 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | ครั้งที่ 3 |
ดังนั้นถ้าต้องการให้ หลอดที่ 1 และ 2 ปิด, หลอดที่ 3 เปิด ต้องกดด้วยวิธีที่ 1, 4 และ 2 เป็นต้น
Lamps.c เป็นโปรแกรมเพื่อแก้ปัญหานี้ โปรแกรมนี้จะรับ Input จาก แฟ้มข้อมูล in.txt และจะได้
output ในแฟ้ม out.txt สิ่งที่ควรระวัง คือ ถ้ากำหนดให้ กด หลายๆ ครั้ง และจำนวน
หลอดไฟ มาก ๆ จะทำให้ หน่วยความจำเต็มเร็วมาก และถ้ากำหนดเงื่อนไขสุดท้าย
มาก ก็จะไม่มีคำตอบ เลย สำหรับ Lamps1.c
จะรับ Input จากแป้นพิมพ์ แต่ก็ได้เตรียมโปรแกรม ให้แก้ไข เพื่อให้รับข้อมูล จากแฟ้ม
ข้อมูล in.txt