Search Strategies (in Thai)

การค้นหา

สมชาย แสงอำนาจเดช

การค้นหาเป็นงานพื้นฐานอย่างหนึ่งในการใช้คอมพิวเตอร์ มาช่วยแก้ปัญหา บทความนี้จะพูดถึงเรื่องการค้นเทคนิคต่างๆซึ่ง จะรวมการค้นอย่าง ละเอียด แบบฮูริสติก และการค้นแบบขยาย และต่อกิ่ง โดยใช้ตัวอย่างปัญหาการหาเส้นทางที่สั้นที่สุดด้วย คอมพิวเตอร์ ปัญหาคือเส้นทางใดคือเส้นทางที่มีระยะทางสั้นที่สุดระหว่างเ มืองที่เป็นจุดเริ่มต้นและเมืองที่เป็นจุดหมาย โดยมีระยะทางระหว่างเมืองต่างๆ แสดงในกราฟภาพที่ 1 ต่อไปนี้

ภาพที่ 1 ข้อมูลจากจุดเริ่มต้นเมือง S ไปสู่เมืองเป้าหมาย G เขียนในรูปกราฟ

แต่ละจุดเมืองเรียกว่า โนด (node หรือ vertices) และเส้น ที่ต่อระหว่างเมืองว่า ลิงค์ (links หรือ arcs) ที่แต่ละโนดจะมีคำ อธิบายกำกับ เรียกว่าเลเบล (labels หรือ descriptors) และใน การค้น (state space search) จะใช้คำอธิบายหรือเลเบลนี้ใน ระหว่างกระบวนการแก้ปัญหา

การใช้คอมพิวเตอร์ในการแก้ปัญหาจะต้องใช้การเขียนสิ่งทด แทน (representation) ของกราฟเพื่อให้คอมพิวเตอร์เข้าใจ วิธี การทำโดยเปลี่ยนเป็นรูปตาราง (matrix method) ซึ่งจะเป็นการ เตรียมโครงสร้างของข้อมูล (data structure) ให้กับคอมพิวเตอร์ โดยค่าในตารางที่ Mij คือค่าระยะห่างระหว่างโนด i และโนด j ข้อมูลที่อยู่ในรูปตารางนี้ยังสามารถเพิ่มข้อมูลทั้งในแถวและ ในคอลัมน์ได้ด้วย อัลกอริธึมในการค้นจะเปลี่ยนชนิดของการค้นเป็นแบบแผน ภูมิ ต้นไม้ (tree search) โดยเริ่มพิจารณาว่าแต่ละจุดว่าสามารถ ไปที่จุดไหนต่อได้บ้าง ดังภาพที่ 2 และ 3

ภาพที่ 2 การสร้างแผนภูมิต้นไม้การค้น (search tree) จากจุดเริ่มต้น S สามารถไปยังจุด A, B, และ E

ภาพที่ 3 จากแต่ละจุดคือ A, B, และ E จะขยายต่อไปยังจุดต่างๆในระดับ ที่สอง

โนดเริ่มต้นจะเรียกว่าเป็นโนดพ่อแม่ (parent node) และเรียก โนดที่แตกออกมาว่าเป็นโนดลูก (child node) ถ้าโนดพ่อแม่มี โนดลูกเท่ากับ b เรียกว่ามีแฟคเตอร์การแตกกิ่งเท่ากับ b (branching factor = b) ถ้าทุกเส้นทางสมบูรณ์ที่ระดับเดียวกัน (ระดับ d) จะมีเส้นทางทั้งหมดเท่ากับ bd

ในแต่ละเส้นทางขยายต่อไปจนถึงจุดหมาย G จึงจะหยุด เส้นทางที่ยังไม่ถึงจะขยายต่อไป การสร้างแผนภูมิต้นไม้การค้นหา (search tree) จากกราฟ โดยเทคนิคข้างต้น เรียกว่า การค้นหาไปในแนวกว้างก่อน (breadth-first search) คือโนดจะถูกขยายต่อๆไปตามลำดับที่โนด ถูกสร้างขึ้น คือโนด A จะขยายไปโนด B, C, D แล้วจึงย้อนกลับ ไปโนด B จากนั้นจากโนด B ไป A, C, E นั่นคือการค้นไปแนว กว้างก่อน ข้อด้อยของวิธีดังกล่าวคือ แต่ละเส้นทาง (route) การค้น ยังคงค้างไม่สิ้นสุด ทำให้เส้นทาง (route) ต่างๆจำนวนมาก จะต้องถูกเก็บในหน่วยความจำไว้ก่อนเพื่อรอการขยายต่อไป อีกเทคนิคของการค้นคือการค้นลงลึกก่อน (depth-first search) วิธีนี้จะขยายต่อๆไปจากโนดที่สร้างใหม่ล่าสุดจนถึง จุดหมาย วิธีนี้มีข้อดีคือไม่สนใจจำนวนโนดที่ขยายลงไปพบและ ระยะทางที่ลงไปจนเสร็จสิ้น นอกจากนี้ยังใช้หน่วยความจำใน การเก็บเส้นทางต่างๆน้อยลง การค้นทั้งแบบแนวลึกก่อน (depth-first search) หรือแนว กว้างก่อน (breadth-first search) เป็นเทคนิคการค้นแบบบอด (blind search technique) คือการค้นประเมินทุกเส้นทางอย่าง เป็นระบบ ในกระบวนการคิดของมนุษย์ถ้าให้ค้นหาเส้นทางก็จะมีการ ประเมินและเลือกว่าจะเลือกไปเส้นทางไหนต่อไป โดยพิจารณา ว่าเส้นทางไหนจะนำไปใกล้เป้าหมายมากกว่า และจะไม่เลือกไป เส้นทางที่ทำให้เดินย้อนกลับหรือไกลจากเป้าหมายไปอีก

วิธีค้นอีกเทคนิคหนึ่งคือ การค้นแบบฮูริสติก (heuristic search methods) วิธีนี้จะใช้ข้อมูลจำเพาะต่อโดเมน (domainspecific information) มาใช้แก้ปัญหา แม้ว่าวิธีฮูริสติกอาจจะ ไม่ช่วยแก้ปัญหาเสมอไปแต่จะช่วยให้อัลกอริธึมที่ใช้แก้ปัญหาได้ เร็วยื่งขึ้นกว่าการค้นบอด (blind search) วิธีฮูลิสติกนี้มีวัตถุประสงค์หลักคือการลดขนาดสิ่งที่จะค้นหา (search space) โดยไปลดการเลือกไปในเส้นทางที่ไม่น่าจะใช่ หรือไม่น่าจะเกี่ยวข้อง ในตัวอย่างการใช้ฮูริสติกในการหาเส้นทางที่สั้นที่สุดนี้ คือการเลือกเส้นทางที่ทำให้การค้นหาใกล้เป้าหมาย โดยอาจมีการให้ข้อมูลเพิ่มเติม เป็นข้อมูลระยะทางโดย ประมาณจากโนดหนึ่งๆไปยังโนดเป้าหมาย (โดยจะเป็นค่าโดย ประมาณที่ไม่จำเป็นต้องเป็นค่าที่ถูกต้องแน่นอน) ต่อไปนี้เป็น ตัวอย่างของวิธีฮูริสติก 1. การปีนขึ้นเขาแบบง่าย (Simple hill-climbing) เป็น อัลกอริธึมการค้นชนิดที่ให้ข้อมูลแบบฮูริสติก (heuristicallyinformed search algorithm) วิธีการนี้จะไม่สำรวจเส้นทางใด ถ้าเส้นทางนั้นไม่ทำให้กาารค้นเข้าใกล้เมืองเป้าหมายมากขึ้น 2. วิธีปีนเขาที่ขึ้นสูงชัน (steepest-ascent hill-climbing) จัดเป็น hill climbing แบบหนึ่ง เป็นวิธีที่จะเลือกสิ่งที่ดีที่สุดใน ระดับขั้นนั้นๆก่อนที่ไปสู่ขั้นต่อไปและจะตัดสินใจจากโนดลูก (child nodes) ทั้งหมดที่สร้างออกมาแล้ว เมื่อเส้นทางขยายไป จนพบจุดหมายแล้วก็เก็บค่าต่ำสุดไว้ แล้วก็ไปค้นในส่วนที่ยังไม่ ได้สำรวจแล้วหาดูว่ามีเส้นทางอื่นใดที่สั้นกว่าค่าที่ได้ก่อนนั้นหรือ ไม่ 3. การค้นแบบลำแสง (beam search) เมื่อพิจารณาวิธีการ ค้นแนวลึกก่อน หรือแนวกว้างก่อนจะเห็นว่าจะขยายเส้นทาง ไปทีละโนด วิธีที่เสริมขึ้นมานี้คือค้นแบบลำแสงนี้จะค้นไปทีละ สองโนดหรือมากกว่าสองโนดพร้อมๆกัน ถ้าความกว้างของ ลำแสง (beam width) เท่ากับสอง การค้นจะขยายทีละสองโนด ในแต่ละระดับ

กลวิธีการค้นแบบที่เหมาะสม (optimal search strategies) เป็นวิธีที่จะใช้ค่าใช้จ่ายหรือระยะจริงของแต่ละเส้นทางที่ได้ จนถึงปัจจุบันเป็นแนวทางที่จะเลือกเส้นทางที่จะขยายต่อไปในแต่ ละระดับ (จะเห็นว่าวิธีแบบนี้คล้ายกับวิธีคิดของมนุุษย์) 1. วิธีแตกและต่อกิ่งก้าน (branch-and-bound) ในวิธีนี้ จากโนดจะขยายต่อไปเหมือนกับการแตกกิ่งก้าน (branching) แล้วกระโดดไปเส้นทางที่มีระยะทางรวมจริง (actual cost) น้อย ที่สุดเหมือนกับการไปต่อกิ่ง (binding) วิธีนี้ยังเรียกอีกอย่างว่า การค้นหาสิ่งที่ดีที่สุดเป็นอันดับแรก (best-first search) 2. อัลกอริธึม A* จัดเป็นการค้นแบบวิธีแตกและต่อกิ่งก้าน ที่มีข้อเสริมขึ้นมา คือจะมีการลบเส้นทางที่ซ้ำซ้อน และมีการใช้ ค่าประมาณระยะทางที่ยังเหลืออยู่ วิธีการ วิธีการค้นแบบนี้ทำโดยแต่ละโนดจะมีค่า x/y กำกับ x คือ ค่าประมาณระยะทางที่เหลืออยู่บวกกับค่าระยะทาง รวมจริงในเส้นทางที่มาจนถึงโนดนั้น y คือ ค่าระยะทางรวมจริงในเส้นทางที่มาจนถึงโนดนั้น 1. จะขยายเส้นทางจาก โนดที่มีค่า x น้อยที่สุดไปก่อน (ที่โนด E ในภาพที่ 4) 2. เมื่อขยายไปแล้ว ถ้า node ที่มาถึงมีค่า x มากกว่า (หรือ เท่ากับ) การไปที่โนดนั้นโดยเส้นทางอื่นในระดับก่อนหน้านี้ เช่น ในตัวอย่างข้างต้น ที่ได้ดังภาพที่ 4 นี้จะเห็นว่าเมื่อขยายไปใน ระดับที่สองจะพบโนด B อีกครั้ง

ซึ่งโนดนี้สามารถไปถึงได้ ตั้งแต่ในระดับที่หนึ่งคือ จาก S ไป B โดยตรง และที่ระดับนั้นมีค่า x น้อยกว่า (หรือเท่ากัน) ดังนั้น เส้นทางที่ มาถึงโนดเหล่านี้จึงเป็นเส้นทางที่ยาวกว่า ดังนั้นจะไม่ ขยายต่อไป จากเส้นทางนี้และจะถูกตัดออกจากแผนภูมิต้นไม้ สำหรับค้น (search tree)

ภาพที่ 4 การค้นตามวิธีของ อัลกอริธึม A

3. จากนั้นก็พิจารณาเส้นทางที่เหลือที่มีโนดที่มีค่า x น้อย สุดแล้วทำซ้ำข้อ 1 และ 2 ข้างต้นไปเรื่อยๆจนในที่สุดมาถึงโนด จุดเป้าหมายก็หยุดแล้วเก็บค่าระยะทางทั้งหมดที่ได้จากเริ่มต้นจน ถึงจุดหมายตามเส้นทางนี้ ภาพที่ 5 แตกแขนงกิ่งต่อจากภาพที่ 4 ในเส้นทาง SEFG พบจุดหมายด้วย ระยะทางเท่ากับ 16 เก็บค่านี้ไว้ก่อน ค้นในเส้นทางอื่นที่เหลืออยู่

4. ไปสำรวจเส้นทางจากโนดที่เหลืออยู่และทำตามข้อ 1 -3 ถ้าพบว่าเส้นทางใหม่มีระยะสั้นกว่าที่บันทึกเก็บค่าไว้จะลบเส้นทา งที่เก็บไว้ 5. เส้นทางใดที่โนดเป้าหมายมีค่า x/y น้อยที่สุดเป็นเส้น ทางของคำตอบของการค้นหานี้

สรุปการค้น 1. กราฟประกอบด้วยโนดที่เชื่อมต่อกันด้วยลิงค์(หรืออาร์ค) ปัญหาทางชีวสารสนเทศศาสตร์ที่จะแก้ไขด้วยคอมพิวเตอร์สามารถ เปลี่ยนให้อยู่ในรูปของกราฟเพื่อวัตถุประสงค์ของการค้นหา 2. การค้นหาจากกราฟอาจใช้วิธีค้นหาอย่างละเอียด (exhaustive method) หรือวิธีฮูริสติก (heuristic method) โดย วิธีการค้นหาอย่างละเอียดปกติจะค้นไปตามแผนภูมิต้นไม้อย่าง เป็นระบบโดยจะใช้การค้นลงลึกเป็นอันดับแรกหรือค้นแนวกว้าง เป็นอันดับแรกก็ได้ ส่วนวิธีฮิวลิสติกต้องอาศัยข้อมูลที่จำเพาะต่อ โดเมน (domain-specific) มาเป็นแนวทางในการค้นตัวอย่างเช่น ใช้ค่าประมาณระยะทางที่เหลือจากจุดโนดนั้นๆ ไปยังจุดเป้าหมาย 3. วิธีฮิลล์ไคลมมิงเป็นวิธีค้นแบบฮูริสติกที่นิยม ซึ่งมีสอง แบบคือ แบบง่าย (simple) และแบบชันขึ้นสูงสุด (steepestascent) การใช้วิธีฮิลล์ไคลมมิงอาจไม่ได้เส้นทางที่เหมาะสมแต่วิธี แตกและต่อกิ่งที่มีวิธีการตัดโนดที่ซ้ำซ้อนออกไปและใช้ระยะที่ เหลืออยู่เป็นข้อมูลช่วยทำให้ได้เส้นทางที่เหมาะสม