มาต่อตอนที่ 3 ตอนจบ
วันนี้มาขึ้นเรือกัน แน่นอนที่ว่าต้องมีชาวนาไปด้วย รวมกันแล้วบนเรือมีได้ 2 อย่าง
มาเริ่มกันที่ชาวนาไปคนเดียวก่อน และต้องอยู่ในสถานะที่ปลอดภัยด้วย (ถ้าลืมไปอ่าน 2 ตอนก่อนหน้านี้)
สถานะที่ปลอดภัยเมื่อชาวนาไปอยู่อีกฝั่งหนึ่ง ที่ตรงข้ามกับฝั่งเดิม
นั่นคือ ต้องหาว่าฝั่งตรงข้ามของชาวนาคืออะไร (other-side) และของแต่ละอย่างอยู่ฝั่งไหน เมื่อชาวนาข้ามไปแล้วปลอดภัยไหม เขียนใน LISP ได้เป็น
(defun farmer-with-him (side)
(safe (create-side (other-side (where-farmer side))
(where-wolf side)
(where-goat side)
(where-cabbage side))))
มี function เพิ่มขึ้นคือ
(defun create-side (f w g c) (list f w g c))
(defun other-side (side)
(cond ((equal side 'w) 'e)
((equal side 'e) 'w)))
ต่อมาเขียนได้ไหมว่า ให้ชาวนาพาของแต่ละอย่างข้ามฝั่ง เขียนอย่างไร
มาดูเฉลย
1.เริ่มต้นต้องตรวจสอบก่อนว่าของที่จะพาไปนั้นอยู่ฝั่งเดียวกับชาวนาไหม เขียน LISP ได้เป็น (ยกตัวอย่าง wolf)
(equal (where-farmer side) (where-wolf side))
2.ถ้าใช่ตรวจสอบต่อไปว่าหลังจากข้ามฝั่งแล้ว สถานะปลอดภัยไหม
(is-safe (create-side (other-side (where-farmer side))
(other-side (where-wolf side))
(where-goat side)
(where-cabbage side))
3.รวมข้อ 1 และ 2
(defun farmer-with-wolf (side)
(cond((equal (where-farmer side) (where-wolf side))
(is-safe (create-side (other-side (where-farmer side))
(other-side (where-wolf side))
(where-goat side)
(where-cabbage side))))
;และถ้าไม่ปลอดภัย หรือชาวนากับของที่ต้องการพาไปด้วยอยู่คนละฝั่งกัน
;ก็ return nil
(t nil)
);end cond
);end defun
อีก 2 อย่างลองไปเขียนเพิ่มเองนะ
มาดูงานที่ต้องทำหลังสุดคือหาเส้นทางที่จะดำเนินการลองใช้วิธี
depth-first search
(defun search (start goal path)
(cond ((null start) nil)
((equal start goal) (reverse (cons start path)))
((not (member start path :test #'equal))
(or (search (farmer-with-him start) goal (cons start path))
(search (farmer-with-wolf start) goal (cons start path))
(search (farmer-with-goat start) goal (cons start path))
(search (farmer-with-cabbage start) goal (cons start path))))))
code LISP ทั้งหมดยังไม่ได้ทดลองวิ่ง (Run) ใครเอาไปเขียนแล้วติดปัญหาหรือมี error ก็ post มาบอกได้นะ และลองไปค้นหาเส้นทางแบบ breadth-first search ดูด้วยนะ