เพื่อให้เข้าใจถึงปัญหา 15Puzzle ฉันได้เรียนรู้เกี่ยวกับการค้นหาที่ลึกซึ้งครั้งแรกและการค้นหาครั้งแรกที่กว้าง ก่อนอื่นมาพูดคุยเกี่ยวกับการค้นหาเชิงลึกครั้งแรก (DFS) วัตถุประสงค์ของความลึกแรกคือการจัดลำดับความสำคัญการค้นหาเส้นทางที่ไกลที่สุดจากจุดสุดยอดเริ่มต้นในขณะที่การค้นหาครั้งแรกที่กว้างคือการค้นหาเส้นทางที่ใกล้เคียงกับจุดสุดยอดเริ่มต้นที่สุด ฉันสงสัยว่าอะไรคือความแตกต่างระหว่างการค้นหาครั้งแรกและการย้อนรอยหลัง? ใน Baidu มีการกล่าวกันว่าการย้อนรอยเป็นการค้นหาที่ลึก แต่ความแตกต่างคือการย้อนรอยไม่ได้รักษาแผนผังการค้นหา แล้วการค้นหาในวงกว้างครั้งแรก (BFS) ล่ะ? แอปพลิเคชันคืออะไร? คำตอบ: เส้นทางที่สั้นที่สุดปัญหาการแบ่งไวน์ปัญหาดิจิตอลแปดข้อ ฯลฯ มากลับไปที่จุดที่นี่ฉันได้ดำเนินการค้นหาอย่างกว้างขวางและค้นหาอย่างลึกล้ำโดยใช้ Java ในหมู่พวกเขาการค้นหาลึกจะถูกนำไปใช้โดยใช้กราฟ + สแต็กและการค้นหาแบบกว้างถูกนำไปใช้โดยใช้กราฟ + คิว รหัสมีดังนี้:
1. สร้างคลาสใหม่ NodirectionGraph ที่แสดงถึง "กราฟที่ไม่ได้กำกับ"
แพ็คเกจ com.wly.algorithmbase.datastructure;/** * กราฟที่ไม่ได้ทิศทาง * @author wly * */คลาสสาธารณะ nodirectiongraph {private int mmaxsize; // จำนวนจุดยอดสูงสุดที่มีอยู่ในกราฟ จุดยอดส่วนตัว int nvertex; // จำนวนจุดยอดที่บันทึกไว้ในปัจจุบัน nodirectionGraph (int maxsize) {mMaxSize = maxSize; VertexList = new graphvertex [mMaxSize]; indicatorMat = ใหม่ int [mMaxSize] [mMaxsize] j = 0; j <mmaxsize; j ++) {สำหรับ (int k = 0; k <mmaxsize; k ++) {indicatormat [j] [k] = 0;}}} โมฆะสาธารณะ addvertex (graphvertex v) {if (nvertex <mmaxsize) {system.out.println ("--- การแทรกล้มเหลวจำนวนจุดยอดถึงขีด จำกัด บน!");}}/*** ปรับเปลี่ยนเมทริกซ์ adjacency และเพิ่มขอบใหม่* @param start* @param end*/public void endge adjacency matrix*/โมฆะสาธารณะ printindicatormat () {สำหรับ (int [] line: indicatormat) {สำหรับ (int i: line) {system.out.print (i + "");} system.out.println ();}}/** ** Matrix adjacency ของกราฟ */โมฆะสาธารณะ DFS (int vertexIndex) {arraystack stack = new ArrayStack (); // 1 เพิ่มองค์ประกอบการค้นหาลงในสแต็ก VertexList [VertexIndex] .setVisited (จริง); stack.push (VertexIndex); int nextvertexIndex = getNextvertexIndex (VertexIndex); ในขณะที่ (! stack.isempty ()) {// กดสแต็กอย่างต่อเนื่องและออกสแต็กจนกว่าสแต็กจะว่างเปล่า (องค์ประกอบการค้นหาไม่ปรากฏขึ้นสแต็ก) ถ้า (nextvertexindex! = -1) {vertexlist [nextvertexindex] {stack.pop ();} // เรียกคืนว่าองค์ประกอบด้านบนปัจจุบันมีโหนดอื่น ๆ ที่ไม่ได้ใช้งานอื่น ๆ ถ้า (! stack.isempty ()) {nextvertexindex = getNextvertexIndex (stack.peek ());}}}/** * getNextvertexIndex (คอลัมน์ int) {สำหรับ (int i = 0; i <indicatormat [คอลัมน์] .length; i ++) {ถ้า (ตัวบ่งชี้ [คอลัมน์] [i] == 1 &&! vertexlist [i]. Traverse นั่นคือจำนวนแถวในเมทริกซ์ adjacency ของกราฟ*/โมฆะสาธารณะ BFS (int VertexIndex) {chainqueue queue = new Chainqueue (); VertexList [VertexIndex] getNextvertexIndex (VertexIndex); ในขณะที่ (! queue.isempty ()) {ถ้า (nextvertexindex! = -1) {vertexlist [nextvertexindex] .setVisited (จริง); queue.insert (queuenode ใหม่ (nextvertexindex)); getNextvertexIndex (queue.peek (). data); queue.printelems ();}}}}}2. จากนั้นมีอาร์เรย์สแต็กที่จำลองด้วยอาร์เรย์
แพ็คเกจ com.wly.algorithmbase.datastructure;/***ใช้อาร์เรย์เพื่อใช้โครงสร้างสแต็ก*@author wly**/คลาสสาธารณะ Arraystack {private int [] tarray; int topindex ส่วนตัว = -1; // ระบุตำแหน่งดัชนีขององค์ประกอบด้านบนของสแต็ก อาร์เรย์ทั่วไป ***/tarray = new int [ความสามารถ _step];}/***เมธอดเพื่อป๊อปอัพองค์ประกอบด้านบน*@return*/สาธารณะ int pop () {ถ้า (isempty ()) {system.out.println ("ข้อผิดพลาดองค์ประกอบในสแต็กว่างเปล่าไม่สามารถป๊อป"); return -1;} else {int i = tarray [topIndex]; tarray [topindex--] = -1; // ลบองค์ประกอบป๊อปกลับ i;}}/*** แทรกองค์ประกอบลงในสแต็ก* @param t*/โมฆะสาธารณะ push (int t) {// ตรวจสอบว่าสแต็กเต็มหรือไม่ int [tarray.length + ความสามารถ _step]; สำหรับ (int i = 0; i <tarray.length; i ++) {temparray [i] = tarray [i];} tarray = temparray; temparray = null;} else {topindex ++; tarray [topindex] = t;}}/** {ถ้า (isempty ()) {system.out.println ("ข้อผิดพลาดองค์ประกอบในสแต็กว่างเปล่าไม่สามารถมองดู"); return -1;} else {return tarray [topindex];}}/*** ตรวจสอบว่าสแต็กปัจจุบันว่าง* เป็นโมฆะ printelems () {สำหรับ (int i = 0; i <= topIndex; i ++) {system.out.print (tarray [i]+"");} system.out.println ();}}}3. chainqueue ในคิวจำลองด้วยรายการที่เชื่อมโยง
แพ็คเกจ com.wly.algorithmbase.datastructure;/** * ใช้รายการที่เชื่อมโยงเพื่อใช้คิว * * @author wly * */public class chainqueue {private queuenode head; // ชี้ไปที่หัวของคิวส่วนตัว โหนดใหม่ไปที่หางของคิว*/โมฆะสาธารณะแทรก (โหนด queuenode) {// แน่นอนคุณสามารถเขียนสิ่งนี้เพิ่ม tail.prev = โหนดถ้า (head == null) {head = node; tail = head; Node;} size ++;}/*** ลบโหนดหัวคิว*/queuenode สาธารณะลบ () {ถ้า (! isempty ()) {queuenode temp = head; head = head.prev; ขนาด-; return temp; ว่างเปล่า * * @return */บูลีนสาธารณะ isempty () {ถ้า (ขนาด> 0) {return false;} else {return true;}}/** * ส่งคืนโหนดแรกของคิว แต่ไม่ได้ลบ */queenode peek.peep () คิวปัจจุบันว่างเปล่า! "); return null;}}/*** ส่งคืนขนาดคิว** @return*/ขนาด int สาธารณะ () {return size;}/*** องค์ประกอบพิมพ์ในคิว*/void printelems () {queuenode tempnode = head; "); tempNode = tempNode.prev;} system.out.println ();}}/** * คลาสโหนด * * * @author wly * */คลาส queuenode {queuenode prev; queuenode next; int data; setData (ข้อมูล int) {this.data = data;}@reverride สตริงสาธารณะ toString () {// todo วิธีการที่สร้างอัตโนมัติ stub super.toString (); return data + "";}}}4. ทดสอบ test_bfs_dfs
แพ็คเกจ com.wly.algorithmbase.search; นำเข้า com.wly.algorithmbase.datastructure.graphvertex; นำเข้า com.wly.algorithmbase.datastructure.nodirectiongraph;/** * argst args_ args (@author class class {// เริ่มต้นการทดสอบ data nodirectionGraph กราฟ = ใหม่ nodirectionGraph (7); graph.addvertex (กราฟใหม่ ("a")); graph.addvertex (กราฟใหม่ ("b"); graph.addvertex graphvertex ("e")); graph.addvertex (ใหม่ graphvertex ("f")); graph.addvertex (ใหม่ graphvertex ("g")); graph.addedge (0, 1); graph.addedge (0, 2); graph.addedge (1, 3); graph.addedge 5); System.out.println ("-เมทริกซ์ที่อยู่ติดกันของกราฟ-"); graph.printindicatormat (); // ทดสอบระบบการค้นหาลึก. graphvertex ("b")); graph.addvertex (ใหม่ graphvertex ("c")); graph.addvertex (ใหม่ graphvertex ("d")); graph.addvertex (graphvertex ใหม่ ("e")); graph.addvertex graphvertex ("g")); graph.addedge (0, 1); graph.addedge (0, 2); graph.addedge (1, 3); graph.addedge (1, 4); graph.addedge (3, 6); graph.addedge (2, 5);โครงสร้างกราฟทดสอบที่นี่มีดังนี้:
ผลการดำเนินการมีดังนี้:
-matrix adjacent ของกราฟ-0 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
ที่นี่เราต้องอธิบายผลลัพธ์การทำงานของการค้นหาอย่างลึกและการค้นหาที่กว้างด้านบนโดยที่ 0, 1, 2, 3 ... สอดคล้องกับ a, b, c, d ตามลำดับ ... มันค่อนข้างสับสนโปรดยกโทษให้ฉัน ~~
โอ้ ~~~
สรุป
ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้เกี่ยวกับการใช้งานการเขียนโปรแกรม Java ของการค้นหาเชิงลึกที่ใช้กราฟครั้งแรกและการค้นหาที่สมบูรณ์แบบเป็นครั้งแรก ฉันหวังว่ามันจะเป็นประโยชน์กับทุกคน เพื่อนที่สนใจสามารถอ้างถึงหัวข้ออื่น ๆ ที่เกี่ยวข้องในเว็บไซต์นี้ต่อไป หากมีข้อบกพร่องใด ๆ โปรดฝากข้อความไว้เพื่อชี้ให้เห็น ขอบคุณเพื่อนที่ให้การสนับสนุนเว็บไซต์นี้!