อัลกอริทึมการค้นหาแบบขนาน

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

• แบ่งและพิชิต
• การค้นหาเชิงลึก - แรก
• การค้นหาแบบกว้าง - แรก
• Best-First Search

แบ่งและพิชิต

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

แนวทางการแบ่งแยกและพิชิตเกี่ยวข้องกับขั้นตอนต่อไปนี้ในแต่ละระดับ -

• Divide - ปัญหาเดิมแบ่งเป็นปัญหาย่อย

• Conquer - ปัญหาย่อยได้รับการแก้ไขแบบวนซ้ำ

• Combine - การแก้ปัญหาของปัญหาย่อยจะถูกรวมเข้าด้วยกันเพื่อหาทางออกของปัญหาเดิม

การค้นหาแบบไบนารีเป็นตัวอย่างของอัลกอริทึมการแบ่งและพิชิต

รหัสเทียม

Binarysearch(a, b, low, high)

if low < high then
   return NOT FOUND
else
   mid ← (low+high) / 2
   if b = key(mid) then
      return key(mid)
   else if b < key(mid) then
      return BinarySearch(a, b, low, mid−1)
   else
   
      return BinarySearch(a, b, mid+1, high)

การค้นหาเชิงลึก - แรก

Depth-First Search (หรือ DFS) คืออัลกอริทึมสำหรับการค้นหาต้นไม้หรือโครงสร้างข้อมูลกราฟที่ไม่มีทิศทาง ที่นี่แนวคิดคือการเริ่มต้นจากโหนดเริ่มต้นที่เรียกว่าrootและสำรวจให้ไกลที่สุดในสาขาเดียวกัน หากเราได้โหนดที่ไม่มีโหนดตัวต่อเราจะส่งคืนและดำเนินการต่อด้วยจุดยอดซึ่งยังไม่มีการเยี่ยมชม

ขั้นตอนของการค้นหาความลึก - แรก

• พิจารณาโหนด (รูท) ที่ไม่ได้เยี่ยมชมก่อนหน้านี้และทำเครื่องหมายว่าเยี่ยมชมแล้ว

• ไปที่โหนดลำดับแรกที่อยู่ติดกันและทำเครื่องหมายว่าเยี่ยมแล้ว

• หากโหนดตัวต่อทั้งหมดของโหนดที่พิจารณาถูกเยี่ยมชมแล้วหรือไม่มีโหนดตัวต่อให้กลับไปที่โหนดหลัก

รหัสเทียม

ปล่อย v เป็นจุดยอดที่การค้นหาเริ่มต้นในกราฟ G.

DFS(G,v)

   Stack S := {};
	
   for each vertex u, set visited[u] := false;
   push S, v;
   while (S is not empty) do
     u := pop S;
	  
      if (not visited[u]) then
         visited[u] := true;
         for each unvisited neighbour w of u
            push S, w;
      end if
		
   end while
   
END DFS()

การค้นหาแบบกว้าง - แรก

Breadth-First Search (หรือ BFS) เป็นอัลกอริทึมสำหรับการค้นหาต้นไม้หรือโครงสร้างข้อมูลกราฟที่ไม่ได้กำหนดทิศทาง ที่นี่เราเริ่มต้นด้วยโหนดจากนั้นไปที่โหนดที่อยู่ติดกันทั้งหมดในระดับเดียวกันจากนั้นย้ายไปยังโหนดตัวต่อที่อยู่ติดกันในระดับถัดไป นี้เรียกอีกอย่างว่าlevel-by-level search.

ขั้นตอนของการค้นหาแบบกว้าง - แรก

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

รหัสเทียม

ปล่อย v เป็นจุดยอดที่การค้นหาเริ่มต้นในกราฟ G.

BFS(G,v)

   Queue Q := {};
	
   for each vertex u, set visited[u] := false;
   insert Q, v;
   while (Q is not empty) do
      u := delete Q;
		
      if (not visited[u]) then
         visited[u] := true;
         for each unvisited neighbor w of u
            insert Q, w;
      end if
		
   end while
   
END BFS()

Best-First Search

Best-First Search คืออัลกอริทึมที่สำรวจกราฟเพื่อไปยังเป้าหมายในเส้นทางที่สั้นที่สุด ซึ่งแตกต่างจาก BFS และ DFS Best-First Search จะทำตามฟังก์ชันการประเมินเพื่อพิจารณาว่าโหนดใดเหมาะสมที่สุดในการสำรวจถัดไป

ขั้นตอนของการค้นหาที่ดีที่สุดเป็นอันดับแรก

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

รหัสเทียม

BFS( m )

   Insert( m.StartNode )
   Until PriorityQueue is empty
      c ← PriorityQueue.DeleteMin
      If c is the goal
      Exit
   Else
   
      Foreach neighbor n of c
         If n "Unvisited"
            Mark n "Visited"
            Insert( n )
      Mark c "Examined"
      
End procedure