ต้นไม้ครอบคลุมขั้นต่ำที่มีความจุ คือ ต้นไม้ครอบคลุมที่มีต้นทุนน้อยที่สุดของกราฟที่มีโหนดรากที่กำหนดไว้และเป็นไปตามข้อจำกัดด้านความจุ ข้อจำกัดด้านความจุนี้รับประกันว่า ต้นไม้ย่อยทั้งหมด (กราฟย่อยสูงสุดที่เชื่อมต่อกับโหนดรากด้วยขอบเดียว) ที่เชื่อมต่อกับโหนดรากจะมีโหนดไม่เกินหากโหนดของต้นไม้มีน้ำหนัก ข้อจำกัดด้านความจุอาจถูกตีความได้ดังนี้: ผลรวมของน้ำหนักในต้นไม้ย่อยใดๆ จะต้องไม่มากกว่าขอบที่เชื่อมต่อกราฟย่อยกับโหนดรากเรียกว่าเกตการค้นหาคำตอบที่เหมาะสมที่สุดเป็น ปัญหา NP- hard ^{[ 1 ]}${\displaystyle r}$${\displaystyle c}$${\displaystyle r}$${\displaystyle c}$${\displaystyle c}$

สมมติว่าเรามีกราฟที่มีรากเป็นให้เป็นโหนดอื่นๆ ทั้งหมดในให้เป็นต้นทุนของขอบระหว่างจุดยอดและซึ่งประกอบกันเป็นเมทริกซ์ต้นทุน ${\displaystyle G=(V,E)}$${\displaystyle n=|G|}$${\displaystyle r\in G}$${\displaystyle a_{i}}$${\displaystyle G}$${\displaystyle c_{ij}}$${\displaystyle a_{i}}$${\displaystyle a_{j}}$${\displaystyle C={c_{ij}}}$

วิธีการฮิวริสติกของ Esau-Williams ค้นหา CMST ที่ไม่เหมาะสมซึ่งใกล้เคียงกับคำตอบที่ถูกต้องมาก แต่โดยเฉลี่ยแล้ว EW ให้ผลลัพธ์ที่ดีกว่าวิธีการฮิวริสติกอื่นๆ หลายวิธี

ในขั้นต้น โหนดทั้งหมดเชื่อมต่อกับโหนดราก (กราฟรูปดาว) และต้นทุนของเครือข่ายคือ; แต่ละขอบเหล่านี้เป็นประตู ในแต่ละรอบการทำซ้ำ เราจะค้นหาเพื่อนบ้านที่ใกล้ที่สุดสำหรับทุกโหนดในและประเมินฟังก์ชันการแลกเปลี่ยน: เราจะมองหาค่าที่มากที่สุดในบรรดาการแลกเปลี่ยนที่เป็นบวก และหากซับทรีที่ได้ไม่ละเมิดข้อจำกัดด้านความจุ ให้ลบประตู ที่เชื่อมต่อซับทรีที่ กับโดยใช้ขอบเราจะทำซ้ำการทำซ้ำจนกว่าเราจะไม่สามารถปรับปรุงต้นไม้ได้อีกต่อไป ${\displaystyle r}$${\displaystyle \displaystyle \sum _{i=0}^{n}c_{ri}}$${\displaystyle a_{j}}$${\displaystyle G-{r}}$${\displaystyle t(a_{i})=g_{i}-c_{ij}}$${\displaystyle t(a_{i})}$${\displaystyle g_{i}}$${\displaystyle i}$${\displaystyle a_{j}}$${\displaystyle c_{ij}}$

ฮิวริสติกส์ของ Esau-Williams สำหรับการคำนวณ CMST ที่ไม่เหมาะสม:

ฟังก์ชัน CMST( c , C , r ): T = { , , ..., } ในขณะที่มีการเปลี่ยนแปลง: สำหรับแต่ละโหนด= โหนดที่ใกล้ที่สุดในซับทรีที่แตกต่างกัน = - t_max = max ( ) k = iโดยที่= t_max ถ้า ( cost (i) + cost (j) <= c ) T = T - T = Tยูเนียนส่งคืนT${\displaystyle c_{1r}}$${\displaystyle c_{2r}}$${\displaystyle c_{nr}}$${\displaystyle a_{i}}$${\displaystyle a_{j}}$${\displaystyle t(a_{i})}$${\displaystyle g_{i}}$${\displaystyle c_{ij}}$${\displaystyle t(a_{i})}$${\displaystyle t(a_{i})}$${\displaystyle g_{k}}$${\displaystyle c_{kj}}$

เห็นได้ชัดว่า EW สามารถหาคำตอบได้ในเวลาที่เป็นพหุนาม

^{[ 2 ]}

ฮิวริสติกของ Ahuja ^{[ 3 ]}ใช้การค้นหาในพื้นที่ใกล้เคียงการแลกเปลี่ยนหลายรายการขนาดใหญ่จากโซลูชันเริ่มต้นแบบ สุ่มโลภ

วิธีแก้ปัญหาเบื้องต้นได้มาจากการใช้เวอร์ชันสุ่มของ Esau-Williams การสุ่มทำได้โดยการเลือกผลลัพธ์ที่ดีที่สุดแบบสุ่มอย่างสม่ำเสมอในแต่ละขั้นตอน แทนที่จะเลือกผลลัพธ์ที่ดีที่สุดเพียงผลลัพธ์เดียว ${\displaystyle p}$

ให้เป็นคำตอบเริ่มต้นที่มีรากเป็นบริเวณใกล้เคียงประกอบด้วยการรวมกันใดๆ ของโหนดเดี่ยวหรือซับทรี (ซับทรีทั่วไป ไม่ใช่แบบที่กล่าวไว้ในบทนำของบทความนี้) ที่แทนที่โหนดหนึ่งในส่วนประกอบที่แตกต่างกันของโดยที่โครงสร้างที่ถูกแทนที่คือตัวแทนที่ถัดไป ตัวแทนที่ตัวแทนที่ตัวแทนที่ตัวแรก ไม่มีส่วนประกอบดั้งเดิมใดที่มีตัวแทนที่มากกว่าหนึ่งตัว และความจุจะไม่เกินในส่วนประกอบที่ได้ ${\displaystyle T}$${\displaystyle r}$${\displaystyle T\setminus r}$

กราฟการปรับปรุงเป็นเครื่องมือที่ใช้ในการค้นหาบริเวณใกล้เคียงขนาดใหญ่ได้อย่างมีประสิทธิภาพ เส้นทางในกราฟการปรับปรุงสอดคล้องกับการเปลี่ยนแปลงของวิธีการแก้ปัญหา และต้นทุนของเส้นทางคือการเปลี่ยนแปลงของต้นทุนของวิธีการแก้ปัญหาเมื่อทำการเปลี่ยนแปลงนั้น กราฟการปรับปรุงในที่นี้เป็นมัลติกราฟแบบมีทิศทางที่สร้างขึ้นโดยใช้โหนดแต่ละโหนด 2 ชุด และมีขอบได้สูงสุด 4 ขอบจากโหนดใดๆ ไปยังโหนดใดๆ ในส่วนประกอบที่แตกต่างกันขอบแต่ละขอบสอดคล้องกับการเปลี่ยนแปลงของการลบโหนดออกจากส่วนประกอบเดิมและแทนที่ด้วยซับทรีที่มีรากอยู่ที่โหนดนั้นในส่วนประกอบเป้าหมาย การรวมโหนดและซับทรีเข้าด้วยกันจะทำให้ได้ขอบที่เป็นไปได้ 4 ขอบจะมีอยู่หากการเปลี่ยนแปลงที่เกี่ยวข้องไม่ทำให้ส่วนประกอบเป้าหมายเกินความจุ ต้นทุนของขอบคือความแตกต่างของต้นทุนของต้นไม้แผ่ขยายขั้นต่ำบนจุดยอดในส่วนประกอบเป้าหมายก่อนและหลังการเคลื่อนย้าย ดังนั้นเพื่อนบ้านในการค้นหาแบบโลคอลจึงสอดคล้องกับวงจรในกราฟการปรับปรุงที่มีโหนดจากแต่ละส่วนประกอบอย่างมากที่สุดหนึ่งโหนด ${\displaystyle i',i''}$${\displaystyle i\in V(T)}$${\displaystyle T\setminus r}$${\displaystyle i',j''}$${\displaystyle i}$${\displaystyle j}$${\displaystyle i'}$${\displaystyle i''}$

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

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

ปัญหา CMST มีความสำคัญในการออกแบบเครือข่าย: เมื่อ ต้องเชื่อมต่อ คอมพิวเตอร์ ปลายทางจำนวนมาก เข้ากับฮับกลาง การกำหนดค่าแบบดาวมักไม่ใช่การออกแบบที่มีต้นทุนต่ำที่สุด การค้นหา CMST ที่จัดระเบียบเทอร์มินัลเป็นเครือข่ายย่อยสามารถลดต้นทุนในการสร้างเครือข่ายได้