Generic version[edit]The following

Generic version[edit]
The following is the skeleton of a generic branch and bound algorithm for minimizing an arbitrary objective function f.[2] To obtain an actual algorithm from this, one requires a bounding function g, that computes lower bounds of f on nodes of the search tree, as well as a problem-specific branching rule.

Using a heuristic, find a solution xh to the optimization problem. Store its value, B = f(xh). (If no heuristic is available, set B to infinity.) B will denote the best solution found so far, and will be used as an upper bound on candidate solutions.
Initialize a queue to hold a partial solution with none of the variables of the problem assigned.
Loop until the queue is empty:
Take a node N off the queue.
If N represents a single candidate solution x and f(x) < B, then x is the best solution so far. Record it and set B ← f(x).
Else, branch on N to produce new nodes Ni. For each of these:
If g(Ni) > B, do nothing; since the lower bound on this node is greater than the upper bound of the problem, it will never lead to the optimal solution, and can be discarded.
Else, store Ni on the queue.
Several different queue data structures can be used. A stack (LIFO queue) will yield a depth-first algorithm. A best-first branch and bound algorithm can be obtained by using a priority queue that sorts nodes on their g-value.[2] The depth-first variant is recommended when no good heuristic is available for producing an initial solution, because it quickly produces full solutions, and therefore upper bounds.[6]

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

รุ่นทั่วไป [แก้]ต่อไปนี้เป็นโครงกระดูกสาขาทั่วไปและอัลกอริทึมที่ถูกผูกไว้เพื่อลดการ f. ฟังก์ชันวัตถุประสงค์เอง [2] รับอัลกอริทึมจริงจากนี้ หนึ่งต้องการ g ฟังก์ชันรูปกล่อง ที่คำนวณขอบเขตล่างของ f บนโหนดของต้นไม้ค้นหา เป็นปัญหาเฉพาะด้านกฎใช้การแก้ปัญหา xh แก้ไขปัญหาเพิ่มเติม เก็บค่า B = f(xh) (ถ้าแก้ปัญหาไม่เป็น B ที่พร้อมใช้งาน ตั้งค่าอนันต์) B จะแสดงวิธีที่ดีที่สุดพบดังนั้นไกล และจะใช้เป็นการขึ้นไปเป็นโซลูชั่นเตรียมใช้คิวเพื่อการแก้ไขปัญหาบางส่วนที่ไม่มีตัวแปรของปัญหาที่กำหนดให้วนรอบจนกว่าคิวจะว่างเปล่า:มีโหนด N ออกคิวถ้า N แทนโซลูชันเดียวสมัคร x และ f(x) < B แล้ว x เป็นโซลูชันที่ดีที่สุดเพื่อให้ห่างไกล บันทึก และตั้งค่า B ← f(x)สาขาอื่น บน N ผลิตโหนใหม่นิ สำหรับแต่ละเหล่านี้:ถ้า g(Ni) > B ทำอะไร ตั้งแต่ขอบล่างบนโหนดนี้เป็นสูงกว่าขอบบนของปัญหา มันจะนำไปสู่การแก้ปัญหาที่ดีที่สุดไม่เคย และสามารถละทิ้งอื่น เก็บ Ni ในคิวสามารถใช้โครงสร้างข้อมูลคิวที่แตกต่างกันหลาย กองซ้อน (LIFO คิว) จะได้เป็นอัลกอริทึมของความลึก สาขาแรกที่ดีที่สุดและอัลกอริทึมที่ถูกผูกไว้จะได้ โดยใช้คิวลำดับความสำคัญที่เรียงโหนบนของค่า g [2] ตัวแปรความลึกแนะนำเมื่อแก้ปัญหาไม่ดีสำหรับแก้ปัญหาการเริ่มต้น การผลิตเนื่องจากรวดเร็วสร้างโซลูชั่นเต็มรูปแบบ และขอบเขตบน [6]

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

รุ่นทั่วไป [แก้ไข]
ต่อไปนี้เป็นโครงกระดูกของสาขาทั่วไปและขั้นตอนวิธีการที่ถูกผูกไว้เพื่อลดพลวัตถุประสงค์ฟังก์ชั่นฉ. [2] เพื่อขอรับอัลกอริทึมที่เกิดขึ้นจริงจากนี้หนึ่งต้องใช้ฟังก์ชัน g ขอบเขตที่คำนวณขอบเขตล่างของ F บน โหนดของต้นไม้ค้นหาเช่นเดียวกับกฎแขนงปัญหาเฉพาะ. ใช้แก้ปัญหาที่พบ XH วิธีการแก้ปัญหาการเพิ่มประสิทธิภาพ เก็บค่าของ B = f (x สูง) (หากไม่มีการแก้ปัญหาที่มีอยู่ตั้ง B ไปไม่มีที่สิ้นสุด.) B จะแสดงว่าทางออกที่ดีที่สุดพบเพื่อให้ห่างไกลและจะถูกนำมาใช้เป็นขอบเขตบนโซลูชั่นผู้สมัคร. เริ่มต้นคิวที่จะถือเป็นวิธีการแก้ปัญหาบางส่วนกับไม่มีตัวแปรของ . ปัญหาที่ได้รับมอบหมายห่วงจนกว่าคิวจะว่างเปล่า: ใช้โหนด N ออกคิว. ถ้าไม่มีแสดงให้เห็นถึงวิธีการแก้ปัญหา x สมัครเพียงครั้งเดียวและ f (x) <B แล้ว x เป็นทางออกที่ดีที่สุดเพื่อให้ห่างไกล บันทึกและการตั้งค่า F B ← (x). อื่นในสาขาการผลิต N โหนดใหม่ Ni สำหรับแต่ละเหล่านี้: หากกรัม (NI)> B, ทำอะไร; ตั้งแต่ขอบเขตล่างบนโหนดนี้มากกว่าขอบเขตบนของปัญหาก็จะไม่นำไปสู่ทางออกที่ดีที่สุดและสามารถนำมาทิ้ง. อื่น ๆ , ร้าน Ni ในคิว. หลายโครงสร้างข้อมูลคิวที่แตกต่างกันสามารถนำมาใช้ สแต็ค (คิวที) จะให้ผลผลิตอัลกอริทึมลึกแรก สาขาที่ดีที่สุดเป็นครั้งแรกและขั้นตอนวิธีการที่ถูกผูกไว้จะได้รับจากการใช้คิวลำดับความสำคัญที่จะเรียงลำดับโหนดใน G-ค่าของพวกเขา. [2] ตัวแปรลึกแรกจะแนะนำเมื่อไม่มีการแก้ปัญหาที่ดีสามารถใช้ได้สำหรับการผลิตวิธีการแก้ปัญหาเบื้องต้นเพราะมันได้อย่างรวดเร็ว ผลิตโซลูชั่นเต็มรูปแบบและขอบเขตดังนั้นบน. [6]

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

[ แก้ไข ] รุ่นทั่วไปต่อไปนี้เป็นโครงกระดูกของสาขาทั่วไปและขั้นตอนวิธีสำหรับการลดฟังก์ชันวัตถุประสงค์ไว้โดยพลการ F . [ 2 ] เพื่อให้ได้วิธีการที่เกิดขึ้นจริงจากหนึ่งนี้ ต้องจำกัดฟังก์ชัน g ที่คำนวณขอบเขตล่างของ F บนโหนดของต้นไม้ค้นหา ตลอดจนปัญหาที่เฉพาะเจาะจงตามกฎใช้ฮิวริสติก หาทางแก้ไขเพื่อเพิ่มประสิทธิภาพ XH ปัญหา เก็บค่าของ B = F ( XH ) ( ถ้าไม่มีแบบพร้อมใช้งาน ชุด B อินฟินิตี้ ) B จะแสดงวิธีที่ดีที่สุดที่พบเพื่อให้ห่างไกล และจะใช้เป็นผูกไว้บนโซลูชั่นผู้สมัครเริ่มคิวถือโซลูชั่นบางส่วนกับไม่มีตัวแปรของปัญหาที่ได้รับมอบหมายห่วงจนคิวว่าง :ใช้โหนด N ออกจากคิวถ้า n เป็นผู้สมัครโซลูชั่นเดียว x และ f ( x ) < b แล้ว X เป็นทางออกที่ดีที่สุดเพื่อให้ห่างไกล บันทึก และชุด B ← f ( x )อีกสาขาในการสร้างโหนดใหม่ นิ สำหรับแต่ละเหล่านี้ :ถ้า g ( N ) B , ทำอะไรที่ขอบเขตล่างบนโหนดนี้มากกว่าค่าขอบเขตบนของปัญหา ก็จะไม่นำไปสู่การแก้ปัญหาที่ดีที่สุด และสามารถเป็นอีกร้านที่ผมกับคิวหลายคิวโครงสร้างข้อมูลที่สามารถใช้ กอง ( เข้าคิว ) จะให้ผลผลิตที่ความลึกแรกขั้นตอนวิธี แรกที่ดีที่สุดกองบัญชาการได้ โดยการใช้แถวคอยลำดับความสำคัญที่ประเภทของโหนดใน g-value [ 2 ] ความลึกแรกตัวแปรคือแนะนำเมื่อไม่ดี ) สามารถใช้ได้ในการผลิตโซลูชั่นแรกเพราะมันได้อย่างรวดเร็วสร้างเต็มรูปแบบโซลูชั่น , และดังนั้นบนขอบเขต [ 6 ]