อัลกอริทึม SMAWKเป็นอัลกอริทึมสำหรับค้นหาค่าต่ำสุดในแต่ละแถวของเมทริก ซ์โมโนโทนทั้งหมดที่กำหนดโดยปริยาย อัลกอริทึม นี้ตั้งชื่อตามอักษรย่อของผู้คิดค้นทั้งห้าคน ได้แก่Peter Shor , Shlomo Moran , Alok Aggarwal, Robert Wilber และMaria Klawe ^{[ 1 ]}

สำหรับวัตถุประสงค์ของอัลกอริธึมนี้ เมทริกซ์จะถูกนิยามว่าเป็นเมทริกซ์โมโนโทน หากค่าต่ำสุดของแต่ละแถวอยู่ในคอลัมน์ที่เท่ากับหรือมากกว่าคอลัมน์ของค่าต่ำสุดในแถวก่อนหน้า และจะเป็นเมทริกซ์โมโนโทนโดยสมบูรณ์ หากคุณสมบัติเดียวกันนี้เป็นจริงสำหรับทุกเมทริกซ์ย่อย (ซึ่งกำหนดโดยเซตย่อยใดๆ ของแถวและคอลัมน์ของเมทริกซ์ที่กำหนด) หรือกล่าวอีกนัยหนึ่ง เมทริกซ์จะเป็นเมทริกซ์โมโนโทนโดยสมบูรณ์ หากไม่มีเมทริกซ์ย่อยขนาด 2×2 ใดที่มีค่าต่ำสุดของแถวอยู่ในมุมบนขวาและมุมล่างซ้าย อาร์เรย์Monge ทุกตัว เป็นเมทริกซ์โมโนโทนโดยสมบูรณ์ แต่ในทางกลับกันนั้นไม่จำเป็นเสมอไป

สำหรับอัลกอริทึม SMAWK เมทริกซ์ที่จะค้นหาควรถูกกำหนดเป็นฟังก์ชัน และฟังก์ชันนี้จะถูกส่งเป็นอินพุตให้กับอัลกอริทึม (พร้อมกับมิติของเมทริกซ์) จากนั้นอัลกอริทึมจะประเมินฟังก์ชันเมื่อใดก็ตามที่ต้องการทราบค่าของเซลล์เมทริกซ์เฉพาะ หากการประเมินนี้ใช้เวลาO ( 1 ) แล้ว สำหรับเมทริกซ์ที่มีrแถวและcคอลัมน์ เวลาในการทำงานและจำนวนการประเมินฟังก์ชันจะเป็นO ( c (1 + log( r / c ))) ทั้งคู่ ซึ่งเร็วกว่า เวลา O ( r/ c ) ของอัลกอริทึมแบบง่ายที่ประเมินเซลล์เมทริกซ์ทั้งหมด มาก

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

การประยุกต์ใช้หลักของวิธีนี้ที่นำเสนอในเอกสารต้นฉบับโดย Aggarwal et al. อยู่ในเรขาคณิตเชิงคำนวณในการค้นหาจุดที่ไกลที่สุดจากแต่ละจุดของรูปหลายเหลี่ยมนูน และในการค้นหารูปหลายเหลี่ยมที่ล้อมรอบอย่างเหมาะสม การวิจัยในภายหลังพบการประยุกต์ใช้อัลกอริทึมเดียวกันนี้ในการแบ่งย่อหน้าเป็นบรรทัด [ ^{2 ] การ} ทำนายโครงสร้างทุติยภูมิของ RNA ^{[ 3 ]}การจัดเรียงลำดับDNAและโปรตีน^{[ 4 ] [ 5 ]}การสร้างรหัสคำนำหน้า^{[ 6 ]}และการกำหนดเกณฑ์ภาพ^{[ 7 ]}และอื่นๆ