لفهم مشكلة 15Puzzle ، تعلمت عن البحث الأول والبحث في العرض الأول. دعنا نناقش أولاً البحث في العمق (DFS). الغرض من العمق الأول هو إعطاء الأولوية للبحث عن مسارات أبعد ما تكون عن قمة البداية ، في حين أن البحث الأول هو البحث أولاً عن المسارات الأقرب إلى قمة البداية. أتساءل ما هو الفرق بين البحث الأول والتراجع؟ في Baidu ، يقال أن التراجع هو نوع من البحث العميق ، ولكن الفرق هو أن التراجع لا يحتفظ بشجرة البحث. إذن ماذا عن البحث الأول الواسع (BFS)؟ ما هي تطبيقاتها؟ الإجابة: أقصر مسار ، مشكلة في قسم النبيذ ، ثمانية مشكلة رقمية ، إلخ. دعنا نعود إلى هذه النقطة ، هنا قمت ببساطة بتطبيق بحث واسع وبحث عميق باستخدام Java. من بينها ، يتم تطبيق البحث العميق باستخدام Graph + Stack ، ويتم تطبيق البحث العريض باستخدام قائمة الانتظار Graph +. الرمز كما يلي:
1. إنشاء فئة جديدة nodirectiongraph تمثل "الرسم البياني غير الموجود"
package com.wly.algorithmbase.datictructure ؛/** * رسم بياني غير موجه * @Author wly * */class public class nodirectiongraph {private int mmaxsize ؛ // الحد الأقصى لعدد القمم الواردة في العلاقة بين الرسم البياني الخاص private int nvertex ؛ // عدد القمم المحفوظة حاليًا NodirectionGraph (int maxSize) {mmaxSize = maxSize ؛ VertexList = جديد GraphVertex [mmaxss] j = 0 ؛ j <mmaxSize ؛ j ++) {for (int k = 0 ؛ k <mmaxSize ؛ k ++) {indicatormat [j] [k] = 0 ؛}}} public void addvertex (graphvertex v) {if (nvertex <mmaxsize) {vertexlist {system.out.println ("--- فشل الإدراج ، وصل عدد القمم إلى الحد الأعلى!") ؛}/*** تعديل مصفوفة متاخمة وأضف حافة جديدة* start* param مصفوفة مجاورة*/public void printIndicatorMat () {for (int [] السطر: indicatormat) {for (int i: line) {system.out.print (i + "") مصفوفة من الرسم البياني */public void dfs (int vertexindex) {arraystack stack = new ArrayStack () ؛ // 1. أضف عنصر البحث إلى vertexlist [VertexIndex] .setVisited (true) ؛ stack.push (vertexindex) ؛ int nextVerTexIndex = getNextVertexIndex (VertexIndex) ؛ بينما (! stack.isempty ()) {// اضغط بشكل مستمر على المكدس والخروج من المكدس حتى يصبح المكدس فارغًا (لا يظهر عنصر البحث على المكدس) إذا (nextVerTexIndex! = -1) {vertexlist [nextVertexIndex] .setVisted (true) ؛ ما إذا كان العنصر العلوي الحالي يحتوي على عقد أخرى غير محسوسة إذا (! stack.isempty ()) {nextVerTexIndex = getNextVertexIndex (stack.peek () i = 0 ؛ i <indicatormat [column] .length ؛ i ++) {if (indicatormat [column] [i] == 1 &&! vertexlist [i] .isvisited ()) {return i ؛}} return -1 ؛}/** الرسم البياني*/public void bfs (int vertexindex) {Quinqueue Queue = new tainqueue () ؛ VertexList [VertexIndex] .SetVisited (true) ؛ queue.insert (Queuenodeexindexexindex) ؛ بينما (! queue.isempty ()) {if (nextVerTexIndex! = -1) {VertexList [nextVerTexIndex] .setVisited (true) ؛ queue.insert (new queuenode (nextVerTexIndex)) ؛} آخر {queue.remove () ؛ getNextVertexIndex (queue.peek (). البيانات) ؛ queue.printelems () ؛}}}}2. ثم هناك arraystack يتم محاكاة مع صفيف
package com.wly.algorithmbase.daturstructure ؛/***استخدم المصفوفات لتنفيذ هيكل المكدس*author wly**/class public class arraystack {private int [] tarray ؛ private int topIndex = -1 ؛ Array ***/tarray = new int [cute_step] ؛}/***طريقة الظهارة العليا العنصر* @return*/public int pop () {if (isEmpty ()) {system.out.println ("خطأ ، العنصر في المكدس فارغ ، لا يمكنه البوب") ؛ return -1 ؛} else {int i = tarray [topIndex] ؛ tarray [topIndex--] = -1 ؛ // محو عنصر البوب إرجاع I ؛}/*** أدخل عنصرًا في المكدس* param t*/public push (int t) int [tarray.length + cute_step] ؛ لـ (int i = 0 ؛ i <tarray.length ؛ i ++) {temparray [i] = tarray [i] ؛ {system.out.println ("خطأ ، العنصر في المكدس فارغ ، لا يمكن أن ينظر إليه") ؛ إرجاع -1 ؛} آخر {return tarray [topIndex] ؛ i = 0 ؛ i <= topIndex ؛ i ++) {system.out.print (tarray [i]+"") ؛} system.out.println () ؛}}3. Chainqueue في قائمة انتظار محاكاة مع قوائم مرتبطة
package com.wly.algorithmbase.datustructure ؛/** * استخدم قائمة مرتبطة لتنفيذ قائمة الانتظار * * author wly * */class public classequeue {private queuenode head ؛ // تشير إلى رأس قائمة قائمة الانتظار الخاصة () من قائمة الانتظار*/public void insert (queuenode node) {// بالطبع ، يمكنك أيضًا كتابة هذا ، إضافة tail.prev = node if (head == null) {head = node ؛ tail = head ؛} else {node.next = tail.prev = node ؛ عقدة رأس قائمة الانتظار*/public queuenode remove () {if (! isempty ()) {queuenode temp = head ؛ head = head.prev ؛ size-؛ return temp ؛} else {system.out.println ("استثناء عملية ، قائمة الانتظار الحالية فارغة!") ؛ 0. Size***/regurn*/public int size () {size return ؛}/***** العناصر الطباعة في قائمة الانتظار*/public void printelems () {queuenode tempnode = head ؛ بينما (tempnode! = null) {system.out.print (tempnode.data + ") ؛ tempnode. فئة العقدة * * Author wly * */class queuenode {queuenode prev ؛ queuenode next ؛ int data ؛ queuenode public (int data) {this.data = data ؛} public int getData () {return data ؛} public void setData (int data) كوب Super.ToString () ؛ إرجاع بيانات + "" ؛}}4. Test Test_BFS_DFS
package com.wly.algorithmbase.search ؛ import com.wly.algorithmbase.datustructure. {// تهيئة اختبار بيانات nodirectiongraph graph = new NodirectionGraph (7) ؛ graph.addvertex (جديد graphvertex ("a") GraphVertex ("E")) ؛ Graph.addvertex (GraphVertex جديد ("F")) ؛ Graph.addvertex (جديد GraphVertex ("G")) ؛ Graph.adDedge (0 ، 1) ؛ Graph.adDedge (0 ، 2) ؛ Graph.addedge (1 ، 3) ؛ Graph.addedge (1 ، 4) ؛ 5) ؛ system.out.println ("-مصفوفة مجاورة من الرسم البياني-") ؛ graph.printIndicAtormat () ؛ // اختبار Search System.out.println ("-البحث العميق-") ؛ Graph.dfs (0) ؛ Graph = new Nodirectiongraph (7) ؛ GraphVertex ("B")) ؛ graph.addvertex (جديد GraphVertex ("C")) ؛ Graph.addvertex (GraphVertex جديد ("D") 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) ؛ system.println ("-shore prienity search-")هيكل الرسم البياني الذي تم اختباره هنا على النحو التالي:
نتائج التشغيل كما يلي:
--Adjacent matrix of graph-- 0 1 1 0 0 0 0 1 0 0 1 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 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 للبحث في العمق القائم على الرسم البياني والبحث في الرمز الكامل للبحث عن الرسم البياني. آمل أن يكون ذلك مفيدًا للجميع. يمكن للأصدقاء المهتمين الاستمرار في الرجوع إلى الموضوعات الأخرى ذات الصلة على هذا الموقع. إذا كانت هناك أي أوجه قصور ، فيرجى ترك رسالة لإشارةها. شكرا لك يا أصدقائك لدعمكم لهذا الموقع!