深度优先解城市交通问题

vlambda
2020-04-23

深度优先解城市交通问题

点击上方“蓝字”，关注我们.

前言：

因为作者选修了人工智能导论课程，最近有一个实验催交的紧，所以不得不写了这个实验。实验中用到了深度优先遍历策略，考虑到之前分享深度优先有关的文章部分朋友看不懂，所以，我觉得再写一篇文章，使用深度优先法解决城市交通问题，希望对各位有所帮助。

正文

题目描述：

使用启发式搜索策略A算法解决城市交通问题，要求:

已知图中是6个城市间的交通费用图。
若从甲城出发，要求把每个城市都访问一遍，且只能访问一遍，最后又回到甲城。
输出搜索树拓展的每一步。
输出一条或者所有可能的路径。

深度优先解城市交通问题

大致思路：

谈到深度优先策略，首先应该想到的，是回朔，题目要求从甲城出发进行访问，首先判断将要访问的城市是否已被访问，如果已经被访问，就选择相邻的下一个城市，如果没有，就访问到这个城市，继续进行判断。让遇到当前所在城市不存在满足条件的可能的情况时，就往回退，即回朔，然后继续对下一个相邻城市进行判断和访问。以此重复下去，直到访问完所有城市为止。(需要注意的是当访问到最后一个城市时，不要急着输出结果，还需要去判断该城市是否能到甲城)。

程序演示：

dao对象实现，该对象只含有一个成员变量lhm，它用于存放每个城市对象相邻的城市名及与这些城市相连的交通费用。

import java.util.LinkedHashMap;public class dao { LinkedHashMap<String,Integer> lhm = new LinkedHashMap<String,Integer>();}

变量声明。

 private String n[]={"甲","乙","丙","丁","戊","己"};  //存储所有城市名 private int totalPrice=0;      //当前所花费的费用 private LinkedHashMap<String, dao> lhm=new LinkedHashMap<String, dao>();  //映射，用于存放城市名(key)-dao对象(value),关于dao对象的定义后面进行解析 LinkedHashMap<String, Integer> isLook=new LinkedHashMap<String, Integer>();  //记录城市的访问状态，0为未访问，1为已访问，城市名和状态为一一映射关系 LinkedList<String> con = new LinkedList<String>();  //容器，通过t索引 LinkedList<Integer> lhsI = new LinkedList<Integer>();  //记录结果集的key值，即总花费费用 LinkedList<String> lhsS = new LinkedList<String>();  //记录结果集的value值，即具体路径

构造器，对象被创建后，第一步把甲城市存入容器con中。

public demo() {if(!con.contains("甲")) con.add("甲"); }

初始化城市交通图，并打印输出查看结果。

public void init() {/*初始状态下城市的访问状态0为未访问，1为访问*/ isLook.put("甲",1); isLook.put("乙",0); isLook.put("丙",0); isLook.put("丁",0); isLook.put("戊",0); isLook.put("己",0);/*城市相邻情况及对应费用*/int price1[]={10,30,20}; initDao("甲","乙,丙,丁",price1);int price2[]={10,13,200}; initDao("乙","甲,丁,己",price2);int price3[]={30,15,20}; initDao("丙","甲,丁,戊",price3);int price4[]={20,13,15,180}; initDao("丁","甲,乙,丙,己",price4);int price5[]={20,100}; initDao("戊","丙,己",price5);int price6[]={200,180,100}; initDao("己","乙,丁,戊",price6); initShow(); }
private void initDao(String city,String str2,int price[]) { String split[];int i=0; split = str2.split(","); dao d=new dao();for(String item:split){ d.lhm.put(item, price[i]); i++; }this.lhm.put(city,d); }
private void initShow() { System.out.println("======================="); System.out.println("【已初始化交通图】"); String key; dao value; Iterator <Entry<String,dao>> iter = lhm.entrySet().iterator();while(iter.hasNext()) { Map.Entry<String, dao> entry = iter.next(); key = entry.getKey();value = entry.getValue(); System.out.println("----------"); System.out.println("-城市名:"+key); String key2;  Integer value2; Iterator <Entry<String,Integer>> iter2 = value.lhm.entrySet().iterator();while (iter2.hasNext()) { Map.Entry<String, Integer> entry2 = iter2.next(); key2 = entry2.getKey(); value2 = entry2.getValue(); System.out.println(" ￥"+value2+" "+key2);  } } System.out.println("======================="); }

打印结果：

深度优先解城市交通问题

程序核心部分，dfs算法的实现。

public void dfs(int t) {for(int i=1;i<=5;i++) { LinkedHashMap<String, Integer> ls = lhm.get(con.get(t)).lhm;if(isLook.get(n[i])==0 && ls.containsKey(n[i])) { System.out.print(" -->"+n[i]+" "); con.add(n[i]); isLook.put(n[i],1); totalPrice += ls.get(n[i]);if(t==4) { LinkedHashMap<String, Integer> ls2 = lhm.get(con.get(con.size()-1)).lhm;if(ls2.containsKey("甲")){ String str1="";for(String item: con) { str1 += (item+"-->"); } totalPrice += ls2.get("甲"); System.out.println(); System.out.println("推出路径:"+str1+"甲 "+totalPrice); lhsI.add(totalPrice); lhsS.add(str1); totalPrice -= ls2.get("甲"); } }else {          dfs(t+1);         } totalPrice -= ls.get(n[i]); System.out.println(" <--BackTo"+ con.get(t)+" "); isLook.put(n[i], 0); con.remove(t+1); } } }

主测试类编写。

public class test {  public static void main(String[] args){ demo d = new demo(); d.init(); System.out.println("======================="); System.out.println("【搜寻路径...】"); System.out.print("甲"); d.dfs(0); System.out.println("======================="); System.out.println("【搜寻结果...】");if(d.lhsI.size()==0)  System.out.println("没有搜寻到合适路径");else { System.out.println("总共有["+d.lhsI.size()+"]种路径:");for(int i=0;i<d.lhsI.size();i++) { System.out.println("总费用:"+d.lhsI.get(i)+" 路径:"+d.lhsS.get(i)+"甲"); } System.out.println("======================="); System.out.println("程序结束"); }}}