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