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

บทความต้นฉบับเขียนขึ้นในปี 1988 โดยคริส เฟอร์กูสันและริชาร์ด อี. คอร์ฟจาก ภาควิชา วิทยาการคอมพิวเตอร์มหาวิทยาลัยแคลิฟอร์เนีย ลอสแอนเจลิส พวกเขาใช้ AI เล่นหมากรุกอื่นๆ อีกหลายตัวเพื่อพัฒนาอัลกอริทึมที่มีขอบเขตกว้างขึ้นนี้

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

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

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

เมื่อกระบวนการค้นหาเสร็จสิ้น มันจะส่งสัญญาณผลลัพธ์ไปยังกระบวนการแม่ซ้ำๆ จนกว่าคำตอบย่อยต่างๆ ทั้งหมดจะถูกรวมเข้าด้วยกันและปัญหาทั้งหมดจะได้รับการแก้ไข^{[ 1 ]}

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

ตัวอย่างสำคัญประการหนึ่งของการใช้ DTS ในชีวิตประจำวันคือการกำหนดเส้นทางเครือข่าย อินเทอร์เน็ตสามารถมองได้ว่าเป็นโครงสร้างแบบต้นไม้ของที่อยู่ IPและการเปรียบเทียบกับโปรโตคอลการกำหนดเส้นทางอาจคล้ายกับวิธีการทำงานของที่ทำการไปรษณีย์ในโลกแห่งความเป็นจริง เนื่องจากปัจจุบันมีที่อยู่ IP มากกว่า 4.3 พันล้านรายการ สังคมจึงพึ่งพาเวลาที่ข้อมูลใช้ในการเดินทางไปยังปลายทางเป็นอย่างมาก ดังนั้น การกำหนดเส้นทาง IP จึงแบ่งงานออกเป็นหน่วยย่อยหลายหน่วย ซึ่งแต่ละหน่วยมีขีดความสามารถในการคำนวณที่แตกต่างกัน และใช้ผลลัพธ์ของหน่วยย่อยอื่นๆ เพื่อค้นหาเส้นทางได้อย่างมีประสิทธิภาพ นี่เป็นตัวอย่างของ DTS ที่ส่งผลกระทบต่อประชากรโลกมากกว่า 43% ด้วยเหตุผลต่างๆ ตั้งแต่ความบันเทิงไปจนถึงความมั่นคงของชาติ^{[ 2 ]}

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

หนึ่งในตัวอย่างที่เป็นข้อถกเถียงมากที่สุดคือการประมวลผลข้อมูลขนาดใหญ่ ในแอปพลิเคชันเช่นGoogle Search Engine, Facebook, YouTubeการค้นหาจำเป็นต้องได้รับการปรับให้เหมาะสมเพื่อให้เวลาในการรออยู่ในช่วงเวลาที่เหมาะสม ซึ่งสามารถทำได้โดยการใช้ DTS เพียงอย่างเดียว แต่มีการใช้อัลกอริธึมอื่นๆ แทน (เช่น การแฮชข้อมูลใน ฐานข้อมูล SQL ) หรือใช้ร่วมกัน (อัลกอริธึม Haystack ของ Facebook รวมการค้นหาแบบต้นไม้แบบขนาน การแฮชข้อมูล และการจัดเรียง/จัดลำดับหน่วยความจำ) ^{[ 3 ]}

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

ความท้าทายที่สำคัญที่สุดต่อแนวคิดเชิงอัลกอริทึมนี้คือบทความของ Kröll B เรื่อง "Balanced Distributed Search Trees Do Not Exist" ซึ่งไม่ได้โจมตีความถูกต้องหรือประสิทธิภาพในปัจจุบันของอัลกอริทึม แต่โจมตีข้อเท็จจริงที่ว่า DTS เอง ไม่ว่าจะมีการปรับปรุงมากเพียงใด (เช่น การปรับสมดุลต้นไม้ข้อมูลขาเข้าก่อน) ก็จะไม่สามารถบรรลุเวลาการแก้ปัญหาที่เหมาะสมที่สุดได้^{[ 4 ]}นี่เป็นการเปิดมุมมองใหม่: มีการใช้ทรัพยากรมากเกินไปในการพัฒนา DTS ซึ่งขัดขวางการวิจัยและพัฒนาอัลกอริทึมใหม่ที่มีศักยภาพด้านประสิทธิภาพสูงกว่าหรือไม่? ข้อจำกัดอีกประการหนึ่งของ DTS คือข้อเท็จจริงที่ว่า ไม่ว่าการแบ่ง การประสานงาน และการรวมโซลูชันจะมีประสิทธิภาพเพียงใด ก็จะถูกจำกัดด้วยจำนวนโปรเซสเซอร์และกำลังการประมวลผลของโปรเซสเซอร์เหล่านั้นเสมอ

• ต้นไม้ (โครงสร้างข้อมูล)
• ต้นไม้ค้นหา
• ต้นไม้ค้นหาแบบไบนารี
• การท่องต้นไม้
• การค้นหาต้นไม้แบบมอนเตคาร์โล
• การประมวลผลแบบขนาน

• Colbrook A., Brewer E., Dellarocas C., Weihl W., "อัลกอริทึมสำหรับต้นไม้ค้นหาบนสถาปัตยกรรมส่งข้อความ" (1996)
• Colbrook A., Smythe C., การนำโครงสร้างต้นไม้ค้นหาไปใช้อย่างมีประสิทธิภาพบนสถาปัตยกรรมหน่วยความจำแบบกระจายขนาน (1990)
• Bayer R., McCreight E., การจัดระเบียบและการบำรุงรักษาดัชนีเรียงลำดับขนาดใหญ่ Acta Informatica 1 (1972)
• Comer D., ต้นไม้บีที่พบได้ทั่วไป (1979)