网站建设运行工作情况总结,岳阳市公共资源交易网,app哪个网站开发好,甘肃省建设厅建筑业信息网文章目录 1、问题描述2、节点类设置3、设置节点之间的关系4、路线规划5、完整类6、结果7、优化 1、问题描述
如下图#xff0c;存在A~F六个地点#xff0c;已知所有地点的相关关系#xff08;每个地点能到达的下一节点名称以及对应的路程#xff09;#xff1b;
计算某个… 文章目录 1、问题描述2、节点类设置3、设置节点之间的关系4、路线规划5、完整类6、结果7、优化 1、问题描述
如下图存在A~F六个地点已知所有地点的相关关系每个地点能到达的下一节点名称以及对应的路程
计算某个起点A~F到某个终点A~F所需要的路程以及经过的地点顺序2、节点类设置
public class Node {// 当前节点名称public String name;// 记录当前节点所能能到达的节点路程 节点名称对应的路程public MapString,Integer map new HashMapString,Integer();// 存储所有能到达节点的对象public ListNode nodeList new ArrayListNode();public Node(){}public Node(String name){this.name name;}public void setValue(String key,Integer value) {map.put(key,value);}public void setNode(Node node) {nodeList.add(node);}
}3、设置节点之间的关系
public static Node setRoute() {Node nodeA new Node(A);Node nodeB new Node(B);Node nodeC new Node(C);Node nodeD new Node(D);Node nodeE new Node(E);Node nodeF new Node(F);nodeA.setValue(B,10);nodeA.setValue(C,14);nodeA.setNode(nodeB);nodeA.setNode(nodeC);nodeB.setValue(A,10);nodeB.setValue(C,11);nodeB.setValue(D,8);nodeB.setNode(nodeA);nodeB.setNode(nodeC);nodeB.setNode(nodeD);nodeC.setValue(A,14);nodeC.setValue(B,11);nodeC.setValue(D,6);nodeC.setValue(E,15);nodeC.setNode(nodeA);nodeC.setNode(nodeB);nodeC.setNode(nodeD);nodeC.setNode(nodeE);nodeD.setValue(B,8);nodeD.setValue(C,6);nodeD.setValue(F,10);nodeD.setNode(nodeB);nodeD.setNode(nodeC);nodeD.setNode(nodeF);nodeE.setValue(C,15);nodeE.setValue(F,12);nodeE.setNode(nodeC);nodeE.setNode(nodeF);nodeF.setValue(D,10);nodeF.setValue(E,12);nodeF.setNode(nodeD);nodeF.setNode(nodeE);return nodeA; // 起点
}4、路线规划
/*** 计算到达某个节点所有的方式* param node 当前节点* param stepStr 所走过的路径避免重复* param steps 总路程* param endNode 终点节点*/
public static void calculate(Node node,String stepStr,Integer steps,String endNode) {if(!node.name.equals(endNode)) {ListNode nodeList node.nodeList;for (int i 0; i nodeList.size(); i) {Node n nodeList.get(i);if(stepStr.contains(n.name)) { continue; }String stepStrT stepStr - n.name;int stepsT steps node.map.get(n.name);calculate(n,stepStrT,stepsT,endNode);}}else {System.out.println(finish steps \t stepStr);}
}5、完整类
package Test;import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;// 路线规划
public class RoutePlanning {// 记录执行次数public static int num 0;public static void main(String[] args) {Node route setRoute();calculate(route,A,0,F);System.out.println(execute times: num);}/*** 计算到达某个节点所有的方式* param node 当前节点* param stepStr 所走过的路径避免重复* param steps 总路程* param endNode 终点节点*/public static void calculate(Node node,String stepStr,Integer steps,String endNode) {if(!node.name.equals(endNode)) {ListNode nodeList node.nodeList;for (int i 0; i nodeList.size(); i) {num;Node n nodeList.get(i);if(stepStr.contains(n.name)) { continue; }String stepStrT stepStr - n.name;int stepsT steps node.map.get(n.name);calculate(n,stepStrT,stepsT,endNode);}}else {System.out.println(finish steps \t stepStr);}}/*** 创建节点以及设置节点信息*/public static Node setRoute() {Node nodeA new Node(A);Node nodeB new Node(B);Node nodeC new Node(C);Node nodeD new Node(D);Node nodeE new Node(E);Node nodeF new Node(F);nodeA.setValue(B,10);nodeA.setValue(C,14);nodeA.setNode(nodeB);nodeA.setNode(nodeC);nodeB.setValue(A,10);nodeB.setValue(C,11);nodeB.setValue(D,8);nodeB.setNode(nodeA);nodeB.setNode(nodeC);nodeB.setNode(nodeD);nodeC.setValue(A,14);nodeC.setValue(B,11);nodeC.setValue(D,6);nodeC.setValue(E,15);nodeC.setNode(nodeA);nodeC.setNode(nodeB);nodeC.setNode(nodeD);nodeC.setNode(nodeE);nodeD.setValue(B,8);nodeD.setValue(C,6);nodeD.setValue(F,10);nodeD.setNode(nodeB);nodeD.setNode(nodeC);nodeD.setNode(nodeF);nodeE.setValue(C,15);nodeE.setValue(F,12);nodeE.setNode(nodeC);nodeE.setNode(nodeF);nodeF.setValue(D,10);nodeF.setValue(E,12);nodeF.setNode(nodeD);nodeF.setNode(nodeE);return nodeA;}public static class Node {// 当前节点名称public String name;// 记录当前节点所能能到达的节点路程public MapString,Integer map new HashMapString,Integer();// 存储所有到达的节点对象public ListNode nodeList new ArrayListNode();public Node(){}public Node(String name){this.name name;}public void setValue(String key,Integer value) {map.put(key,value);}public void setNode(Node node) {nodeList.add(node);}}
}
6、结果
finish37 A-B-C-D-F
finish48 A-B-C-E-F
finish51 A-B-D-C-E-F
finish28 A-B-D-F
finish43 A-C-B-D-F
finish30 A-C-D-F
finish41 A-C-E-F
execute times: 417、优化
优化每次遍历都判断所走路程详细记录已走的节点如果当前路程超过记录中的最大路程则停止
选中记录列表中的最小路程重新往下走重复该过程直到到达终点后
