อัลกอริทึมในการหาเส้นทางที่สั้นที่สุด
12 พ.ย. 2008 ให้ความเห็น
in Algorithm, Artificial Intelligent
อัลกอริทึมในการหาเส้นทางที่สั้นที่สุด (Shortest Paths Algorithm)
ในกราฟที่มีน้ำหนัก หากเอาไปแทนระยะทางระหว่างจังหวัดต่าง ๆ ดังตัวอย่างข้อที่ 9.5 น้ำหนักอาจหมายถึงระยะทางเป็นกิโลเมตร หรือเวลาเดินทางเป็นชั่วโมง หรือค่าตั๋วโดยสาร ฯลฯ ปัญหาลักษณะนี้จึงเป็นเรื่องที่น่าศึกษาเพื่อหาเส้นทางที่มีน้ำหนักน้อยที่สุดจากเวอร์เทกซ์ที่กำหนดไปยังเวอร์เทกซ์อื่น ๆ ทุกเวอร์เทกซ์ในกราฟที่มีเส้นทางไปถึง หรือเรียกว่า เส้นทางที่สั้นที่สุดจากจุดเดียว (Single Source Shortest Path) อัลกอริทึมที่ใช้เพื่อแก้ปัญหานี้รู้จักในชื่ออัลกอริทึมของ ดิจสตรา ( Dijkstra’ Algorithm) ซึ่งเป็นชื่อของนักคณิตศาสตร์ ชาวดัทช์ (Dutch) ผู้เสนอวิธีการแก้ปัญหานี้ในปี ค.ศ. 1959
ข้อจำกัดประการหนึ่งของอัลกอริทึมข้างต้น คือ ค่าน้ำหนักของเอดจ์ต้องมีค่าไม่น้อยกว่า 0 (Non Negative) ส่วนกราฟจะเป็นแบบมีทิศทางหรือไม่ก็ได้ แต่ต้องเป็นกราฟที่ต่อถึงกัน (Connected) กล่าวคือ จะต้องมีเส้นทาง (Path) ระหว่างทุก ๆ เวอร์เทกซ์ของกราฟ
Dijkstra’s Algorithm คล้ายกับอัลกอริทึมของการค้นหาในแนวกว้าง แต่จะต้องเพิ่มส่วนของน้ำหนักในแต่ละเวอร์เทกซ์ เพื่อแสดงน้ำหนักจากเวอร์เทกซ์ตั้งต้นจนถึงเวอร์เทกซ์นั้น เราสามารถกำหนดค่าเริ่มต้น (Initialize) ให้กับเวอร์เทกซ์ตั้งต้นให้มีน้ำหนัก 0
น้ำหนักที่เวอร์เทกซ์ใด ๆ สามารถหาได้จาการหาผลบวกของน้ำหนักเอดจ์จากเวอร์เทกซ์ตั้งต้นถึงเวอร์เทกซ์นั้น
อัลกอริทึมในการหาเส้นทางที่สั้นที่สุด จะต้องเปลี่ยนโครงสร้างคิวทั่วไปมาเป็น
Priority Queue ซึ่งเป็นคิวที่เรียงจากเวอร์เทกซ์ที่มีน้ำหนักของเวอร์เทกซ์น้อยที่สุดไปจนถึงเวอร์เทกซ์ที่มีน้ำหนักมาที่สุด อัลกอริทึมนี้ใช้แนวทางที่รู้จักกันในนาม อัลกอริทึมเชิงละโมบ
(Greedy Algorithm)
จากอัลกอริทึมในหัวข้อ 9.12 ที่ผ่านมา สามารถนำมาหาเส้นทางที่สั้นที่สุด เริ่มด้วยกำหนดค่าให้เวอร์เทกซ์ตั้งต้น ในที่นี้คือเวอร์เทกซ์ B ให้มีน้ำหนัก 0 (ศูนย์) จากนั้นให้ดำเนินการดังนี้
รอบแรก
อัลกอริทึมเพื่อการหาเส้นทางที่สั้นที่สุด
สรุปเป็นแนวทางได้ดังนี้
initMarks (graph)
clearPriorityQ (pqueue)
enPQ (pqueue, startVertex
do
dePQ (pqueue, vertex)
if (NOT vertexMarked)
markVertex (vertex)
getAdjacencyVertices (adjList)
updateVertexWeight (graph, vertex,Weight)
enPQ (pqueue, adjList)
while (NOT emptyPQ (pqueue))
วิธีการหาเส้นทางที่สั้นที่สุด
ต่อไปนี้เป็นตัวอย่าง การหาเส้นทางที่สั้นที่สุด จากกราฟที่กำหนดให้ โดยเริ่มจากเวอร์เทกซ์ B
รอบที่ 3
รอบที่ 4
รอบที่ 5
รอบที่ 6
รอบที่ 7
การค้นหาในแนวกว้าง (Breadth-First Search)
12 พ.ย. 2008 ให้ความเห็น
in Algorithm, Artificial Intelligent
การค้นหาในแนวกว้าง (Breadth-First Search)
การค้นหาแบบนี้จะค้นหาในเวอร์เทกซ์ในระดับเดียวกันก่อน โดยเริ่มจากจุดเริ่มต้นแล้วไปค้นหายังเวอร์เทกซ์ข้างเคียงทั้งหมด ก่อนที่จะลงลึกไปยังเวอร์เทกซ์ข้างเคียงในระดับถัดไปต่อไป ค้นหาไปเรื่อย ๆ จนกว่าจะพบหรือหากค้นหาจนทั่วทุกเวอร์เทกซ์แล้วไม่พบ ก็สามารถแจ้งผลให้ทราบได้
หากดูจากวิธีการค้นหาแล้ว พบว่ามีแนวทางคล้ายกับการค้นหาแบบลงลึกก่อน แต่จะต้องแก้ไขส่วนที่เก็บรายชื่อเวอร์เทกซ์ข้างเคียงจากสแตกมาเป็นคิว ทั้งนี้เพราะเราต้องค้นหาจากเวอร์เทกซ์ข้างเคียงที่เข้ามาอยู่ในรายชื่อของเวอร์เทกซ์ก่อน ซึ่งตรงกับลักษณะการทำงานแบบโครงสร้างคิวพอดี
การค้นหาในแนวลึก ( Depth – First Search)
12 พ.ย. 2008 ให้ความเห็น
in Algorithm, Artificial Intelligent
การค้นหาในแนวลึก ( Depth – First Search)
การค้นหาแบบนี้จะค้นหาเวอร์เทกซ์แบบลงลึกก่อน โดยเริ่มจากจุดเริ่มต้นแล้วลงลึกไปยังเวอร์เทกซ์ข้างเคียงในระดับถัดไปเรื่อยๆ จนกว่าจะพบ หากค้นหาจนทั่วทุกเวอร์เทกซ์แล้วไม่พบก็สามารถแจ้งผลให้ทราบได้
โครงสร้างกราฟจะแตกต่างจากโครงสร้างต้นไม้ เราสามารถเข้าถึงทุกโหนดในต้นไม้โดยเริ่มจากรูท แต่ในกราฟ เวอร์เทกซ์ทุกเวอร์เทกซ์ไม่จำเป็นต้องมีเส้นทางถึงกันหมด
ตัวอย่าง การท่องเข้าไปในกราฟมีทิศทาง
จากเวอร์เทกซ์ A จะไปยังเวอร์เทกซ์ B C D หรือ E ได้ แต่จะไปยัง เวอร์เทกซ์ F ไม่ได้
จากเวอร์เทกซ์ B จะไปยังเวอร์เทกซ์อื่นใดไม่ได้ เพราะเป็นกราฟมีทิศทาง
จากเวอร์เทกซ์ C จะไปยังเวอร์เทกซ์ C E B ได้ แต่จะไปยังเวอร์เทกซ์ A หรือ D ไม่ได้
-
-
-
อัลกอริทึมเพื่อการค้นหาในแนวลึก
สรุปเป็นแนวทางได้ดังนี้
found FALSE
clearStack (stack)
push (stack, startVertex)
do
pop (stack, vertex)
if (vertex = = targetVertex)
print vertex
found TRUE
else
print vertex
getAdjacencyVertices
push (stack, adjacency vertices)
while ((NOT emptyStack (stack)) AND (NOT found))
if (NOT found)
print “No path to target vertex”
