pythainlp/thai_wikipedia_clean_20230101 huggingface dataset:
การเข้ารหัสของซาวเดกซ์ของเดตช์-โมโคทอฟฟ์นั้น เริ่มจากรับอินพุทที่เป็นคำ (สตริง) และจะแปลงตัวอักษรเหล่านั้นออกมาเป็นเอาต์พุตซึ่งเป็นตัวเลข 6 หลัก แต่ละตัวเลขจะบ่งบอกถึงการออกเสียงของตัวอักษรในคำนั้น ถ้าหากว่าเข้ารหัสแล้วได้ตัวเลขไม่ถึง 6 ตัว ก็จะใช้วิธีเติม 0 ต่อท้ายให้ครบแทน หรือถ้าหากว่ามีอักษรที่ต้องออกเสียงมากกว่า 6 ตัว ก็จะเลือกเอา 6 ตัวที่สำคัญที่สุด
ตารางนี้จะเป็นตารางที่บอกว่าสำหรับการออกเสียงแบบใด จะสามารถเข้ารหัสออกมาได้เป็นตัวเลขไหน ซึ่งตัวอักษรตัวเดียวกันอาจทำหน้าที่คนละอย่าง และออกเสียงได้ต่างกันอีกด้วย จึงได้มีการแยกเป็นกรณีไว้
ตัวอย่างการใช้.
ALPERT : A เป็นสระก็จริง แต่ทำหน้าที่เป็นพยัญชนะต้น จึงเข้ารหัสได้เป็น 0 8 7 9 3 0
BREUER : E และ U เป็นสระก็จริง แต่ในกรณีนี้เมื่อมีสระ 2 ตัว อยู่ด้านหน้าสระอีกตัวหนึ่ง แสดงว่าสระนั้นจะต้องมีการออกเสียง จึงเข้ารหัสได้เป็น 7 9 1 9 0 0
HABER :เป็นตัวอักษร H แต่ทำหน้าที่เป็นพยัญชนะต้น จึงเข้ารหัสได้เป็น 5 7 9 0 0 0
MANHEIM : แม้จะเป็นตัวอักษร H และไม่ได้เป็นอักษรที่ขึ้นต้นคำ แต่ก็ออกเสียงเป็นพยัญชนะต้นของพยางค์หลัง จึงเข้ารหัสได้เป็น 665600
ข้อสรุป.
ซาวเดกซ์ของเดตช์และโมโคทอฟฟ์นับเป็นขั้นตอนวิธีที่มีประโยชน์มากต่อการเก็บชื่อที่สำคัญๆ มีการประยุกต์ใช้ในหลายๆด้าน อาทิเช่น การทำสำมะโนครัว หรือในโรงพยาบาลบางแห่งยังใช้วิธีนี้ในการเก็บชื่อยาอีกด้วย
หลวงพ่อจง พุทธสโร
ชาช่ามารุ
วิธีการลอกแบบ มีมีติกอัลกอริทึม
การค้นหาเฉพาะที่
การค้นหาเฉพาะที่  เป็นกลวิธีในการใช้ค้นหาคำตอบแบบหนึ่ง จากเซตของผลเฉลยที่มีขนาดใหญ่มากๆ ซึ่งเป็นไปไม่ได้ที่จะตรวจสอบผลเฉลยทั้งหมดเพื่อให้เจอผลเฉลยที่ดีที่สุด โดยจะมีฟังก์ชันต้นทุนสำหรับพิจารณาแต่ละผลเฉลย เพื่อเปลี่ยนแปลงสถานะของผลเฉลยปัจจุบันที่ค้นหา ไปจนกว่าจะเจอผลเฉลยที่เราพอใจ
ขั้นตอนวิธีการค้นเฉพาะที่นี้ยังเป็นกลวิธีในการแก้ปัญหาการหาค่าเหมาะที่สุดเชิงการจัด (combinatorial optimization problem) ซึ่งเป็นปัญหาเอ็นพีแบบยาก (NP-hard) อีกทั้งยังถูกนำไปประยุกต์ใช้ในหลากหลายวงการ ซึ่งสามารถหาผลเฉลยที่ดีได้สำหรับปัญหาที่พบในทางปฏิบัติ
กระบวนการทำงาน.
ขั้นตอนวิธีการค้นเฉพาะที่จะเริ่มต้นจาก s โดยเป็นผลเฉลยหนึ่งที่อยู่ใน S โดย S เป็นเซตของผลเฉลยที่เป็นไปได้ทั้งหมดของปัญหา แล้วค่อยๆ ตรวจสอบผลเฉลยที่ไม่ห่างไกลจาก s มากไปเรื่อยๆ ว่ามีผลสัมฤทธิ์ที่ดีขึ้นหรือไม่ โดยเราจะมีฟังก์ชัน f(s) สำหรับใช้การคำนวณต้นทุนของผลเฉลย s ฟังก์ชันนี้จะใช้เป็นดัชนีชี้วัดความเหมาะสมของแต่ละผลเฉลย
รหัสเทียมข้างต้นเป็นแนวการทำขั้นตอนวิธีการค้นหาเฉพาะที่ โดยเริ่มต้นจะเริ่มจาก initialSolution แล้วทำงานแบบวนซ้ำสำหรับในการหาผลเฉลยที่เป็นเพื่อนบ้านกับ s คือ s' โดยมีฟังก์ชัน select เป็นตัวเลือกตัวที่พิจารณา หากผลเฉลย s' ดีกว่า s ก็จะแทนที่ s ด้วย s' โดยมี accept เป็นตัวตัดสินว่าจะยอมรับ s' หรือไม่ การทำซ้ำนี้จะทำไปเรื่อยๆ จนกว่าความเหมาะสมของ s ที่ได้เราพอใจ
ขั้นตอนวิธีการค้นหาเฉพาะที่นี้มีหัวใจสำคัญอยู่ที่ฟังก์ชันต้นทุน หากกำหนดดีๆ การค้นหาคำตอบก็จะมีประสิทธิภาพ
ลักษณะการค้นหาเฉพาะที่นี้ ถูกนำไปใช้กับขั้นตอนวิธีเกี่ยวกับการค้นหาในแบบอื่นๆ อยู่มากมาย
วัดกลางสุรินทร์
วัดกลาง หรือ วัดกลางสุรินทร์ เป็นวัดสังกัดคณะสงฆ์มหานิกาย เขตปกครองคณะสงฆ์หนตะวันออก ภาค 11 ได้รับการพระราชทานวิสุงคามสีมา เมื่อวันที่ 12 มีนาคม พ.ศ. 2508 กำหนดเขตวิสุงคามสีมา กว้าง 15 เมตร ยาว 27 เมตร
ประวัติวัดกลางสุรินทร์.
เมืองสุรินทร์เมื่อก่อนเป็นเมืองโบราณ มีชื่อเรียกว่า คูประทาย หรือ ไผทสมัน มีกำแพงและคูล้อมชั้นใน เป็นรูปวงกลม วัดผ่าศูนย์กลางจากตะวันออกสู่ตะวันตกประมาณ 22 เส้นจากทิศเหนือจดใต้ประมาณ 26 เส้น มีกำแพงและคูชั้นนอกอีกชั้นหนึ่งเป็นรูปสี่เหลี่ยมวงรี ๆ รวมเป็นกำแพง 2 ชั้น ภูมิประเทศภายในเขตกำแพงชั้นในส่วนมากเป็นที่ลุ่ม บางแห่งมีน้ำขังอยู่ตลอดฤดูหนาว ที่เป็นเนินมีบริเวณจากซอยตาดอกทอดไปทางทิศตะวันออกจดวัดบูรพารามด้านทิศใต้แค่บริเวณถนนหลักเมือง เนินที่สูงสุดตรงบริเวณทิศใต้ตลาดเทศบาล ชาวบ้านเรียกคนแถบนี้ว่า “คุ้มโคกสูง”
วัดที่มีอยู่ในตัวเมืองสุรินทร์ ที่เป็นวัดโบราณเก่าแก่มี 9 วัด ที่สร้างขึ้นใหม่เฉพาะในเขตเทศบาลมี2 วัด วัดทั้ง 10 นี้ตั้งอยู่ดังนี้
วัดกลางและวัดบูรพาราม ตั้งอยู่ภายในเขตกำแพงชั้นใน วัดจำปา, วัดศาลาลอย วัดจุมพลสุธาวาส, วัดพรหมสุรินทร์ และวัดโคกบัวราย (ตั้งใหม่) ตั้งอยู่ภายในเขตกำแพงชั้นนอกและวัดที่ตั้งอยู่นอกกำแพงชั้นนอกมี วัดหนองบัว, วัดประทุมเมฆ และวัดเทพสุรินทร์ (สร้างใหม่) วัดทั้ง 8 ล้วนเป็นวัดโบราณไม่มีประวัติจารึกว่า วัดใดสร้างขึ้นเมื่อใดแน่นอน
อนึ่ง ภายในเขตกำแพงและคูเมืองชั้นใน มีที่พอสันนิษฐานว่า เคยเป็นวัดมาก่อน 4 แห่งคือ
การก่อตั้งวัดกลางสุรินทร์ วัดกลางสุรินทร์ ได้เริ่มสร้างขึ้นเมื่อใดใครเป็นผู้สร้าง เจ้าอาวาสองค์แรกและองค์ต่อ ๆ มามีชื่ออย่างไรบ้าง ไม่มีหลักฐานปรากฏชัดแต่สถานที่ตั้งวัดนั้นพอมีเหตุผลที่น่าเชื่อดังนี้
เมืองสุรินทร์มีกำเนิดมาแต่ครั้งใด นักประวัติศาสตร์สันนิษฐานว่า หลายร้อยปีมาแล้วโดยมีชื่อเดิมว่า ไผทสมัน ต่อมาเมื่อประมาณ พ.ศ. 2306 เชียงปุมซึ่งเดิมอยู่บ้านเมืองที ได้รับบรรดาศักดิ์เป็นพระสุรินทร์ภักดี และย้ายมาอยู่ที่ไผทสมัน เมืองนี้จึงได้ชื่อว่าเมืองสุรินทร์ ตามบรรดาศักดิ์ของเจ้าเมือง
ในการอพยบครั้งแรก สันนิษฐานว่า ได้เริ่มกำหนดตั้งสถานที่หลักเมืองขึ้นโดยถือเนื้อที่ส่วนกลางของเมืองจริง ๆ กล่าวคือประมาณอาณาเขตภายในคูกำแพงเมืองชั้นใน จากทิศตะวันออกจดทิศตะวันตก และจากทิศเหนือจดทิศใต้ มีศูนย์กลางตรงที่ตั้งหลักเมืองในปัจจุบันพอดี ถนนสายนี้เกิดขึ้นในสมัยหลัง
ส่วนจวนเจ้าเมืองนั้น ตั้งเยืองจากศาลเจ้าหลักเมืองมาทางทิศตะวันออกเฉียงเหนือตรงบริเวณตลาดเก่า ตรงหน้าวัดกลางปัจจุบัน หรือบริเวณหลังโรงแรมโมเมเรียลทั้งหมดเป็นบริเวณจวนเจ้าเมืองมาแต่เดิม แต่ปัจจุบันนี้เป็นที่ของเอกชนหมดแล้ว
วัดกลาง น่าจะเริ่มได้รับการก่อสร้างขึ้นในสมัยนี้ ทั้งนี้เนื่องจากตั้งในเนื้อที่แนวเดียวกับจวนเจ้าเมือง ด้านทิศตะวันออกขนานกับจวนเจ้าเมือง โดยมีทางขั้นกลางระหว่างจวนเจ้าเมืองกับวัด ปัจจุบันทางสายนี้ คือถนนธนสารซึ่งเป็นทางสายเดียว ที่ตัดกลางเมืองทอดจากกำแพงด้านเหนือจดด้านใต้ และมีถนนสายหลักเมืองผ่ากลางจากตะวันออกสู่ตะวันตก ตัดกันเป็นสี่แยกหลักเมือง ถนนสองสายนี้เป็นถนนดังเดิมของเมืองสุรินทร์
การวางผังเมืองของเจ้าเมืองสุรินทร์ เข้าใจว่า ได้เพ่งถึงจุดศูนย์กลางของตัวเมืองและสร้างจวนในบริเวณดังกล่าว ที่แห่งนี้เป็นเนินสูง
ข้อยืนยันว่า เจ้าเมืองสุรินทร์คนแรกเป็นผู้สร้างวัดกลางสุรินทร์ มีเหตุผลประกอบดังนี้
หลังจากเชียงปุมได้รับพระราชทานยศและตำแหน่ง กลับมาสู่บ้านเดิมที่เมืองที และเห็นว่าที่บ้านเมืองทีเป็นบ้านเล็ก ชัยภูมิไม่เหมาะสมจึงย้ายมาตั้งเมืองที่คูประทาย เมื่อกำหนดที่ตั้งจวนแล้วก็วางผังการสร้างวัดเคียงข้างกับเขตจวน ทางทิศตะวันออก
การตั้งวัดนี้ น่าจะเป็นการเลียนแบบข้าราชการทหารในสมัยนั้น ที่กลับจากการทำศึกสงครามก็มีการสร้างวัด ซึ่งการสร้างวัดนี้แม้พระบาทสมเด็จพระเจ้าอยู่หัวและพระบรมวงศานุวงศ์ก็สร้างมาก ข้าราชบริพารก็สร้างเช่นกัน จนมีคำกล่าวในสมัยนั้นว่า “สร้างวัดให้ลูกเล่น” เจ้าเมืองสุรินทร์ได้สร้างวัดขึ้นเป็นความนิยมตามสมัยนั้น เป็นการเลียนแบบจากส่วนกลางก็ได้
เจ้าเมืองอาจตั้งความประสงค์ว่า เมื่อสร้างเมืองก็สร้างวัดเป็นคู่บ้านคู่เมืองด้วย จึงกำหนดพื้นที่วัดกลางติดกับเขตจวน
การปฏิบัติราชการในสมัยนั้น ไม่มีศาลากลางเป็นเอกเทศใช้จวนเป็นที่ราชการด้วย เมื่อมีการชุมนุมเรื่องข้าราชการก็ใช้บริเวณวัดเป็นที่ชุมนุมเป็นความสะดวกสบายโดยตลอด วัดกลางได้เป็นที่ร่วมประชุมของทางราชการตลอดในสมัยนั้น รวมทั้งการระดมพล
ตามที่กล่าว ณ เบื้องต้นว่า เรื่องมีปรากฏซากอิฐเก่าที่ “โคกโพธิ์” คือบริเวณตั้งโรงเรียนราษฎร์บำรุงว่า เคยเป็นที่ตั้งวัดมาแต่เดิม เมื่อพระสุรินทร์มาสร้างเมืองแล้วเมื่อมีการวางผังเมืองและกำหนดที่วัด โดยท่านเจ้าเมืองอาจโยกย้ายวัดนี้มาตั้งเป็นวัดกลางก็ได้ ทั้งนี้โดยเหตุผลตามคติพื้นบ้านถือว่า การสร้างวัดต้องให้อยู่ทางทิศตะวันออกของหมู่บ้าน จึงจะเป็นมงคล วัดอยู่ทางทิศตะวันตกของหมู่บ้าน ถือว่าเป็นอัปมงคล วัดอยู่ทางทิศเหนือหรือใต้หมู่บ้านไม่ถือเป็นเรื่องเสียหาย อาจจะเป็นเพราะเหตุที่เจ้าเมืองสร้างจวนอยู่ทางทิศตะวันออกวัด จึงย้ายวัดจากทิศตะวันตกมาตั้งทิศตะวันออก แต่ทั้งนี้เป็นเพียงข้อสันนิษฐานอาจจะร้างไปเอง และวัดกลางก็อาจตั้งขึ้นใหม่ก็ได้ แต่เหตุผลที่ยืนยันมานั้นพอกล่าวได้ว่า วัดกลางเกิดในสมัยพระสุรินทร์คนแรกแน่นอน เพราะปรากฏเรื่องของเจ้าเมืองดังกล่าวแล้ว
วัดกลางสุรินทร์ ได้รับการพระราชทานวิสุงคามสีมา
วัดกลาง ตำบลในเมือง อำเภอเมือง จังหวัดสุรินทร์ ได้รับพระราชทานวิสุงคามสีมา ตามประกาศสำนักนายกรัฐมนตรี เรื่องพระราชทานวิสุงคามสีมา ประกาศ ณ วันที่ 12 มีนาคม พ.ศ. 2508 ผู้รับสนองพระบรมราชโองการ จอมพลถนอม กิตติขจร นายกรัฐมนตรี ประกาศในราชกิจจานุเบกษา เล่มที่ 82 ตอนที่ 24 19 มีนาคม 2508 ฉบับพิเศษ หน้า 18 และบัญชีรายชื่อวัดที่ขอพระราชทานวิสุงคามสีมา งวดที่ 1 ประจำปี 2508 ลำดับที่ 94 วัดกลาง ตำบลในเมือง อำเภอเมือง จังหวัดสุรินทร์ กำหนดเขตวิสุงคามสีมา กว้าง 15 เมตร ยาว 27 เมตร ประกาศในราชกิจจานุเบกษา เล่มที่ 82 ตอนที่ 24 19 มีนาคม 2508 ฉบับพิเศษ หน้า 22
ประเพณีที่เกิดขึ้นในวัด
วัดกลางสุรินทร์มีอุโบสถ สร้างด้วยอิฐโบกปูนแบบโบราณ ไม่มีปูนซีเมนต์เช่นปัจจุบัน เป็นโครงสวยงามในสมัยโบราณมาแล้ว วัดกลางเป็นศูนย์งานราชการ เช่นการเกณฑ์คนมาเพื่อกิจอย่างใดอย่างหนึ่ง มีเกณฑ์ทหารเป็นต้น งานประเพณีของชาวบ้านที่ต้องชุมนุม และที่เกี่ยวกับด้านศาสนาดังนี้
อาณาบริเวณของวัดกลางสุรินทร์ ในสมัยก่อนมีความกว้างขวาง จดเขตติดต่อถึงวัดบูรพาราม แต่เนื่องจากความล้มลุกคลุกคลานของวัดประกอบด้วยการครอบครองที่ดินของวัดด้วยมือเปล่า เมื่อทางราชการได้มีการวางผังเมืองขึ้น ที่ดินของวัดมีสภาพรกร้างว่างเปล่าครอบครองไม่ทั่วถึง ทางราชการได้ถือเอาที่ดินทางบริเวณทิศใต้สระของวัดทั้งหมดเป็นที่ราชพัสดุของกระทรวงยุติธรรม คงปล่อยเพียงสระน้ำให้เป็นของวัด โดยที่ไม่มีใครชี้แจงคัดค้านชี้แนวเขตของวัด
ประกอบชาวเมืองสุรินทร์สมัยนั้น ก็คือชาวบ้านที่ไร้การศึกษา ไม่มีความเจริญทางภาษาที่พูด ใช้ภาษาท้องถิ่นคือภาษาเขมร ไม่มีความรู้ภาษาไทยเลย ข้าราชการในสมัยนั้นชาวบ้านรู้สึกว่าเป็นเจ้านายไม่กล้าคัดค้านถกเถียงข้าราชการ จะพูดอะไรได้ตามใจชอบเพราะพูดกันไม่รู้เรื่อง แม้ภิกษุสงฆ์ก็ไม่ต่างจากชาวบ้าน
ทำเนียบเจ้าอาวาสวัดกลางสุรินทร์ และรักษาการแทนเจ้าอาวาสวัดกลางสุรินทร์.
วัดกลางสุรินทร์ตั้งแต่สมัยแรกเริ่มการสร้างวัดเมื่อประมาณ พ.ศ. 2306-2320 แต่ไม่มีหลักฐานยืนยันว่าเจ้าอาวาสรูปแรกและต่อ ๆ มามีกี่รูปกี่สมัย มีชื่ออย่างไรบ้าง ไม่มีหลักฐานปรากฏ เพิ่งมาปรากฏในยุคหลัง ประมาณ พ.ศ. 2440 เป็นต้นมา จนถึงเจ้าอาวาสรูปปัจจุบัน มีรายนาม ตามลำดับดังนี้
ทำเนียบผู้ช่วยเจ้าอาวาสวัดกลางสุรินทร์.
พระเถระที่ได้รับตำแหน่งทางคณะสงฆ์ในระดับจังหวัด
พระเถระที่ได้รับตำแหน่งทางคณะสงฆ์ในระดับอำเภอ
พระสงฆ์ที่ได้รับตำแหน่งทางคณะสงฆ์ในระดับตำบล
พระสงฆ์ที่ได้รับตำแหน่งทางคณะสงฆ์ในระดับพระเลขานุการ
เสนาสนะของวัดกลางสุรินทร์.
ทางวัดกลางสุรินทร์ได้พยายามก่อสร้างเริ่มสร้างบูรณะเท่าที่เป็นไปได้ แต่วัดมีอุปสรรคที่แก้ไม่ได้ เพราะเหตุการณ์และสถานที่ไม่อำนวย เช่น เหตุการณ์ที่เกี่ยวกับอัคคีภัยเมื่อต้นปี พ.ศ. 2516 ทำให้วัดกลางสุรินทร์ตกอยู่ในสภาพเหมือนวัดสร้างใหม่ ไม่มีความสะดวกในการบำเพ็ญศาสนกิจ แม้สถานศึกษาของพระภิกษุสามเณรก็ต้องปลูกปรำเรียน ทั้ง ๆ ที่วัดอยู่กลางใจเมือง เท่ากับเป็นการประจานน้ำใจของพุทธศาสนิกชนของชาวจังหวัดสุรินทร์ทั่วไปซึ่งเนื่องจากเหตุการณ์ที่ผ่านมา ที่ทางวัดยังแก้ไม่ตกที่ได้กล่าวว่าสถานที่ไม่อำนวย ก็เพราะความคับแคบของวัดไม่อาจวางผังวัดให้มีเขตเป็นพุทธาวาส สังฆาวาสให้เป็นสัดส่วนได้ แม้ในการพัฒนาวัดยังไม่สามารถทำได้เท่าที่ควร เพราะอาคารสถานที่ยังไม่พอแก่ความจำเป็น แต่ก็ได้ตั้งโครงการเพื่อการทะนุบำรุงทางศาสนาวัตถุต่อไป
เสนาสนะที่ก่อสร้างมาก่อน และยังปลอดอัคคีภัย
อาคารสถานที่สร้างหลังเกิดอัคคีภัยและสร้างใหม่ในยุคปัจจุบัน
การจัดการศึกษาจากอดีตถึงปัจจุบัน.
วัดกลางสุรินทร์ ได้เปิดการศึกษาปริยัติธรรมตั้งแต่ พ.ศ. 2481 แต่ยังไม่มั่นคงมีอุปสรรคเกี่ยวกับเรื่องครูสอนยังขาดเป็นครั้งคราว และได้เปิดทำการสอนได้มั่นคงดังนี้
วัดกลาง เป็นศูนย์การศึกษาปริยัติธรรมส่วนกลางของจังหวัด แต่ละปีมีภิกษุสามเณรร่วมเรียนเป็นจำนวนมาก อย่างเช่น
ปีการศึกษา 2519 มีจำนวนนักเรียนเข้าศึกษาเล่าเรียน โดยปริมาณดังนี้
นักธรรมทุกชั้นมีจำนวน 39 รูป เปิดเรียนเวลา 08.30-10.30 น.
ธรรมศึกษา มีจำนวนนักเรียน 42 คน เปิดเรียนเวลา 16.30-17.30 น.
แผนกบาลี มีจำนวน 92 รูป เปิดเรียนเวลา 13.00-15.00 น.
เปิดเรียนศึกษาผู้ใหญ่ มีจำนวนนักเรียน 165 รูป เปิดเรียนเวลา 16.00-19.00 น.
โรงเรียนพุทธศาสนาวันอาทิตย์ มีนักเรียน 118 คน เปิดเรียนเวลา 08.30 น.
ในทฤษฎีสารสนเทศและวิทยาการคอมพิวเตอร์ Damerau–Levenshtein distance (ตั้งตามชื่อผู้คิดค้น และ ) คือระยะทางระหว่างสองสายอักขระ ซึ่งสามารถหาได้จากจำนวนการกระทำที่น้อยที่ในการแปลงสายอักขระหนึ่งมาเป็นอีกสายอักขนะหนึ่ง โดยการกระทำที่สามารถทำกับสายอักขระได้มีสี่แบบ ดังนี้
Damerau คิดเฉพาะการสะกดผิดที่สามารถแก้ไขด้วยการกระทำเพียงครั้งเดียว ส่วนการหาระยะทางที่เกิดจากการกระทำหลายการกระทำเป็นของ Levenshtein ในชื่อ Levenshtein edit distance แต่ Levenshtein ไม่มีการกระทำสลับอักขระ เมื่อนำมารวมกันจึงได้เป็น Damerau–Levenshtein distance
ถึงแม้ตอนแรกจะใช้ในการแก้คำที่ผู้ใช้พิมพ์ผิด แต่ในปัจจุบัน Damerau–Levenshtein distance ถูกใช้ในชีววิทยาในการหาความแตกต่างระหว่างสายอักขระ DNA อีกด้วย
Damerau–Levenshtein distance เป็นการแก้ไข Levenshtein edit distance ให้มีการกระทำสลับอักขระเพิ่มขึ้น โดยสามารถนำ Levenshtein edit distance ซึ่งใช้การแก้ปัญหาโดยกำหนดการพลวัต มาแก้ไขเพิ่มเติมการกระทำได้เลย
เพิ่มการกระทำจาก Levenshtein edit distance เข้าไปอีกหนึ่งการกระทำ ดังนี้
if(i &gt; 1 and j &gt; 1 and str1[i] = str2[j-1] and str1[i-1] = str2[j]) then
d[i, j] := minimum(
d[i, j],
d[i-2, j-2] + cost "// transposition"
จะได้รหัสเทียมที่สมบูรณ์เป็น
"// สำหรับทุกๆค่า i และ j, d[i,j] จะแสดงค่าความแตกต่างระหว่างอักขระ i ตัวแรกของ s และ อักขระ j ตัวแรกของ t สังเกตว่า แถวลำดับ d จะมีขนาด (m+1)x(n+1)"
d[i, 0] := i "// ค่าความแตกต่างระหว่างข้อความแรกใดๆ กับ ข้อความที่สองที่ว่างเปล่า"
d[0, j] := j "// ค่าความแตกต่างระหว่างข้อความที่สองใดๆ กับ ข้อความแรกที่ว่างเปล่า"
d[i, j] := d[i-1, j-1] "// พิจารณาตัวถัดมา"
d[i-1, j] + 1, "// การตัดออก"
d[i, j-1] + 1, "// การแทรก"
d[i-1, j-1] + 1 "// การแทนที่"
if(i &gt; 1 and j &gt; 1 and s[i] = t[j-1] and s[i-1] = t[j]) then
d[i-2, j-2] + cost "// การสลับอักขระ"
เนื่องจากมีการวนสำหรับทุกอักขระในอักขระ "s" และ "t" จะได้ว่า ประสิทธิภาพในการทำงานเป็น formula_1 เมื่อ "m", "n" คือความยาวของสายอักขระ
Karakuri Chachamaru
Chachamaru
การจำลองการอบเหนียว
เป็นกลวิธีหนึ่งในการแก้ปัญหาการหาค่าเหมาะสมที่สุดเชิงการจัด (combinatorial optimization problem) ซึ่งมักจะใช้เมื่อปริภูมิการค้น  นั้นไม่ต่อเนื่อง การจำลองการอบเหนียวอาจจะมีประสิทธิภาพในการแก้ปัญหาในบางกรณีได้ดีกว่าการแจกแจงจนกว่าจะได้คำตอบ (exhaustive enumeration) หากว่าเป้าหมายเป็นเพียงแค่การหาคำตอบที่จะมาแก้ปัญหาได้ดีในเวลาอันจำกัด ไม่ใช่เพื่อการหาวีธีที่มีประสิทธิภาพที่สุด
ชื่อและแรงบันดาลใจนี้มาจากการอบเหนียวในโลหะวิทยา ซึ่งก็คือเทคนิคในการให้ความร้อนและการควบคุมความอุณหภูมิของโลหะเพื่อที่จะเพิ่มขนาดของผลึกและลดข้อบกพร่องของโครงสร้างของโลหะนั้น โดยความร้อนจะทำให้อะตอมหลุดออกมาจากตำแหน่งเดิมที่มันอยู่และเคลื่อนที่แบบสุ่มโดยจะมีพลังงานในระดับที่สูง การลดอุณหภูมิลงอย่างช้าๆจะทำให้อะตอมมีโอกาสมากขึ้นในการหาตำแหน่งซึ่งมีพลังงานภายในที่ต่ำกว่าเดิมโครงสร้างของโลหะจะจัดเรียงตัวอย่างเป็นระเบียบผลก็คือจะได้โลหะที่เหนียวและไม่เปราะแต่ถ้ามีการลดอุณหภูมิลงอย่างรวดเร็วหรือทำให้เย็นเร็วเกินไป ก็จะทำให้โครงสร้างของโลหะไม่สม่ำเสมอและเกิดรอยร้าวขึ้นได้
การอุปมาอุปไมยระหว่างการแก้ปัญหาแบบการหาค่าที่เหมาะที่สุดเชิงการจัดกับกระบวนการอบเหนียวในทางโลหะวิทยานั้นอธิบายได้ดังนี้ สถานะของโลหะจะแทนผลเฉลยที่เป็นไปได้สำหรับปัญหาที่ต้องการหาผลเฉลยที่เหมาะที่สุด สถานะของพลังงานจะเสมือนเป็นค่าของฟังก์ชันเป้าหมาย (Objective function) หรือฟังก์ชันต้นทุน (Cost function) ที่คำนวณได้จากผลเฉลยนั้นๆ ดังนั้นสถานะของพลังงานที่ต่ำที่สุดก็จะเปรียบเสมือนผลเฉลยที่เหมาะที่สุดของปัญหา และการทำให้เย็นลงเร็วเกินไป จะเป็นการค้นพบผลเฉลยเฉพาะพื้นที่
วิธีการจำลองการอบเหนียวนั้นถูกนำเสนอโดย Scott Kirkpatrick, C. Daniel Gelatt and Mario P. Vecchi ในปีค.ศ.1983 ซึ่งดัดแปลงมาจากขั้นตอนวิธี Metropolis-Hastings
ขั้นตอนวิธีในการทำงานจะเป็นลำดับการทำงานแบบวนซ้ำ โดยในแต่ละรอบจะประกอบด้วยการเปลี่ยนแปลงแบบสุ่มจากผลเฉลยปัจจุบันเพื่อสร้างผลเฉลยใหม่ที่ใกล้เคียงกับผลเฉลยปัจจุบัน เมื่อผลเฉลยใหม่ถูกสร้างขึ้นจะคำนวณค่าของฟังก์ชันเป้าหมายหรือฟังก์ชันต้นทุน เพื่อตัดสินใจว่าจะยอมรับให้เป็นผลเฉลยปัจจุบันหรือไม่ หากผลเฉลยใหม่ดีกว่าผลเฉลยปัจจุบันก็จะถูกยอมรับให้เป็นผลเฉลยปัจจุบันแทน แต่ถ้าผลเฉลยใหม่ไม่ดีกว่าผลเฉลยในปัจจุบันก็อาจจะถูกยอมรับได้ โดยใช้กฎบนพื้นฐานความน่าจะเป็นของโบลต์ซมันน์ (Boltzman’s probability) คือ จะมีการสุ่มตัวเลข β ในช่วง 0-1 ขึ้นมาและถ้า β≤e-ΔC/kT ก็จะยอมรับผลเฉลยใหม่ (เมื่อ ΔC คือ ผลต่างระหว่างค่าฟังก์ชันต้นทุนของผลเฉลยทั้งสองซึ่งมีค่ามากกว่าหรือเท่ากับ 0 และ T คือ อุณหภูมิ)
การเลือกพารามิเตอร์.
ในการใช้วิธีการจำลองการอบเหนียวกับการแก้ปัญหาที่เฉพาะเจาะจงอย่างใดอย่างหนึ่ง จะต้องระบุพารามิเตอร์ต่อไปนี้: ปริภูมิสถานะ, พลังงาน (เป้าหมาย) หรือฟังก์ชัน E, ฟังก์ชัน neighbour ซึ่งเอาไว้สร้างคำตอบอื่นที่เป็นไปได้ ความน่าจะเป็นที่ยอมรับได้หรือฟังก์ชัน P และตารางเวลาการหลอม temp และค่าอุณหภูมิเริ่มต้น ตัวเลือกเหล่านี้จะมีผลกระทบอย่างมากต่อประสิทธิภาพการทำงานของขั้นตอนวิธีการอบเหนียว
การเริ่มใหม่.
ในบางครั้งการเริ่มจากคำตอบเก่าที่ผ่านมาซึ่งเป็นคำตอบที่ดีกว่าคำตอบในปัจจุบันก็ดีกว่าการเริ่มที่สถานะปัจจุบันในทุกๆครั้ง กระบวนการนี้เรียกว่า การเริ่มใหม่ของการจำลองการอบเหนียว การตัดสินใจว่าจะเริ่มใหม่หรือไม่นั้นขึ้นอยู่กับปัจจัยหลายประการ ปัจจัยสำคัญอย่างหนึ่งคือการดูว่าพลังงาน ณ ปัจจุบันสูงกว่าพลังงานที่ดีที่สุดที่เราพบมาแล้วมากเกินไปหรือเปล่า
ตัวอย่างด้านล่างเป็นการนำขั้นตอนวิธีการจำลองการอบเหนียวมาใช้แก้ปัญหาการเดินทางของพนักงานขาย
tspSA( d[1..n][1..n] ) {
tour = initialTour( d )
maxT = T = tourLength(d, tour)
while ( T &gt; 0.001 ) ) {
N = maxT – T;
for (i = 1; i &lt;= N; i++) {
newTour = nextTour( minT )
dE = tourLength(d,newTour) - tourLength(d,tour)
if (dE &lt; 0 OR random(0,1) &lt; e-dE/kT ){
tour = newTour;
T *= 0.999
return tour;
โดยขั้นตอนวิธีนี้จะรับอาเรย์2มิติที่เป็นเก็บข้อมูลของจุดที่แทนเมืองต่างๆและระยะทางระหว่างเมือง
จากนั้นให้สุ่มทางเดินขึ้นมาหนึ่งทางเก็บในตัวแปร tour จากนั้นก็คำนวณหาความยาวของทางเดินนั้นเก็บในตัวแปร maxT กับ T ซึ่ง T แทนอุณหภูมิของระบบ
เราจะให้ T ที่ได้นั้นถือว่าเป็นอุณหภูมิเริ่มต้นของระบบ จากนั้นก็เข้าวงวนโดยตรวจสอบค่า T และค่า T จะลดลงเรื่อยๆ
ถ้า T ลดลงจน T≤0.001 ก็จะเลิกทำและส่งค่า tour ที่ได้กลับไป โดยในวงวนจะมีค่า N ซึ่งเป็นผลต่างระหว่าง maxT กับ T
จากนั้นจะเข้าสู่วงวน for ซึ่งจะสังเกตได้ว่ายิ่งถ้าค่า T สูงจำนวนรอบทำซ้ำจะน้อยแต่ถ้าค่า T ต่ำจำนวนรอบทำซ้ำจะเยอะ
โดยในวงวน for ก็จะคำนวณหาทางเดินถัดไป (neighbor solution)โดยเก็บค่าใส่ตัวแปร dE
โดยถ้า E เป็นจำนวนบวกแสดงว่าทางเดินใหม่ที่ได้จะยาวขึ้น ถ้า E เป็นจำนวนลบแสดงว่าทางเดินใหม่ที่ได้จะสั้นลง
จากนั้นเราก็ดูเงื่อนไขว่าถ้า dE&lt;0 หรือถ้าเราสุ่มตัวเลขที่อยู่ระหว่าง 0 กับ 1 ขึ้นมาแล้วน้อยกว่า e-dE/kT
เราก็จะรับทางเดินใหม่ให้เป็นคำตอบของเรา จะสังเกตได้ว่าถ้าค่า T สูง e-dE/kT ก็จะสูงตามไปด้วย
หมายความว่าในขณะที่อุณหภูมิสูงนั้นเราก็มีโอกาสที่จะรับคำตอบไว้เยอะเมื่ออุณหภูมิต่ำลงเราก็จะรับคำตอบน้อยลง
ชะชะมะรุ
ขั้นตอนวิธีของคริสโตไฟด์
ขั้นตอนวิธีของคริสโตไฟด์  ตั้งชื่อตาม นิคอส คริสโตฟิลด์ เป็นขั้นตอนวิธีในการแก้ปัญหาบางกลุ่มของปัญหาการเดินทางของพนักงานขาย ที่มีเส้นเชื่อมถ่วงน้ำหนักเป็นไปตามความไม่เสมอภาคของสามเหลี่ยม ซึ่งได้คำตอบที่มีอัตราส่วนการประมาณ เป็น 1.5 เท่าของคำตอบดีที่สุด
ขั้นตอนที่ 1: สร้าง ต้นไม้ทอดข้ามที่น้อยที่สุด formula_6 จาก formula_2
ขั้นตอนที่ 2: ให้ formula_8 เป็นเซตของจุดยอดที่มี ระดับขั้น เป็นจำนวนคี่ ใน formula_6 และหา การจับคู่สมบูรณ์ formula_10 ซึ่งมีน้ำหนักน้อยที่สุดใน กราฟบริบูรณ์ บนจุดยอดใน formula_8
ขั้นตอนที่ 3: รวมเส้นเชื่อมของ formula_10 และ formula_6 เป็น มัลติกราฟ formula_14
ขั้นตอนที่ 4: สร้างวงจรออยเลอร์ ใน formula_14
ขั้นตอนที่ 5: สร้างวงจรแฮมิลตัน จากขึั้นตอนที่แล้วโดยข้ามจุดยอดที่เยี่ยมชมแล้วออกไป ("shortcutting")
อัตราส่วนการประมาณ.
ผลลัพธ์ของขั้นตอนวิธีนี้มีค่าเป็น 1.5 เท่าของของคำตอบดีที่สุด
พิสูจน์ได้ดังนี้:
ให้ formula_16 แทนเซตของเส้นเชื่อมของคำตอบดีสุดของปัญหาการเดินทางของพนักงานขาย สำหรับformula_2, เนื่องจากformula_18 เชื่อมต่อกันบริบูรณ์ จึงมีต้นไม้ทอดข้ามแน่ๆ ดังนั้น formula_19
ให้ formula_20 แทนเซตของเส้นเชื่อมของคำตอบดีสุดของปัญหาการเดินทางของพนักงานขาย สำหรับกราฟบริบูรณ์ที่ใช้จุดยอดจาก formula_8, เนื่องจากน้ำหนักของเส้นเชื่อมเป็นรูปสามเหลี่ยม ไม่ว่าจะเยี่ยมชมจุดยอดเพิ่มก็ไม่ทำให้น้ำหนักลดลง (ตามสมบัติความไม่เสมอภาคของสามเหลี่ยม) ทำให้เรารู้ว่า formula_22
เราแสดงให้เห็นว่ามีการจับคู่ที่สมบูรณ์แบบของจุดยอดจากformula_8 ที่มีน้ำหนักต่ำกว่า formula_24 ซึ่งมีขอบบนเหมือนกันกับ formula_10 ( formula_10 เป็นการจับคู่สมบูรณ์ที่มีน้ำหนักน้อยที่สุด), เนื่องจาก formula_8 จะมีจำนวนจุดยอดเป็นเลขคู่ จึงมีการจับคู่สมบูรณ์แน่ๆ
ให้ formula_28 เป็นวิถีออยเลอร์ใน formula_29 แน่นอนว่า formula_30 และ formula_31 เป็นการจับคู่สมบูรณ์ และ มีเส้นเชื่อมในการจับคู่สมบูรณ์นี้ อย่างน้อยหนึ่งอันที่น้ำหนักน้อยกว่าหรือเท่ากับ formula_32
ดังนั้น จาก formula_33 และคุณสมบัติความไม่เสมอภาคของสามเหลี่ยม ทำให้ทราบว่าขั้นตอนวิธีนี้มีอัตราส่วนการประมาณ เป็น 1.5
เนื่องจากปัญหาการเดินทางของพนักงานขายอยู่ในกลุ่มปัญหาเอ็นพีบริบูรณ์ ซึ่งการจะหาคำตอบนั้นทำได้ยาก เราจึงมักใช้ขั้นตอนวิธีการประมาณในการประมาณคำตอบแทน และขั้นตอนวิธีของคริสโตไฟด์ ก็เป็นแนวทางหนึ่ง โดยมีเงื่อนไขว่าเส้นเชื่อมในกราฟนั้นจะเป็นไปตามความไม่เสมอภาคของสามเหลี่ยม ซึ่งเปรียบได้กับเมืองบนโลกจริงที่ถ้าหากมีเส้นทางจาก formula_16 ไป formula_20 และจาก formula_20 ไป formula_37 แล้ว จะมีเส้นทางจาก formula_16 ไป formula_37 ซึ่งไม่ยาวกว่าเส้นทางจาก formula_16 ไป formula_20 บวกกับเส้นทางจาก formula_20 ไป formula_37 แน่ๆ (ทางจาก formula_16 ไป formula_37 เปรียบได้กับทางลัด) ด้วยข้อกำหนดนี้ในการทำขั้นตอนที่ 2 และ 3 จะเป็นการเพิ่มเส้นเชื่อมที่จำเป็นในการหาวงจรออยเลอร์เข้าไปในกราฟ และขึ้นตอนที่ 5 ก็คือการเลือกเดินทางลัดนั่นเอง ซึ่งผลของขั้นตอนวิธีนี้ รับประกันได้ว่า ไม่แย่ไปกว่า 1.5 เท่าของคำตอบที่ดีที่สุด
เอวาจัง
การค้นหาแบบดีสตาร์
ขั้นตอนวิธีดีสตาร์  เป็นขั้นตอนวิธีที่ใช้ในการหาเส้นทางการเคลื่อนที่ของหุ่นยนต์ จัดเป็นขั้นตอนวิธีการค้นหาแบบฮิวริสติกแบบหนึ่งเพราะมีการนำเทคนิคฮิวริสติกมาใช้ ขั้นตอนวิธีดีสตาร์นี้ได้ถูกนำมาใช้อย่างแพร่หลายซึ่งขั้นตอนวิธีดีสตาร์จะทำการสร้างเส้นทางการเคลื่อนที่ที่เหมาะสมที่สุดให้การวางแผนการเคลื่อนที่ของหุ่นยนต์เป็นไปอย่างมีประสิทธิภาพ ผู้นิยามและนำเสนอขั้นตอนวิธีนี้คือ แอนโทนี สเตนซ์ ซึ่งได้สร้างและพัฒนาไว้ในปี ค.ศ. 1994 ที่มหาวิทยาลัยคาร์เนกีเมลลอน
ขั้นตอนวิธีการนี้เป็นส่วนขยายของขั้นตอนวิธีเอสตาร์ โดยสืบทอดแนวคิดโดยตรงมาจากแนวคิดของ ขั้นตอนวิธีของ Dijkstra โดยทั้งขั้นตอนวิธีเอสตาร์และขั้นตอนวิธี Dijkstra จะไม่สามารถตอบสนองต่อการเปลี่ยนแปลงในกราฟในระหว่างหรือหลังจากการขยายตัวของกระบวนการในขั้นตอนวิธี ในทั้งสองขั้นตอนวิธีนี้ที่ผู้ใช้อาจจะต้องทิ้งผลทั้งหมดและเริ่มต้นใหม่อีกครั้งเมื่อมีการเปลี่ยนแปลงเกิดขึ้น โดยเฉพาะอย่างยิ่งเมื่อทำงานร่วมกับหุ่นยนต์ภายใต้เงื่อนไขที่เป็นจริง (เช่นช่วงเซ็นเซอร์จำกัด , สภาพแวดล้อมที่ไม่คุ้นเคย)
ชื่อของขั้นตอนวิธีนี้ได้มีที่มามาจากความที่ขั้นตอนวิธีนี้เป็นขั้นตอนวิธีที่ถูกพัฒนาต่อยอดมาจากขั้นตอนวิธีเอสตาร์ซึ่งมีการเปลี่ยนแปลงให้สามารถเปลี่ยนแปลงค่าพารามิเตอร์ต่างๆในระหว่างการวิเคราะห์หาเส้นทาง ซึ่งความสามารถที่เพิ่มเข้ามานี้นั้นสามารถเรียกได้ว่ามีความเป็น "ไดนามิก" จึงเปรียบได้ว่าขั้นตอนวิธีนี้เป็นไดนามิกเอสตาร์ เราจึงตั้งชื่อของขั้นตอนวิธีนี้ว่า ขั้นตอนวิธีดีสตาร์
ทุกๆจุดที่ถูกรู้จักแล้วจะถูกนำเข้ามาเก็บไว้ใน โอเพ่นลิสต์ (เป็นรายการสำหรับเก็บจุดที่เอาไว้เก็บจุดต่างๆได้) โดยที่ตอนเริ่มต้นนั้นเราจะมีเพียงแค่จุดสุดท้ายหรือเป้าหมายซึ่งจะถูกเก็บอยู่ใน โอเพ่นลิสต์ เพียงตัวเดียว ซึ่งจนกว่าจะเจอจุดเริ่มต้นของเรา โอเพ่นลิสต์ นั้นจะถูกเพิ่มจุดและมาและนำจุดออกไปอยู่เรื่อยๆ เพื่อค้นหาเส้นทางในการเคลื่อนที่ระหว่างจุดเริ่มต้นไปยังจุดสุดท้าย
การขยายตัวของจุด.
เริ่มต้นเราตัดสินใจว่าเลือกว่าจุดปัจจุบันที่เลือกมานั้นกำลังขยายไปสู่สถานะสูงขึ้นหรือไม่(ซึ่งหลังจากนั้นจะเปลี่ยนแปลงไปสู่สถานะต่ำกว่าโดยอัตโนมัติ) ถ้าพบว่าเป็นสถานะต่ำกว่าก็จะทำงานตามขั้นตอนของขั้นตอนวิธีเอสตาร์ตามปกตินั่นคือจุดที่อยู่รอบๆจุดของเรานั้นจะถูกตรวจสอบเพื่อหาว่าจะไปต่อทางจุดไหนต่อไปถึงจะดีกว่าจุดก่อนหน้าที่เคยหาเอาไว้ ซึ่งถ้าเป็นไปตามนี้นั่นหมายถึงจุดต่างๆที่อยู่รอบจุดของเราจะถูกนำมาคำนวณหาค่าใหม่และจะถูกเพิ่มเข้าไปยัง โอเพ่นลิสต์ ด้วย แต่ถ้าพบว่าก่อนหน้านั้นเป็นสถานะสูงขึ้น ค่าของจุดเราก็จะถูกส่งผ่านโดยทันทีไปให้กับจุดต่างๆที่กำลังมองเราเป็นเป้าหมายที่อยู่รอบๆจุดเรา ซึ่งการกระทำเหล่านี้เป็นการพยายามลดค่าของจุดต่างๆให้ได้เป็นค่าที่น้อยที่สุดซึ่งเป็นการทำการหาค่าที่ดีที่สุดนั่นเอง
ตัดสินใจสถานะสูงขึ้นหรือต่ำกว่า.
การตัดสินใจนั้นจะขึ้นอยู่กับค่าปัจจุบันและค่าต่ำสุดของจุดๆนั้น ถ้าเส้นทางปัจจุบันมากกว่าค่าต่ำสุดจะถือว่าเข้าสู่สถานะสูงขึ้น และจะตามด้วยการทำการเพิ่มค่าต่อไป แต่อย่างไรก็ตามมันก็จะตรวจสอบว่าจะมีจุดใดๆที่อยู่รอบๆตัวมันหรือไม่ที่จะสามารถลดค่าให้กับจุดเราได้ ถ้าในจุดเหล่านั้นมีที่ถูกเซตและคำนวณค่าใหม่ไว้ก่อนแล้ว และถ้าทุกๆจุดที่อยู่รอบๆนั้นได้ถูกตรวจสอบแล้วและถูกตรวจสอบว่าค่าต่ำสุดตรงกับค่าปัจจุบันในกรณีนี้เราจะนำเข้าไปสู่สถานะต่ำกว่าถ้าเป็นกรณีอื่นนอกจากนี้มันจะยังคงอยู่ในสถานะสูงขึ้นและค่าของมันก็จะถูกเพิ่มขึ้น
การขยายตัวเริ่มต้น.
ขั้นตอนสิธีนี้จะเริ่มต้นโดยการวนเลือกจุดแต่บะจุดจากโอเพ่นลิสต์มาจัดการทีละตัว จากนั้นมันก็จะส่งผ่านค่าที่เปลี่ยนแปลงไปยังจุดที่อยู่รอบๆตัวและเก็บจุดรอบๆตัวนั้นไปไว้ยังโอเพ่นลิสต์ ซึ่งกระบวกการของขั้นตอนวิธีดีสตาร์นี้จะตรงกันข้ามกับขั้นตอนวิธีเอสตาร์ตรงที่การขยายตัวของจุดจะเริ่มจากจุดเป้าหมายมาสู่จุดเริ่มต้นไม่ใช่จุดเริ่มต้นไปสู้จุดเป้าหมายอย่างในขั้นตอนวิธีเอสตาร์ และจุดต่างๆที่ถูกขยายไปนั้นจะมีสิ่งที่เรียกว่าตัวชี้ย้อนกลับ(back pointer) เพื่อชี้ไปยังจุดที่อยู่ในเส้นทางจุดถัดไปซึ่งจะนำทางไปสู่จุดมุ่งหมายได้ และขั้นตอนวิธีนี้จะหยุดทางงานเมื่อจุดถัดไปที่เรียกเข้ามานั้นเป็นจุดเริ่มต้นนั่นคือสิ้นสุดการทำงานเจอเส้นทางที่ต้องการแล้วซึ่งเส้นทางนี้นั้นสามารถหาได้อย่างง่ายๆจากการไล่ค้นหาเรื่อยๆตามตัวชี้ย้อนกลับ
การจัดการสิ่งกีดขวาง.
เมื่อสิ่งกีดขวางนั้นถูกพบในระหว่างการหาเส้นทาง ทุกๆจุดที่ถูกผลกระทบจากการเปลี่ยนแปลงนี้จะถูกนำเข้ามาเก็บไว้ในโอเพ่นลิสต์และในครั้งนี้แต่ละจุดนั้นก็จะถูกทำเครื่องหมายว่าอยู่ในสถานะสูงขึ้น อย่างไรก็ตามจุดที่อยู่รอบๆก็จะถูกตรวจสอบว่าสามารถลดค่าของจุดได้หรือไม่ ถ้าไม่ก็จะส่งผ่านสถานะสูงขึ้นไปยังจุดที่เป็นจุดลูกของจุดๆนั้นซึ่งตัวชี้ย้อนกลับจะเป็นตัวชี้นั่นเอง และจะมีการสร้างเวฟขึ้นมา เมื่อจุดที่อยู่ในสถานะสูงขึ้นสามารถลดค่าได้ตัวชี้ย้อนกลับของมันก็จุดถูกอัปเดตค่าและก็จะส่งผ่านสถานะต่ำกว่าไปยังจุดที่อยู่รอบๆ ซึ่งเวฟของสถานะสูงขึ้นและต่ำกว่านั้นเป็นหัวใจที่สำคัญของขั้นตอนวิธีดีสตาร์
การเกิดสิ่งกีดขวางเพิ่มขึ้นอีก.