ต้นไม้และ–หรือ

คือการแสดงกราฟของการลดลงของปัญหา (เป้าหมาย) เพื่อสันธานและการเลือกของปัญหา (หรือเป้าหมายย่อย)

ตัวอย่าง

 

หมายถึงพื้นที่การค้นหาสำหรับการแก้ปัญหา P โดยใช้วิธีการลดเป้าหมาย:

P ถ้า Q และ R

P ถ้า S

Q ถ้า T

Q ถ้า U

คำนิยาม

ต้นไม้ (อังกฤษ: Tree) เป็น แบบชนิดข้อมูลนามธรรม ประเภทหนึ่ง มีลักษณะการเรียงเป็นกิ่งก้านสาขาแตกแขนงออกไป จะไม่มีวงวน (loop) โยงในสมาชิกตัวต่างๆ โดยสมาชิกจะถูกเก็บไว้ในประเภทข้อมูลชนิดวัตถุ (Object) หรือโครงสร้าง (Structure) เรียกว่าปม (node) ซึ่งจะมีตัวแปรซึ่งเก็บตัวชี้ (Pointer) ไปยังปมอื่นๆได้ต้นไม้ถูกใช้ในการจัดการข้อมูลที่เปรียบเทียบกันได้ (comparable) อย่างรวดเร็วเช่น ตัวเลข หรือ การเรียงลำดับความสำคัญของข้อมูล เช่น การคำนวณที่มีวงเล็บ เป็นต้น

กลยุทธ์การค้นหา

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

ความสัมพันธ์กับการเขียนโปรแกรม

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