During a rescue problem, a room or

During a rescue problem, a room or edge may be destroyed at some specified time. Robots that have not completed their rescue operation at that time are then to be reallocated to complete remaining rescues at minimum total cost.

1. The original rescue problem is solved as in Subsection 3.3 and, for each minimum cost path, the partial costs to reach each node on the path are recorded. We assume that these partial costs give the times at which a robot reaches a node.

2. The adjacency matrices for each are updated to allow for the destruction of a room or edge. A room I is removed by deleting row I and column I of the original adjacency matrix. An edge (i,j) is removed by setting aij to 0 or infinity in full storage mode, or deleting the entry in sparse storage mode.

3. The position of each robot at the time of the node or edge destruction is determined. The robots are separated into “active” robots that have not completed their rescue mission and inactive robots that have completed their mission.

4. The rescue problem for the active robots is solved using the algorithm given in Subsection 3.3. The adjacency matrices for the active robots are constructed by selecting appropriate rows and columns from the updated adjacency matrices obtained in stage 2. The “start” node for each active robot is taken as the position of that robot at the time of the destruction of the node or edge. The active set of “target” nodes is taken as the subset of the original target nodes that have not yet been reached by any robot. Of course, if a target node is the node that was destroyed then this node cannot be included in the active set of “target” nodes.

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

ระหว่างปัญหากู้ภัย ห้องพักหรือขอบอาจจะทำลายบางครั้งระบุ หุ่นยนต์ที่ยังไม่สมบูรณ์ของการดำเนินการช่วยเหลือที่ จะให้สามารถจัดสรรใหม่ให้เสร็จ rescues เหลือต้นทุนรวมต่ำสุดแล้ว1.ต้นฉบับช่วยเหลือแก้ไขปัญหาได้อย่างใน Subsection 3.3 และ มีบันทึกต้นทุนบางส่วนถึงแต่ละโหนดในเส้นทางแต่ละเส้นทางต้นทุนที่ต่ำ เราสมมติว่า ต้นทุนเหล่านี้บางส่วนให้เวลาที่หุ่นยนต์ถึงโหนด2.เมทริกซ์ adjacency สำหรับแต่ละจะถูกปรับปรุงเพื่อให้การทำลายห้องหรือขอบ ห้องพักผมจะถูกเอาออก โดยการลบแถวคอลัมน์และฉันฉันเมตริกซ์ adjacency เดิม ขอบ (i, j) จะถูกเอาออก โดยตั้งค่า aij เป็น 0 หรืออินฟินิตี้ในโหมดเก็บเต็ม หรือลบรายการในโหมดเก็บบ่อ3. ตำแหน่งของหุ่นยนต์แต่ละครั้งทำลายโหนหรือขอบจะถูกกำหนด หุ่นยนต์จะแบ่งออกเป็นหุ่นยนต์ "ใช้งาน" ที่ยังไม่สมบูรณ์ของภารกิจกู้ภัยและหุ่นยนต์งานที่เสร็จภารกิจของพวกเขา4 เป็นแก้ไขปัญหา.ช่วยเหลือหุ่นยนต์ใช้งานอยู่โดยใช้อัลกอริทึมใน Subsection 3.3 เมทริกซ์ adjacency สำหรับหุ่นยนต์ใช้งานอยู่ถูกสร้าง โดยเลือกที่เหมาะสมของแถวและคอลัมน์จากเมทริกซ์ adjacency ปรับปรุงที่ได้รับในขั้นตอนที่ 2 โหน "เริ่มต้น" สำหรับหุ่นยนต์แต่ละงานจะถูกใช้เป็นตำแหน่งของหุ่นยนต์นั้นเมื่อทำลายของโหนดหรือขอบ ชุดใช้งานอยู่โหน "เป้าหมาย" จะถูกใช้เป็นชุดย่อยของโหนเป้าหมายเดิมที่ยังไม่ถูกเข้าถึง โดยหุ่นยนต์ใด ๆ แน่นอน ว่าโหนปลายทาง โหนดที่ถูกทำลาย โหนดนี้ไม่รวมในชุดงานของโหน "เป้าหมาย"

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

ในช่วงปัญหากู้ภัย, ห้องหรือขอบอาจถูกทำลายในบางเวลาที่กำหนด หุ่นยนต์ที่ยังไม่เสร็จสิ้นการดำเนินการช่วยเหลือพวกเขาในเวลาที่มีแล้วจะได้รับการจัดสรรให้เสร็จสมบูรณ์เหลืออยู่บ้างที่ค่าใช้จ่ายรวมต่ำสุด. 1 ปัญหากู้ภัยเดิมจะแก้ไขเช่นเดียวกับในข้อย่อย 3.3 และสำหรับแต่ละเส้นทางค่าใช้จ่ายขั้นต่ำค่าใช้จ่ายบางส่วนที่จะไปถึงโหนดบนเส้นทางแต่ละมีการบันทึกไว้ เราคิดว่าค่าใช้จ่ายบางส่วนเหล่านี้ให้ครั้งที่หุ่นยนต์ถึงโหนด. 2 การฝึกอบรมสำหรับแต่ละถ้อยคำที่มีการปรับปรุงเพื่อให้การทำลายของห้องหรือขอบ ห้องที่ผมจะถูกลบออกโดยการลบแถวและคอลัมน์ฉันฉันเมทริกซ์ถ้อยคำเดิม ขอบ (ฉัน j) จะถูกลบออกโดยการตั้งค่า AIJ 0 หรืออินฟินิตี้ในโหมดที่เก็บเต็มหรือลบรายการในโหมดที่เก็บเบาบาง. 3 ตำแหน่งของหุ่นยนต์แต่ละช่วงเวลาของการทำลายโหนดหรือขอบจะถูกกำหนด หุ่นยนต์ที่ถูกแยกออกเป็น "การใช้งาน" หุ่นยนต์ที่ยังไม่เสร็จสิ้นภารกิจกู้ภัยของพวกเขาและไม่ได้ใช้งานหุ่นยนต์ที่ได้เสร็จสิ้นภารกิจของพวกเขา. 4 ปัญหากู้ภัยสำหรับหุ่นยนต์ที่ใช้งานได้รับการแก้ไขโดยใช้ขั้นตอนวิธีการที่กำหนดในข้อย่อย 3.3 การฝึกอบรมถ้อยคำสำหรับหุ่นยนต์ที่ใช้งานจะถูกสร้างโดยการเลือกแถวและคอลัมน์ที่เหมาะสมจากการฝึกอบรมการปรับปรุงถ้อยคำที่ได้รับในขั้นตอนที่ 2 "เริ่มต้น" โหนดสำหรับหุ่นยนต์ที่ใช้งานในแต่ละจะมาเป็นตำแหน่งของหุ่นยนต์ที่ในช่วงเวลาของการล่มสลายของ โหนดหรือขอบ ชุดที่ใช้งานของ "เป้าหมาย" โหนดจะมาเป็นส่วนหนึ่งของโหนดเป้าหมายเดิมที่ยังไม่ได้ไปถึงได้โดยหุ่นยนต์ใด ๆ แน่นอนถ้าโหนดเป้าหมายคือโหนดที่ถูกทำลายแล้วโหนดนี้ไม่สามารถรวมอยู่ในชุดที่ใช้งานของ "เป้าหมาย" โหนด

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

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

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

2 ส่วนถ้อยคำเมทริกซ์สำหรับแต่ละการปรับปรุง เพื่อให้สำหรับการทำลายของห้องหรือขอบ ห้องผมจะถูกลบออกโดยการลบแถวและคอลัมน์ของเมตริกซ์ถ้อยคำเดิม ขอบ ( i , j ) จะถูกลบออกโดยการ aij 0 หรืออนันต์ในโหมดเต็มกระเป๋า , หรือลบรายการในโหมดกระเป๋าโปร่ง

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

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