DTS 11-16-09-2552

สรุป Searching

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


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

ตัวอย่าง เช่น มีข้อมูลอยู่ 10 จำนวน ดังนี้

18 3 39 70 27 8 1 31 2 50

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


การค้นหาแบบเซนทินัล(Sentinel)
เป็นวิธีที่การค้นหาแบบเดียวกับวิธีการค้นหาแบบเชิงเส้นแต่ประสิทธิภาพดีกว่า
ตรงที่เปรียบเทียบน้อยครั้งกว่า วิธีการ คือ
1. เพิ่มขนาดของแถวลำดับ ที่ใช้เก็บข้อมูลอีก 1 ที่
2. นำข้อมูลที่จะใช้ค้นหาข้อมูลใน Array ไปฝากที่ต้นหรือ ท้าย Array
3. ตรวจสอบผลลัพธ์จากการหา โดยตรวจสอบจากตำแหน่งที่พบ ถ้าตำแหน่งที่พบมีค่าเท่ากับ n-1แสดงว่าหาไม่พบนอกนั้นถือว่าพบข้อมูลที่ค้าหา




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

สูตรในการค้นหาตำแหน่งตัวเเทน คือ
mid = (low+high)/2mid คือ ตำแหน่งกลาง
low คือ ตำแหน่งต้นแถวลำดับ
high คือ ตำแหน่งท้ายของแถวลำดับ

DTS 10-09-09-2552

สรุป Graph (ต่อ) และ Sorting

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

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

1. การท่องแบบกว้าง (breadth first traversal)
วิธีนี้ทำโดยเลือกโหนดที่เป็นจุดเริ่มต้น ต่อมาให้เยือนโหนดอื่นที่ใกล้กันกับโหนดเริ่มต้นทีละระดับจนกระทั่งเยือนหมดทุกโหนดในกราฟ

2. การท่องแบบลึก (depth first traversal)
การทำงานคล้ายกับการท่องทีละระดับของทรี โดยกำหนดเริ่มต้นที่โหนดแรกและเยือนโหนดถัดไปตามแนววิถีนั้นจนกระทั่งนำไปสู่ปลายวิถีนั้น จากนั้น ย้อนกลับ (backtrack) ตามแนววิถีเดิมนั้น จนกระทั่งสามารถดำเนินการต่อเนื่องเข้าสู่แนววิถีอื่น ๆ เพื่อเยือนโหนดอื่น ๆ ต่อไปจนครบทุกโหนด



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

2.การหาเส้นทางที่สั้นที่สุด
ข้อกำหนดเซต S เก็บโหนดที่ผ่านได้และมีระยะทางจากจุดเริ่มต้นสั้นสุดให้ W แทนโหนดนอกเซตให้ D แทนระยะทางขั้นตอนการทำงาน
- เซต S คือจุดเริ่มต้น
- คำนวณหาระยะทางจากโหนดเริ่มต้นไปยังทุกโหนด โดยยอมให้โหนดในเซต S เป็นทางผ่าน
* ถ้าโหนดในเซต S ที่เป็นทางผ่านมีมากกว่า 1 ให้เลือกระยะทางที่สั้นที่สุดไปใส่ใน D
- เลือกโหนด W ที่ห่างจากจุดเริ่มต้นน้อยที่สุดไปไว้ใน S


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

วิธีการเรียงลำดับ

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

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


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

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

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

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

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

DTS 09-02-09-2552

สรุป TREE (ต่อ) และ Graph


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

1.ฟังก์ชัน
2.วงเล็บ
3.ยกกำลัง
4.เครื่องหมายหน้าเลขจำนวน
5.คูณหรือหาร
6.บวกหรือลบ
7.ถ้ามีเครื่องหมายที่ระดับเดียวกันให้ทำจากซ้ายไปขวา



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

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

ก. กรณีโหนดที่จะดึงออกเป็นโหนดใบ
ข. กรณีโหนดที่ดึงออกมีเฉพาะทรีย่อยทางซ้ายหรือทรีย่อยทางขวาเพียงด้านใดด้านหนึ่ง
ค. กรณีโหนดที่ดึงออกมีทั้งทรีย่อยทาง





Graph
กราฟ เป็นโครสร้างข้อมูบแบบไม่ใช่เชิงเส้น ที่ประกอบ ด้วยกลุ่มของสิ่งสองสิ่งคือ
(1) โหนด (Nodes) หรือ เวอร์เทกซ์(Vertexes)
(2) เส้นเชื่อมระหว่างโหนด เรียก เอ็จ (Edges)

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

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

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

การท่องไปในกราฟ
การท่องไปในกราฟ (graph traversal) คือ กระบวนการเข้าไปเยือนโหนดในกราฟ
โดยมีหลักในการทำงานคือ แต่ละโหนดจะถูกเยือนเพียงครั้งเดียว
สำหรับการท่องไปในทรีเพื่อเยือนแต่ละโหนดนั้นจะมีเส้นทางเดียว
แต่ในกราฟระหว่างโหนดอาจจะมีหลายเส้นทาง

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

1. การท่องแบบกว้าง (breadth first traversal)
วิธีนี้ทำโดยเลือกโหนดที่เป็นจุดเริ่มต้น ต่อมาให้เยือนโหนดอื่นที่ใกล้กันกับโหนดเริ่มต้นทีละระดับจนกระทั่งเยือนหมดทุกโหนดในกราฟ


2. การท่องแบบลึก (depth first traversal)
การทำงานคล้ายกับการท่องทีละระดับของทรี โดยกำหนดเริ่มต้นที่โหนดแรกและเยือนโหนดถัดไปตามแนววิถีนั้นจนกระทั่งนำไปสู่ปลายวิถีนั้น จากนั้น ย้อนกลับ (backtrack) ตามแนววิถีเดิมนั้น จนกระทั่งสามารถดำเนินการต่อเนื่องเข้าสู่แนววิถีอื่น ๆ เพื่อเยือนโหนดอื่น ๆ ต่อไปจนครบทุกโหนด