เนื้อหา

• แผนภูมิเปรียบเทียบ
• คำจำกัดความของการค้นหาที่มีข้อมูล
• Heuristic Depth การค้นหาครั้งแรก
• คำจำกัดความของการค้นหาที่ไม่รู้ข้อมูล
• ค้นหาความลึกครั้งแรก
• ข้อสรุป

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

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

1. 1. แผนภูมิเปรียบเทียบ
   2. คำนิยาม
   3. ความแตกต่างที่สำคัญ
   4. ข้อสรุป

แผนภูมิเปรียบเทียบ

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

คำจำกัดความของการค้นหาที่มีข้อมูล

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

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

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

Heuristic Depth การค้นหาครั้งแรก

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

อัลกอริธึมการค้นหาที่มีข้อมูลอีกแบบหนึ่งคือการค้นหาแบบ A * ซึ่งผสานแนวคิดของการค้นหาต้นทุนต่ำสุดแรกและดีที่สุด วิธีนี้จะพิจารณาทั้งต้นทุนเส้นทางและข้อมูลฮิวริสติกในกระบวนการค้นหาและเลือกเส้นทางที่จะขยาย ค่าใช้จ่ายรวมของเส้นทางโดยประมาณที่ใช้สำหรับแต่ละพา ธ ที่อยู่ในแนวชายแดนจากจุดเริ่มต้นไปยังโหนดเป้าหมาย ดังนั้นจึงใช้สองฟังก์ชั่นในเวลาเดียวกัน - cost (p) คือค่าใช้จ่ายของพา ธ ที่ค้นพบและ h (p) คือมูลค่าโดยประมาณของต้นทุนพา ธ จากโหนดเริ่มต้นไปยังโหนดเป้าหมาย

คำจำกัดความของการค้นหาที่ไม่รู้ข้อมูล

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

มีอัลกอริธึมการค้นหาที่หลากหลายภายใต้หมวดหมู่นี้เช่นการค้นหาความลึกแรกการค้นหาต้นทุนสม่ำเสมอการค้นหาความกว้างแรกและอื่น ๆ ให้เราเข้าใจแนวคิดเบื้องหลังการค้นหาที่ไม่รู้ด้วยความช่วยเหลือของการค้นหาในเชิงลึกก่อน

ค้นหาความลึกครั้งแรก

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

กล่าวอีกนัยหนึ่งอัลกอริธึมเลือกทางเลือกแรกในแต่ละโหนดจากนั้นย้อนรอยไปทางเลือกอื่นจนกว่ามันจะข้ามเส้นทางทั้งหมดจากการเลือกครั้งแรก สิ่งนี้ยังทำให้เกิดปัญหาที่การค้นหาอาจหยุดหยุดเนื่องจากมีลูปไม่สิ้นสุด (รอบ) ที่มีอยู่ในกราฟ

1. เทคนิคการค้นหาที่ได้รับการบอกกล่าวก่อนหน้านี้ใช้ความรู้เพื่อค้นหาวิธีแก้ปัญหา ในทางกลับกันเทคนิคการค้นหาหลังที่ไม่รู้จะไม่ใช้ความรู้ กล่าวง่ายๆคือไม่มีข้อมูลเพิ่มเติมเกี่ยวกับการแก้ปัญหา
2. ประสิทธิภาพของการค้นหาที่มีข้อมูลดีกว่าการค้นหาที่ไม่มีข้อมูล
3. การค้นหาที่ไม่มีรูปแบบจะใช้เวลาและค่าใช้จ่ายมากขึ้นเนื่องจากไม่มีเงื่อนงำเกี่ยวกับโซลูชันเมื่อเปรียบเทียบกับการค้นหาที่มีข้อมูล
4. การค้นหาความลึกครั้งแรกการค้นหาแบบกว้างและการค้นหาครั้งแรกที่ต้นทุนต่ำที่สุดคืออัลกอริธึมที่อยู่ในหมวดหมู่ของการค้นหาที่ไม่ทราบข้อมูล การค้นหาที่มีข้อมูลครอบคลุมถึงอัลกอริทึมเช่นการค้นหาเชิงลึกอันดับหนึ่งการค้นหาแบบกว้างแรกและการค้นหาแบบ A *

ข้อสรุป

การค้นหาที่มีข้อมูลจะให้ทิศทางเกี่ยวกับการแก้ปัญหาในขณะที่อยู่ในการค้นหาที่ไม่มีข้อมูลไม่มีข้อเสนอแนะเกี่ยวกับการแก้ปัญหา สิ่งนี้ทำให้การค้นหาที่ไม่รู้ข้อมูลยาวขึ้นเมื่อใช้อัลกอริทึม