We first consider the problem of se

We first consider the problem of searching for an admissible solution, we will then consider the
problem of searching for a solution of minimum cost.
We assume that the admissible solutions for an instance I belong to a subset of elements SI
that is easy to enumerate and that it is possible to test efficiently if an elements s ∈ SI is an
admissible solution for I. In other words, we make the following assumptions:
(1) for every I, AdmI ⊆ SI ;
(2) there exists an efficient algorithm enumerateSI that, on input instance I, enumerates
SI ;
(3) there exists an efficient algorithm isAdmissible that, for every S ∈ SI , decides whether
S is an admissible solution for I;
and describe the following meta-algorithm

ผลลัพธ์ (ไทย) 1:

เรามาพิจารณาดูปัญหาการค้นหาสำหรับโซลูชัน admissible เราจะแล้วพิจารณาปัญหาของการค้นหาโซลูชันต้นทุนต่ำสุดเราคิดว่า โซลูชั่น admissible สำหรับอินสแตนซ์ของฉันอยู่ในชุดย่อยขององค์ประกอบศรีที่พักที่ระบุ และสามารถทดสอบได้อย่างมีประสิทธิภาพถ้า∈ s เป็นองค์ประกอบในการโซลูชั่น admissible สำหรับฉัน ในคำอื่น ๆ เราให้สมมติฐานต่อไปนี้:(1) หาทุก AdmI ⊆ SI(2) enumerateSI อัลกอริทึมที่มีประสิทธิภาพเป็นที่ บนอินสแตนซ์สำหรับการป้อนค่า ระบุมีศรี(3) มีอยู่ isAdmissible เป็นอัลกอริทึมที่มีประสิทธิภาพที่ สำหรับทุก∈ S ซี ตัดสินใจว่าS เป็นโซลูชัน admissible หาและอธิบายอัลกอริธึม meta ที่ต่อไปนี้

ผลลัพธ์ (ไทย) 2:

ก่อนอื่นเราพิจารณาปัญหาของการค้นหาวิธีการแก้ปัญหาที่ยอมรับเราก็จะพิจารณา
ปัญหาของการหาวิธีแก้ปัญหาของค่าใช้จ่ายน้อยที่สุด.
เราคิดว่าการแก้ปัญหาการยอมรับเช่นฉันเป็นส่วนหนึ่งขององค์ประกอบ SI
ที่ง่ายต่อการระบุและ ว่ามันเป็นไปได้ที่จะทดสอบได้อย่างมีประสิทธิภาพถ้าองค์ประกอบ S ∈ SI เป็น
ทางออกที่ยอมรับสำหรับ I. ในคำอื่น ๆ ที่เราทำสมมติฐานดังต่อไปนี้
(1) สำหรับทุกครั้งที่ผม, Admi ⊆ SI;
(2) มีอยู่ enumerateSI อัลกอริทึมที่มีประสิทธิภาพ ว่าในอินสแตนซ์ใส่ผมระบุ
SI;
(3) มีอยู่ isAdmissible อัลกอริทึมที่มีประสิทธิภาพที่สำหรับทุก∈ S SI ตัดสินใจว่า
S เป็นวิธีการแก้ปัญหาที่ยอมรับสำหรับฉัน;
และอธิบายต่อไปนี้ขั้นตอนวิธี meta-

ผลลัพธ์ (ไทย) 3:

แรกที่เราต้องพิจารณาปัญหาของการค้นหาสำหรับโซลูชั่นที่เป็นยอมรับ เราจึงจะพิจารณา
ปัญหาการหาวิธีแก้ปัญหาของค่าใช้จ่าย .
เราคิดว่ายอมรับโซลูชั่นสำหรับอินสแตนซ์ ฉันเป็นส่วนหนึ่งขององค์ประกอบศรี
ที่ง่ายต่อการระบุและว่ามันเป็นไปได้ที่จะทดสอบได้อย่างมีประสิทธิภาพ หากมีองค์ประกอบของ ∈ศรีเป็น
ยอมรับโซลูชั่นสำหรับ ในคำอื่น ๆเราให้สมมติฐานดังต่อไปนี้ :
( 1 ) ทุกชั้น จังหวัดนครราชสีมา⊆ศรี ;
( 2 ) มี enumeratesi มีประสิทธิภาพขั้นตอนวิธีที่ป้อนตัวอย่างผมได้แจกแจง
ศรี ;
( 3 ) มีอยู่ประสิทธิภาพอัลกอริทึม isadmissible ว่าสำหรับทุก s ∈ศรี , ตัดสินใจว่า
S เป็นโซลูชั่น ที่ยอมรับได้สำหรับฉัน ;

และอธิบายตาม meta ขั้นตอนวิธี