守望者--AIR技术交流

 找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

搜索
热搜: ANE FlasCC 炼金术
查看: 833|回复: 1

[数学算法] 广度优先遍历公交路线寻路算法JAVA实现

[复制链接]
  • TA的每日心情
    擦汗
    2017-11-3 12:47
  • 签到天数: 441 天

    [LV.9]以坛为家II

    1741

    主题

    2093

    帖子

    13万

    积分

    超级版主

    Rank: 18Rank: 18Rank: 18Rank: 18Rank: 18

    威望
    517
    贡献
    24
    金币
    51073
    钢镚
    1421

    开源英雄守望者

    发表于 2016-7-4 18:05:12 | 显示全部楼层 |阅读模式
    是算法为测试算法,仅供参考

    RoadUtil.java

    1. package com.swift.util;

    2. import java.util.ArrayList;
    3. import java.util.HashMap;
    4. import java.util.List;
    5. import java.util.Map;

    6. import com.swift.dao.PointsDaoImpl;
    7. import com.swift.dao.RoadDaoIpml;
    8. import com.swift.util.tree.Node;

    9. /**
    10. * 广度优先遍历       
    11. */       
    12. public class RoadUtil {
    13.        
    14.         private static Map<Integer, Node> allNode = null;
    15.        
    16.        
    17.         /**
    18.          * 根据ID获取站点名称
    19.          * @param pid
    20.          * @return
    21.          */
    22.         public static String getNameById(int pid)
    23.         {
    24.                 if(allNode == null)
    25.                                 buildTree();
    26.                 return allNode.get(pid).name;
    27.         }
    28.        
    29.         public static Map<String, Object> findRoad(int start, int end)
    30.         {
    31.                 if(start == end) return null;
    32.                 Map<String, Object> result = new HashMap<String, Object>();
    33.                 if(allNode == null)
    34.                         buildTree();
    35.                
    36.                 Node sn = allNode.get(start);
    37.                 Node en = allNode.get(end);
    38.                 List<Node> findNodes = new ArrayList<Node>();   // 已遍历节点
    39.                 List<Node> currentNodes = new ArrayList<Node>();   // 当前到达节点
    40.                
    41.                 findNodes.add(sn);
    42.                 currentNodes.add(sn);
    43.                
    44.                 List<HashMap<String, Object>> road = new ArrayList<HashMap<String, Object>>();
    45.                 HashMap<String, Object> roadItem;
    46.                
    47.                 if(findRoadAI(currentNodes, en, findNodes))
    48.                 {
    49.                         Node temp = en;
    50.                         while(temp.parent != null && temp != sn)
    51.                         {
    52.                                 roadItem = new HashMap<String, Object>();
    53.                                 roadItem.put("id", temp.id);
    54.                                 roadItem.put("name", temp.name);
    55.                                 road.add(0, roadItem);
    56.                                 temp = temp.parent;
    57.                         }
    58.                        
    59.                         roadItem = new HashMap<String, Object>();
    60.                         roadItem.put("id", sn.id);
    61.                         roadItem.put("name", sn.name);
    62.                         road.add(0, roadItem);
    63.                 }
    64.                
    65.                 result.put("road", road);
    66.                 result.put("len", road.size());
    67.                
    68.                 return result;
    69.         }
    70.        
    71.        
    72.         /**
    73.          * 寻路AI 此方法无法用于多线程并发
    74.          * @param cNode
    75.          * @param end
    76.          * @param fNode
    77.          */
    78.         private static boolean findRoadAI(List<Node> cNode, Node end, List<Node> fNode)
    79.         {
    80.                 //TODO: 此方法无法用于多线程并发
    81.                 if(cNode.size() == 0) return false;
    82.                 List<Node> newCNode = new ArrayList<Node>();   // 当前到达节点
    83.                 for(Node item:cNode)
    84.                 {
    85.                         for(Node ci:item.children)
    86.                         {
    87.                                 if(ci == end)
    88.                                 {
    89.                                         ci.parent = item;
    90.                                         return true;
    91.                                 }
    92.                                 if(fNode.contains(ci))
    93.                                         continue;
    94.                                 ci.parent = item;
    95.                                 newCNode.add(ci);
    96.                                 fNode.add(ci);
    97.                         }
    98.                 }
    99.                 return findRoadAI(newCNode, end, fNode);
    100.         }
    101.        
    102.         /**
    103.          * 构建路线数
    104.          */
    105.         private static void buildTree()
    106.         {
    107.                 allNode = new HashMap<Integer, Node>();
    108.                
    109.                 PointsDaoImpl pdi = new PointsDaoImpl();
    110.                 Node item;
    111.                
    112.                 for(Map<String, Object> pi:pdi.getPoints())
    113.                 {
    114.                         item = new Node();
    115.                         item.id = (int) pi.get("id");
    116.                         item.name = (String) pi.get("pname");
    117.                         item.type = (int) pi.get("type");
    118.                
    119.                         allNode.put(item.id, item);
    120.                 }
    121.                
    122.                 RoadDaoIpml rdi = new RoadDaoIpml();
    123.                
    124.                 Node start = null;
    125.                 Map<String, Object> currentRoad = null;
    126.                 Node preItem = null;
    127.                 Node currentItem;
    128.                
    129.                 for(Map<String, Object> pi:rdi.getRoadPoints())
    130.                 {
    131.                         currentItem = allNode.get(pi.get("pointId"));
    132.                         if(currentRoad == null || !pi.get("roadId").equals(currentRoad.get("roadId")))  // 切换路线
    133.                         {
    134.                                 if(currentRoad != null && start != null && currentRoad.get("type").equals(2))
    135.                                 {
    136.                                         preItem.children.add(start);
    137.                                         start.children.add(preItem);
    138.                                        
    139. //                                        start.parent = preItem;
    140. //                                        preItem.parent = start;
    141.                                 }
    142.                                 currentRoad = pi;
    143.                                
    144.                                 start = currentItem;
    145.                         }
    146.                         else
    147.                         {
    148.                                 preItem.children.add(currentItem);
    149.                                 currentItem.children.add(preItem);
    150.                                
    151. //                                currentItem.parent = preItem;
    152. //                                preItem.parent = currentItem;
    153.                         }
    154.                         preItem = currentItem;
    155.                 }
    156.                
    157.                 // 如果最后一个站点是环形线路终点
    158.                 if(currentRoad != null && preItem != null && start != null && currentRoad.get("type").equals(2))
    159.                 {
    160.                         preItem.children.add(start);
    161.                         start.children.add(preItem);
    162.                        
    163. //                        start.parent = preItem;
    164. //                        preItem.parent = start;
    165.                 }
    166.                
    167.                 start = null;
    168.                 currentRoad = null;
    169.                 preItem = null;
    170.                 currentItem = null;
    171.         }
    172. }
    复制代码


    Node.java

    1. package com.swift.util.tree;

    2. import java.util.ArrayList;
    3. import java.util.List;

    4. public class Node{
    5.         public Node parent;
    6.         public List<Node> children = new ArrayList<>();
    7.         public String name;
    8.         public int type;
    9.         public int id;
    10. }
    复制代码


    RoadDaoIpml.java

    1. package com.swift.dao;

    2. import java.sql.ResultSet;
    3. import java.sql.SQLException;
    4. import java.util.ArrayList;
    5. import java.util.HashMap;
    6. import java.util.List;
    7. import java.util.Map;

    8. import com.swift.connect.DataBaseManager;

    9. public class RoadDaoIpml {
    10.        
    11.         public String addRoad()
    12.         {
    13.                 return null;
    14.         }
    15.        
    16.         public List<Map<String, Object>> getRoads()
    17.         {
    18.                 List<Map<String, Object>> resultList = new ArrayList<Map<String, Object>>();

    19.                 String sql = "select * from road order by Id";

    20.                 DataBaseManager db = null;

    21.                 try {
    22.                         db = DataBaseManager.getDefaultConnection();
    23.                         db.createStmt();
    24.                         ResultSet result = db.getResult(sql);

    25.                         Map<String, Object> item;

    26.                         while(result.next())
    27.                         {
    28.                                 item = new HashMap<String, Object>();
    29.                                 item.put("id", result.getInt("Id"));
    30.                                 item.put("rname", result.getString("rname"));
    31.                                 item.put("type", result.getInt("rtype"));
    32.                                 item.put("numpoint", result.getInt("numpoint"));

    33.                                 resultList.add(item);
    34.                         }
    35.                 } catch (Exception e) {
    36.                         // TODO Auto-generated catch block
    37.                         e.printStackTrace();
    38.                 }
    39.                 finally{

    40.                         if(db != null)
    41.                                 try {
    42.                                         db.close();
    43.                                 } catch (SQLException e) {
    44.                                         // TODO Auto-generated catch block
    45.                                         e.printStackTrace();
    46.                                 }
    47.                 }

    48.                 return resultList;
    49.         }

    50.         public List<Map<String, Object>> getRoadPoints()
    51.         {
    52.                 List<Map<String, Object>> resultList = new ArrayList<Map<String, Object>>();

    53.                 String sql = "select t1.pindex, t1.pointId,t1.roadId, t2.rname,t2.rtype, t2.numpoint " +
    54.                                 "from  roadpoint t1, road t2 " +
    55.                                 "where t2.Id = t1.roadId " +
    56.                                 "order by t2.Id, t1.pindex";

    57.                 DataBaseManager db = null;

    58.                 try {
    59.                         db = DataBaseManager.getDefaultConnection();
    60.                         db.createStmt();
    61.                         ResultSet result = db.getResult(sql);

    62.                         Map<String, Object> item;

    63.                         while(result.next())
    64.                         {
    65.                                 item = new HashMap<String, Object>();
    66.                                 item.put("pindex", result.getInt("pindex"));
    67.                                 item.put("rname", result.getString("rname"));
    68.                                 item.put("type", result.getInt("rtype"));
    69.                                 item.put("pointId", result.getInt("pointId"));
    70.                                 item.put("numpoint", result.getInt("numpoint"));
    71.                                 item.put("roadId", result.getInt("roadId"));

    72.                                 resultList.add(item);
    73.                         }
    74.                 } catch (Exception e) {
    75.                         // TODO Auto-generated catch block
    76.                         e.printStackTrace();
    77.                 }
    78.                 finally{

    79.                         if(db != null)
    80.                                 try {
    81.                                         db.close();
    82.                                 } catch (SQLException e) {
    83.                                         // TODO Auto-generated catch block
    84.                                         e.printStackTrace();
    85.                                 }
    86.                 }

    87.                 return resultList;
    88.         }
    89. }
    复制代码



    下面是获取数据的类  不重要  可以不看

    PointsDaoImpl.java

    1. package com.swift.dao;

    2. import java.sql.ResultSet;
    3. import java.sql.SQLException;
    4. import java.util.ArrayList;
    5. import java.util.HashMap;
    6. import java.util.List;
    7. import java.util.Map;

    8. import org.apache.log4j.Logger;

    9. import com.swift.connect.DataBaseManager;

    10. public class PointsDaoImpl {
    11.        
    12.         private static Logger logger = Logger.getLogger(PointsDaoImpl.class);
    13.        
    14.         public List<Map<String, Object>> getPoints()
    15.         {
    16.                 List<Map<String, Object>> resultList = new ArrayList<Map<String, Object>>();

    17.                 String sql = "select * from points order by ename";

    18.                 DataBaseManager db = null;

    19.                 try {
    20.                         db = DataBaseManager.getDefaultConnection();
    21.                         db.createStmt();
    22.                         ResultSet result = db.getResult(sql);

    23.                         Map<String, Object> item;

    24.                         while(result.next())
    25.                         {
    26.                                 item = new HashMap<String, Object>();
    27.                                 item.put("id", result.getInt("Id"));
    28.                                 item.put("pname", result.getString("pname"));
    29.                                 item.put("type", result.getInt("ptype"));
    30.                                 item.put("ename", result.getString("ename"));

    31.                                 resultList.add(item);
    32.                         }
    33.                         logger.info("########Points:");
    34.                         logger.info(resultList.size());
    35.                 } catch (Exception e) {
    36.                         // TODO Auto-generated catch block
    37.                         logger.error(e.toString());
    38.                         e.printStackTrace();
    39.                 }
    40.                 finally{

    41.                         if(db != null)
    42.                                 try {
    43.                                         db.close();
    44.                                 } catch (SQLException e) {
    45.                                         // TODO Auto-generated catch block
    46.                                         e.printStackTrace();
    47.                                 }
    48.                 }

    49.                 return resultList;
    50.         }
    51. }
    复制代码



    DataBaseManager.java

    1. package com.swift.connect;
    2. import java.sql.Connection;
    3. import java.sql.DriverManager;
    4. import java.sql.ResultSet;
    5. import java.sql.SQLException;
    6. import java.sql.Statement;
    7. import java.util.HashMap;

    8. import org.apache.log4j.Logger;

    9. import com.swift.util.ContextUtil;

    10. public class DataBaseManager
    11. {
    12.         private Connection con;
    13.         private ResultSet rs;
    14.         private Statement stmt;
    15.        
    16.         private static Logger logger = Logger.getLogger(DataBaseManager.class);
    17.        
    18.         /**
    19.          * @param url  例:jdbc:mysql://127.0.0.1/eshop
    20.          * @param user
    21.          * @param password
    22.          */
    23.         private DataBaseManager(String url, String user, String password)
    24.         {
    25.                 try{
    26.                         Class.forName( "com.mysql.jdbc.Driver" );
    27.                         // con=DriverManager.getConnection("jdbc:mysql://localhost:3306/eshop","root","123456");
    28.                         con=DriverManager.getConnection(url + "?user=" + user + "&password=" + password + "&allowMultiQueries=true&useUnicode=true&characterEncoding=UTF8");
    29.                         con.setAutoCommit(false);
    30.                 }
    31.                 catch ( ClassNotFoundException cnfex ) {
    32.                         logger.error("Failed to load JDBC/ODBC driver." );
    33.                         cnfex.printStackTrace();
    34.                         System.exit( 1 );  
    35.                 }
    36.                 catch(SQLException sqle)
    37.                 {
    38.                         sqle.printStackTrace();
    39.                         logger.error(sqle.toString());
    40.                 }
    41.         }
    42.        
    43.        
    44.         /**
    45.          * 查询数据库
    46.          * @param strSQL
    47.          * @return
    48.          */
    49.         public ResultSet getResult(String strSQL)
    50.         {
    51.                 try{
    52.                         rs=stmt.executeQuery(strSQL);
    53.                         return rs;
    54.                 }
    55.                 catch(SQLException sqle)
    56.                 {
    57.                         logger.error(sqle.toString());
    58.                         return null;
    59.                 }
    60.         }
    61.        
    62.         public Statement createStmt() throws SQLException
    63.         {
    64.                 stmt=con.createStatement(ResultSet.TYPE_SCROLL_SENSITIVE,ResultSet.CONCUR_UPDATABLE);
    65.                
    66.                 return stmt;
    67.         }
    68.        
    69.         /**
    70.          *  更新数据库
    71.          * @param strSQL
    72.          * @return
    73.          */
    74.         public boolean updateSql(String strSQL)
    75.         {
    76.                 try{
    77.                         stmt.executeUpdate(strSQL);
    78.                         con.commit();
    79.                         return true;
    80.                 }
    81.                 catch(SQLException sqle)
    82.                 {
    83.                         try {
    84.                                 con.rollback();
    85.                         } catch (SQLException e) {
    86.                                 // TODO Auto-generated catch block
    87.                                 e.printStackTrace();
    88.                         }
    89.                         logger.error(sqle.toString());
    90.                         return false;
    91.                 }
    92.                 finally
    93.                 {
    94.                        
    95.                 }
    96.         }
    97.        
    98.         /**
    99.          * 回收对象
    100.          * @throws SQLException
    101.          */
    102.         public void close() throws SQLException
    103.         {
    104.                 if(rs != null)
    105.                         rs.close();
    106.                 if(stmt != null)
    107.                         stmt.close();
    108.                
    109.                 closeConnection();
    110.                
    111.                 rs = null;
    112.                 stmt = null;
    113.                 con = null;
    114. //                stack.push(this);
    115.         }
    116.        
    117.         /**
    118.          * 关闭当前连接
    119.          */
    120.         public void closeConnection()
    121.         {
    122.                 try
    123.                 {
    124.                         if(con != null)
    125.                                 con.close();
    126.                 }
    127.                 catch(SQLException sqle)
    128.                 {
    129.                         logger.error(sqle.toString());
    130.                 }
    131.         }

    132.         /** 连接池堆栈 */
    133. //        private static Stack<DataBaseManager> stack = new Stack<DataBaseManager>();
    134.        
    135.        
    136.         /**
    137.          * @param url  例:jdbc:mysql://127.0.0.1/eshop
    138.          * @param user
    139.          * @param password
    140.          * @return
    141.          */
    142.         public static DataBaseManager getConnection(String url, String user, String password)
    143.         {
    144.                 logger.info("###DBinfo:");
    145.                 logger.info(url);
    146.                 logger.info(user);
    147.                 logger.info(password);
    148.                 return new DataBaseManager(url, user, password);
    149.         }
    150.        
    151.         public static DataBaseManager getDefaultConnection() throws Exception
    152.         {
    153.                 HashMap<String, String>  map = ContextUtil.getInstance().getDbCon();
    154.                
    155.                 return getConnection(map.get("url"), map.get("user"), map.get("password"));
    156.         }
    157. }
    复制代码


    ContextUtil.java

    1. package com.swift.util;

    2. import java.io.File;
    3. import java.net.URL;
    4. import java.util.HashMap;

    5. import javax.xml.parsers.DocumentBuilder;
    6. import javax.xml.parsers.DocumentBuilderFactory;

    7. import org.w3c.dom.Document;
    8. import org.w3c.dom.NamedNodeMap;

    9. /**
    10. * @author 破晓
    11. *
    12. */
    13. public class ContextUtil {
    14.         /**单例*/
    15.         private static ContextUtil instance;
    16.        
    17.         private HashMap<String, String> dbCon = null;
    18.         private HashMap<String, String> serverCon = null;
    19.        
    20.         /**
    21.          * 获取唯一实例
    22.          * @return
    23.          * @throws Exception
    24.          */
    25.         public static ContextUtil getInstance() throws Exception
    26.         {
    27.                 if(instance == null)
    28.                         instance = new ContextUtil();
    29.                
    30.                 return instance;
    31.         }

    32.         private ContextUtil() throws Exception
    33.         {
    34.                 initData();
    35.         }
    36.        
    37.         private void initData() throws Exception
    38.         {
    39.                 URL fileUrl = getClass().getResource("/config.xml");

    40.                 if(fileUrl != null)
    41.                 {
    42.                         String fileName = fileUrl.toURI().getPath();
    43.                         File f = new File(fileName);
    44.                         DocumentBuilderFactory factory = DocumentBuilderFactory.newInstance();
    45.                         DocumentBuilder builder = factory.newDocumentBuilder();
    46.                         Document doc = builder.parse(f);
    47.                        
    48.                         dbCon = new HashMap<String, String>();
    49.                         serverCon = new HashMap<String, String>();
    50.                        
    51.                         NamedNodeMap db = doc.getElementsByTagName("db").item(0).getAttributes();
    52.                         NamedNodeMap server = doc.getElementsByTagName("server").item(0).getAttributes();
    53.                         dbCon.put("url", db.getNamedItem("url").getNodeValue());
    54.                         dbCon.put("user", db.getNamedItem("user").getNodeValue());
    55.                         dbCon.put("password", db.getNamedItem("password").getNodeValue());
    56.                        
    57.                         serverCon.put("url", server.getNamedItem("url").getNodeValue());
    58.                 }
    59.         }

    60.         public HashMap<String, String> getDbCon() {
    61.                 return dbCon;
    62.         }
    63.        
    64.         public HashMap<String, String> getServerCon() {
    65.                 return serverCon;
    66.         }
    67. }
    复制代码





    本帖子中包含更多资源

    您需要 登录 才可以下载或查看,没有帐号?立即注册

    x
    守望者AIR技术交流社区(www.airmyth.com)
    回复

    使用道具 举报

  • TA的每日心情
    郁闷
    2016-8-19 16:08
  • 签到天数: 7 天

    [LV.3]偶尔看看II

    4

    主题

    31

    帖子

    2628

    积分

    少尉

    Rank: 6Rank: 6

    威望
    0
    贡献
    8
    金币
    320
    钢镚
    25
    发表于 2016-8-17 16:43:46 | 显示全部楼层
    不错。。。。。。。
    我是一个兵
    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    
    关闭

    站长推荐上一条 /4 下一条

    QQ|手机版|Archiver|网站地图|小黑屋|守望者 ( 京ICP备14061876号

    GMT+8, 2017-12-13 23:02 , Processed in 1.312500 second(s), 36 queries .

    守望者AIR

    守望者AIR技术交流社区

    本站成立于 2014年12月31日

    快速回复 返回顶部 返回列表