DTS 11-16-09-2552

การค้นหาข้อมูล (Searching)

การค้นหาข้อมูล (Searching)

การค้นหา คือ การใช้วิธีการค้นหากับโครงสร้างข้อมูล เพื่ือดูว่าข้อมูลตัวที่ต้องการถูกเก็บอยู่ในโครงสร้างแล้วหรือยัง

การค้นหาข้อมูล searching แบ่งเป็น 2 ประเภท
1.การค้นหาข้อมูลแบบภายใน
2.การค้นหาข้อมูลแบบภายนอก

การค้นหาแบบเชิงเส้นหรือการค้นหาตามลำดับ (Linear)

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

การค้นหาแบบเซนทินัล (Sentinel)

มี ลักษณะเช่นเดียวกับการค้นหาแบบเชิงเส้น แต่ประสิทธิภาพดีกว่าตรงที่เปรียบเทียบค่าน้อยครั้งกว่าการค้นหาแบบเชิงเส้น มีวิธีโดยการเพิ่มพื้นที่ที่เก็บข้อมูลอีก 1 ที่ แล้วนำข้อมูลที่ต้องการค้นหาไปใส่ไว้ที่ต้น หรือท้ายอาเรย์ แล้วทำการตรวจสอบ ถ้าตำแหน่งที่พบเท่ากับ n-1 แสดงว่าหาข้อมูลไม่พบ นอกนั้นถือว่าพบข้อมูลที่ต้องการค้นหา

การค้นหาแบบไบนารี (Binary Search)

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


----------------------------------------------------------------------------------------------------------------------------------------

DTS 10-09-09-2552

กราฟ(ต่อ)

การท่องไปในกราฟ

1.การค้นหาแบบกว้าง จะมีการกำหนดจุดเริ่มต้น แล้วท่องไปยังโหนดประชิดของจุดเริ่มต้นไปเรื่อยๆจนครบทุกโหนด
- การค้นหาแบบกว้าง ในกราฟไม่มีทิศทาง โหนดที่พบมีได้หลายรายการแล้วแต่ลำดับของโหนดประชิดที่ได้จัดเรียงไว้
- การค้นหาแบบกว้าง ในกราฟมีทิศทาง การค้นหาโหนดทำได้ง่ายขึ้น โดยใช้คิวเก็บลำดับของโหนดประชิด และใช้ตารางเก็บค่าโหนดประชิด
2.การค้นหาแบบลึก ต้องมีการกำหนดจุดเริ่มต้นสำหรับเยี่ยมเป็นจุดแรก มีหลักการคล้ายกับแบบลำดับของทรี

กราฟ มีน้ำหนัก หมายถึง กราฟที่ทุกเอดจ์ มีค่าน้ำหนักกำกับ ซึ่งค่าน้ำหนักอาจสื่อถึงระยะทาง เวลา ค่าใช้จ่าย เป็นต้น นิยมนำไปใช้

แก้ปัญหาหลัก ๆ 2 ปัญหา คือ
1. การสร้างต้นไม้ทอดข้ามน้อยที่สุด
(Minimum Spanning Trees :MST)
1. เรียงลำดับเอดจ์ ตามน้ำหนัก
2. สร้างป่าที่ประกอบด้วยต้นไม้ว่างที่มีแต่โหนด และไม่มีเส้นเชื่อม
3. เลือกเอดจ์ที่มีน้ำหนักน้อยที่สุดและยังไม่เคยถูกเลือกเลย ถ้ามีน้ำหนักซ้ำกันหลายค่าให้สุ่มมา 1เส้น
4. พิจารณาเอดจ์ที่จะเลือก ถ้านำมาประกอบในต้นไม้ทอดข้ามน้อยที่สุดแล้วเกิด วงรอบ ให้ตัดทิ้งนอกนั้นให้นำมาประกอบเป็นเอดจ์ในต้นไม้ทอดข้ามน้อยที่สุด
5. ตรวจสอบเอดจ์ที่ต้องอ่านในกราฟ ถ้ายังอ่านไม่
หมดให้ไปทำข้อ 3

2. การหาเส้นทางที่สั้นที่สุด (Shortest path) Dijkstra’s Algorithm
หาเส้นทางที่สั้นที่สุดจากโหนดต้นทางไปโหนดใด ๆ ในกราฟ มีน้ำหนัก และน้ำหนักไม่เป็นลบ
ข้อกำหนด
ให้ เซต S เก็บโหนดที่ผ่านได้และมีระยะทางห่างจากจุดเริ่มต้นสั้นที่สุด
ให้ W แทนโหนด นอกเซต S
ให้ D แทนระยะทาง (distance) ที่สั้นที่สุดจากโหนดต้นทางไปโหนดใด ๆ ในกราฟ โดยวิถีนี้ประกอบด้วย โหนดในเชต
ให้ S ถ้าไม่มีวิถี ให้แทนด้วยค่าอินฟินีตี้ (Infinity) : ∞

Sorting

การเรียงลำดับ (sorting) เป็นการจัดให้เป็นระเบียบมีแบบแผน ช่วยให้การค้นหาสิ่งของหรือข้อมูล ซึ่งจะสามารถกระทำได้รวดเร็วและมีประสิทธิภาพ เช่น การค้นหาคำตามตัวอักษรไว้อย่างมีระบบและเป็นระเบียบ หรือ การค้นหาหมายเลขโทรศัพท์ในสมุดโทรศัพท์ ซึ่งมีการเรียงลำดับ ตามชื่อและชื่อสกุลของเจ้าของโทรศัพท์ไว้ ทำให้สามารถค้นหา หมายเลขโทรศัพท์ของคนที่ต้องการได้อย่างรวดเร็ว เป็นต้น

วิธีการเรียงลำดับสามารถแบ่งออกเป็น 2 ประเภท คือ
(1)การเรียงลำดับแบบภายใน (internal sorting)เป็นการเรียงลำดับที่ข้อมูลทั้งหมดต้องอยู่ในหน่วยความจำหลัก เวลาที่ใช้ในการเรียงลำดับจะคำนึงถึงเวลาที่ใช้ในการเปรียบเทียบและเลื่อนข้อมูลภายในความจำหลัก
(2) การเรียงลำดับแบบภายนอก(external sorting) เป็นการเรียงลำดับข้อมูลที่เก็บอยู่ในหน่วยความจำสำรอง ซึ่งเป็นการเรียงลำดับข้อมูลในแฟ้มข้อมูล (file) เวลาที่ใช้ในการเรียงลำดับต้องคำนึงถึงเวลาที่เสียไประหว่างการถ่ายเทข้อมูลจากหน่วยความจำหลักและหน่วยความจำสำรองนอกเหนือจากเวลาที่ใช้ในการเรียงลำดับข้อมูลแบบภายใน

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


การเรียงลำดับแบบฟอง (Bubble Sort)เป็นวิธีการเรียงลำดับที่มีการเปรียบเทียบข้อมูลในตำแหน่งที่อยู่ติดกัน
1. ถ้าข้อมูลทั้งสองไม่อยู่ในลำดับที่ถูกต้องให้สลับตำแหน่งที่อยู่กัน
2. ถ้าเป็นการเรียงลำดับจากน้อยไปมากให้นำข้อมูลตัวที่มีค่าน้อยกว่าอยู่ในตำแหน่งก่อนข้อมูลที่มีค่ามาก ถ้าเป็นการเรียงลำดับจากมากไปน้อยให้นำข้อมูล ตัวที่มีค่ามากกว่าอยู่ในตำแหน่งก่อนข้อมูลที่มีค่าน้อย
*การจัดเรียงลำดับแบบฟองเป็นวิธีที่ไม่ซับซ้อนมากนัก เป็นวิธีการเรียงลำดับที่นิยมใช้กันมากเพราะมีรูปแบบที่เข้าใจง่าย แต่ประสิทธิภาพการทำงานค่อนข้างต่ำพอ ๆ กับการเรียงลำดับแบบเลือกในหัวข้อที่ผ่านมา


การเรียงลำดับแบบแทรก (insertion sort)เป็นวิธีการเรียงลำดับที่ทำการเพิ่มสมาชิกใหม่เข้าไปในเซต ที่มีสมาชิกทุกตัวเรียงลำดับอยู่แล้ว และทำให้เซตใหม่ที่ได้นี้มีสมาชิกทุกตัวเรียงลำดับด้วย วิธีการเรียงลำดับจะ
1. เริ่มต้นเปรียบเทียบจากข้อมูลในตำแหน่งที่ 1 กับ 2หรือข้อมูลในตำแหน่งสุดท้ายและรองสุดท้ายก็ได้ถ้าเป็นการเรียงลำดับจากน้อยไปมาก
2. จะต้องจัดให้ข้อมูลที่มีค่าน้อยอยู่ในตำแหน่งก่อนข้อมูลที่มีค่ามาก และถ้าเรียงจากมากไปน้อยก็จะจัดให้ข้อมูลที่มีค่ามากอยู่ในตำแหน่งก่อน


การเรียงลำดับแบบฐาน (radix sort)เป็นการเรียงลำดับโดยการพิจารณาข้อมูลทีละหลัก
1. เริ่มพิจารณาจากหลักที่มีค่าน้อยที่สุดก่อน นั่นคือถ้าข้อมูลเป็นเลขจำนวนเต็มจะพิจารณาหลักหน่วยก่อน
2. การจัดเรียงจะนำข้อมูลเข้ามาทีละตัว แล้วนำไปเก็บไว้ที่ซึ่งจัดไว้สำหรับค่านั้น เป็นกลุ่ม ๆตามลำดับการเข้ามา
3. ในแต่ละรอบเมื่อจัดกลุ่มเรียบร้อยแล้ว ให้รวบรวมข้อมูลจากทุกกลุ่มเข้าด้วยกัน โดยเริ่มเรียงจากกลุ่มที่มีค่าน้อยที่สุดก่อนแล้วเรียงไปเรื่อย ๆ จนหมดทุกกลุ่ม
4. ในรอบต่อไปนำข้อมูลทั้งหมดที่ได้จัดเรียงในหลักหน่วยเรียบร้อยแล้วมาพิจารณาจัดเรียงในหลักสิบต่อไป ทำเช่นนี้ไปเรื่อย ๆ จนกระทั่งครบทุกหลักจะได้ข้อมูลที่เรียงลำดับจากน้อยไปมากตามต้องการ
*การเรียงลำดับแบบฐานมีวิธีการที่ไม่ซับซ้อนแต่ค่อนข้างใช้เนื้อที่ในหน่วยความจำมาก เนื่องจากการจัดเรียงแต่ละรอบจะต้องเตรียมเนื้อที่สำหรับสร้างที่เก็บข้อมูลในแต่ละกลุ่ม

DTS 09-02-09-2552

Tree(ทรี) (ต่อ)

เอ็กซ์เพรสชันทรี (Expression Tree)
เป็นการนำเอาโครง สร้างทรีไปใช้เก็บนิพจน์ทางคณิตศาสตร์โดยเป็นไบนารีทรี ซึ่งแต่ละโหนดเก็บตัวดำเนินการ (Operator) และและตัวถูกดำเนินการ(Operand) ของนิพจน์คณิตศาสตร์นั้น ๆ ไว้ หรืออาจจะเก็บค่านิพจน์ทางตรรกะ (Logical Expression)นิพจน์เหล่านี้เมื่อแทนในทรีต้องคำนึงลำดับขั้นตอนในการคำนวณตาม ความสำคัญของเครื่องหมายด้วยโดยมีความสำคัญตามลำดับดังนี้

- ฟังก์ชัน
- วงเล็บ ( )
- ยกกำลัง
- เครื่องหมายหน้าเลขจำนวน
- คูณ หรือ หาร * /
- บวก หรือ ลบ + -
- ถ้ามีเครื่องหมายที่ระดับเดียวกันให้ทำจากซ้ายไปขวา
การ แทนนิพจน์ในเอ็กซ์เพรสชันทรี ตัวถูกดำเนินการจะเก็บอยู่ที่โหนดใบส่วนตัวดำเนินการจะเก็บในโหนดกิ่งหรือ โหนดที่ไม่ใช่โหนดใบเช่น นิพจน์ A + B สามารถแทนในเอ็กซ์เพรสชันทรีได้ดังนี้

ไบนารีเซิร์ชทรี
ไบนารีเซิร์ชทรี (Binary Search Tree) เป็นไบนารีทรีที่มีคุณสมบัติที่ว่าทุก ๆ โหนดในทรี ค่าของโหนดรากมีค่ามากกว่าค่าของทุกโหนดในทรีย่อยทางซ้าย และมีค่าน้อยกว่าหรือเท่ากับค่าของทุกโหนดในทรีย่อยทางขวาและในแต่ละทรีย่อย ก็มี คุณสมบัติเช่นเดียวกัน


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


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

ขั้นตอนวิธีดึงโหนดออกอาจแยกพิจารณาได้ 3 กรณีดังต่อไปนี้

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

- ถ้าโหนดที่มาแทนที่เป็นโหนดที่เลือกจากทรีย่อยทางซ้ายต้องเลือกโหนดที่มีค่ามากที่สุดในทรีย่อยทางซ้ายนั้น
- ถ้าโหนดที่จะมาแทนที่เป็นโหนดที่เลือกมาจากทรีย่อยทางขวา ต้องเลือกโหนดที่มีค่าน้อยที่สุดในทรีย่อยทางขวานั้น

Graph

นิยามของกราฟกราฟ
เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้นที่ประกอบ ด้วยกลุ่มของสิ่งสองสิ่งคือ
(1) โหนด (Nodes) หรือ เวอร์เทกซ์ (Vertexes)
(2) เส้นเชื่อมระหว่างโหนด เรียก เอ็จ (Edges)กราฟที่มีเอ็จเชื่อมระหว่างโหนดสองโหนดถ้าเอ็จไม่มีลำดับ ความสัมพันธ์จะเรียกกราฟนั้นว่ากราฟแบบไม่มีทิศทาง (Undirected Graphs) และถ้ากราฟนั้นมีเอ็จที่มีลำดับความสัมพันธ์หรือมีทิศทางกำกับด้วยเรียกกราฟ นั้นว่า กราฟแบบมีทิศทาง(Directed Graphs)บางครั้งเรียกว่า ไดกราฟ (Digraph)ถ้าต้องการอ้างถึงเอ็จแต่ละเส้นสามารถเขียนชื่อเอ็จกำกับไว้ก็ได้

การแทนกราฟในหน่วยความจำ

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

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