Graph
กราฟ (Graph) เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้น อีกชนิดหนึ่ง กราฟเป็นโครงสร้างข้อมูลที่มีการนำไปใช้ในงานที่เกี่ยวข้องกับการแก้ปัญหาที่ค่อนข้างซับซ้อนเช่น การวางข่าย งานคอมพิวเตอร์ การวิเคราะห์เส้นทางวิกฤติ และปัญหาเส้นทางที่สั้นที่สุด เป็นต้น
การท่องไปในกราฟ
1. การค้นหาแบบกว้าง (Breadth-first Search)
2. การค้นหาแบบลึก (Depth-first Search)
การท่องไปในกราฟ
1. การค้นหาแบบกว้าง (Breadth-first Search)กำหนดจุดเริ่มต้น ถ้าให้เริ่มต้นที่จุด A การค้นหาจะเริ่มต้นที่โหนดประชิดของ A จนครบทุกจำนวนของโหนดประชิดจากภาพที่ปรากฏต่อไปนี้ โหนด N1 โหนด N2 ไปเรื่อย ๆจนจบที่โหนด Nk การค้นหาแบบกว้างจะค้นหาต่อที่โหนดประชิดของ N1 ซึ่งเป็นโหนด ประชิดแรกของโหนด Aแบบแผนการค้นหา จะเป็นแบบเดียวกับโหนด A หลังจากเสร็จสิ้นการค้นหาจะดำเนินการค้นหาต่อที่ โหนด N2 จนสุดท้ายจบที่ โหนด Nk ในหารค้นหาแบบกว้างจะใช้คิวเก็บลำดับ
ของโหนด ที่ต้องการค้นหาต่อไป
1.1 การค้นหาแบบกว้าง ในกราฟไม่มีทิศทาง รายชื่อโหนดที่พบจากการค้นหาแบบกว้าง มีได้หลายรายการขึ้นกับลำดับการเรียงโหนดประชิดดังตารางต่อไปนี้ แสดงค่าโหนดประชิดของโหนดทุกโหนด ซึ่งสร้างมาจากกราฟถ้ากำหนดให้เริ่มต้นค้นที่โหนด 1 รายชื่อ
โหนดที่พบเรียงตามลำดับดังนี้ 2 3 4 5 6 7 และ 8ถ้ากำหนดให้เริ่มต้นค้นที่โหนด 6 รายชื่อโหนดที่พบเรียงลำดับดังนี้ 4 8 1 7 5 2 และ 3
1.2 การค้นหาแบบกว้าง ในกราฟมีทิศทาง การค้นหาโหนดในกราฟทำได้ง่ายขึ้นถ้าใช้คิวเก็บลำดับของโหนดประชิดที่ต้องเยี่ยมต่อไป และใช้ตารางเก็บค่าโหนดประชิดของโหนดทุกโหนดในกราฟ การค้นหาแบบกว้างในกราฟจะพบโหนดตามลำดับดังนี้ A F C B D G E J และ K
2. การค้นหาแบบลึก (Depth-first Search)
จะต่างตรงที่จุดเริ่มต้นที่จะไปเยี่ยมโหนดในกราฟมีหลายจุด จึงต้องกำหนดจุดเริ่มต้นสำหรับเยี่ยมเป็นจุดแรก การค้นหาแบบลึกใช้หลักการคล้ายแบบลำดับของต้นไม้จากภาพในตัวอย่างต่อไปจะใช้โหนด A เป็นจุดเริ่มต้น การค้นหาจะเริ่มจากโหนดประชิดค่าแรกของโหนด A คือโหนด N1 แล้วดูว่าโหนดN1 มีโหนดประชิดหรือไม่ถ้ามีก็ค้นหาต่อไป โดยใช้แบบแผนการค้น เหมือนโหนด A จนครบ แล้ว
กลับไปค้นหาที่โหนดประชิดตัวที่ 2 ของโหนด A คือ โหนด N2 โดยใช้แบบแผนการค้นเดียวกับโหนด N1 ทำแบบเดียวกันจนครบถึงโหนด Nk
กราฟ มีน้ำหนัก หมายถึง กราฟที่ทุกเอดจ์ มีค่าน้ำหนักกำกับ ซึ่งค่าน้ำหนักอาจสื่อถึงระยะทาง เวลา ค่าใช้จ่าย เป็นต้น นิยมนำไปใช้
แก้ปัญหาหลัก ๆ 2 ปัญหา คือ
1. การสร้างต้นไม้ทอดข้ามน้อยที่สุด
(Minimum Spanning Trees :MST)
2. การหาเส้นทางที่สั้นที่สุด
(Shortest path)
1. การสร้างต้นไม้ทอดข้ามน้อยที่สุด
(Minimum Spanning Trees :MST)
Kruskal’s Algorithm
1. เรียงลำดับเอดจ์ ตามน้ำหนัก
2. สร้างป่าที่ประกอบด้วยต้นไม้ว่างที่มีแต่โหนด และไม่มีเส้นเชื่อม
3. เลือกเอดจ์ที่มีน้ำหนักน้อยที่สุดและยังไม่เคยถูกเลือกเลย ถ้ามีน้ำหนักซ้ำกันหลายค่าให้สุ่มมา 1เส้น
4. พิจารณาเอดจ์ที่จะเลือก ถ้านำมาประกอบในต้นไม้ทอดข้ามน้อยที่สุดแล้วเกิด วงรอบ ให้ตัดทิ้งนอกนั้นให้นำมาประกอบเป็นเอดจ์ในต้นไม้ทอดข้ามน้อยที่สุด
5. ตรวจสอบเอดจ์ที่ต้องอ่านในกราฟ ถ้ายังอ่านไม่หมดให้ไปทำข้อ 3
6. เลือกเอดจ์ที่เหลือและมีน้ำหนักน้อยที่สุดมา ตามตัวอย่าง คือ edges(6,7) edges (3,4 ) edges (5,6 ) นำมาเชื่อมต่อต้นไม่ในป่า
7. เลือกเอดจ์ที่เหลือและมีน้ำหนักน้อยที่สุด ตามตัวอย่าง คือ edges (5,7) จากนั้นให้ตัดทิ้งไม่นำมาเชื่อมต่อต้นไม้ในป่า เนื่องจากทำให้เกิดวงรอบ
8. เลือกเอดจ์ที่เหลือและมีน้ำหนักน้อยที่สุด ตามตัวอย่าง คือ edges (1,4) จากนั้นให้ตัดทิ้งไม่นำมาเชื่อมต่อต้นไม้ในป่า เนื่องจากทำให้เกิดวงรอบ
9. เลือกเอดจ์ที่เหลือและมีน้ำหนักน้อยที่สุดมา ตามตัวอย่าง คือ edges(3,5) นำมาเชื่อมต่อต้นไม่ในป่า เนื่องจากเป็นเอดจ์สุดท้าย
2. การหาเส้นทางที่สั้นที่สุด (Shortestpath) Dijkstra’s Algorithmหาเส้นทางที่สั้นที่สุดจากโหนดต้นทางไปโหนด
ใด ๆ ในกราฟ มีน้ำหนัก และน้ำหนักไม่เป็นลบ
การคำนวณหาระยะทางสั้นที่สุด จากโหนดต้นทางคือโหนด 1
ไปยังโหนดใด ๆ มีวิธีคำนวณดังนี้
1) เริ่มต้นโหนดที่เป็นจุดเริ่มต้น คือ โหนด 1 ไปไว้ที่เซต Sจากนั้นนำค่าน้ำหนักบนเอดจ์ (1,2) เอดจ์ (1,4) เอดจ์ (1,5)
และ เอดจ์ (1,6) ไปเขียนในตารางสำหรับ โหนด 3 ไม่ได้ เชื่อมต่อกับโหนดที่ 1 ดังนั้นจึงใช้ค่าอินฟินีตี้ (Infinity) แทน แสดงในตารางที่ปรากฏในบรรทัดIter= Initial
2) เลือก W ที่มีระยะทางสั้นที่สุด คือ โหนด 2 ไปไว้ที่เซต Sคำนวณ ระยะทางใหม่ ระยะทางสั้นที่สุด จากโหนด 1 ไปโหนด
อื่น ๆ เท่าเดิม ยกเว้นโหนด 3 ซึ่งขณะนี้มีวิถีกับโหนด 1 ดังนี้ (1,2,3) ระยะทางที่ได้มาจากน้ำหนักบนเอจน์เป็น (1,2) และ เอดจ์ (2,3)รวมกันคือ 70 จึงเขียนค่า 70 แทนค่าอินฟินีตีเดิม
3) เลือก W ที่มีระยะทางสั้นที่สุดคือโหนด 5 ไปไว้ที่เซต Sคำนวณหาระยะทางใหม่ปรากฏว่าถึงแม้จะมีโหนด 5 อยู่ในวิถีเส้นทางใหม่ แต่ระยะทางจากวิถีเดิมสั้นกว่า จึงคงค่าเดิมไว้ดังแสดงในตาราง
4) เลือก W ที่มีระยะทางสั้นที่สุดคือโหนด 4 ไปไว้ที่เซต Sคำนวณหาระยะทางใหม่ปรากฏว่า มีวิถีจากโหนด 1 ไปโหนด
3 รวม 2 วิถีดังนี้
วิถีที่ 1 คือ (1,2 และ3) มีค่าน้ำหนัก = 30+40 =70
วิถีที่ 2 คือ (1,4 และ3) มีค่าน้ำหนัก = 50+10 =60
เลือกน้ำหนักจากวิถีที่สั้นที่สุด คือ 60 ไปเขียนแทนค่าเดิม
5) เลือก W ที่มีระยะทางสั้นที่สุดคือโหนด 3 ไปไว้ที่เซต Sคำนวณหาระยะทางใหม่ปรากฏว่า มีวิถีจากโหนด 1 ไปโหนด 3
สมัครสมาชิก:
ส่งความคิดเห็น (Atom)
ไม่มีความคิดเห็น:
แสดงความคิดเห็น