import heapq
创新互联一直在为企业提供服务，多年的磨炼，使我们在创意设计，网络营销推广到技术研发拥有了开发经验。我们擅长倾听企业需求，挖掘用户对产品需求服务价值，为企业制作有用的创意设计体验。核心团队拥有超过十年以上行业经验，涵盖创意，策化，开发等专业领域，公司涉及领域有基础互联网服务重庆服务器托管、成都app软件开发、手机移动建站、网页设计、网络整合营销。
from collections import defaultdict
edges = [["A","B"],["A","D"],["A","E"],["B","C"],["C","E"],["D","E"],["D","C"]]
dist = [10,30,100,50,10,60,20]
res = []
def dijkstra(e,dist,start,end):
hm = defaultdict(list)
for i in range(len(e)):
hm[e[i][0]].append((e[i][1],dist[i]))
r = {}
r = 0
q = [(0,start,)]
while q:
dis,node,res = heapq.heappop(q)
if node == end:
return dis,res
for u,v in hm[node]:
t = dis+v
if u not in r or t r[u]:
r[u] = t
heapq.heappush(q,(t,u,res+[u]))
return 0,[]
dijkstra(edges,dist,"A","E")
C语言代码：//清华大学出版社光盘的代码
void ShortestPath_DIJ(MGraph G,int v0,PathMatrix P,ShortPathTable D)
{ // 算法7.15
// 用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]
// 及其带权长度D[v]。
// 若P[v][w]为TRUE，则w是从v0到v当前求得最短路径上的顶点。
// final[v]为TRUE当且仅当v∈S,即已经求得从v0到v的最短路径。
int i=0,j, v,w,min;
bool final[MAX_VERTEX_NUM];
for (v=0; vG.vexnum; ++v) {
final[v] = FALSE;
D[v] = G.arcs[v0][v].adj;
for (w=0; wG.vexnum; ++w) P[v][w] = FALSE; // 设空路径
if (D[v] INFINITY) { P[v][v0] = TRUE; P[v][v] = TRUE; }
}
D[v0] = 0; final[v0] = TRUE; // 初始化，v0顶点属于S集
//--- 开始主循环，每次求得v0到某个v顶点的最短路径，并加v到S集 ---
for (i=1; iG.vexnum; ++i) { // 其余G.vexnum-1个顶点
min = INFINITY; // 当前所知离v0顶点的最近距离
for (w=0; wG.vexnum; ++w)
if (!final[w]) // w顶点在V-S中
if (D[w]min) { v = w; min = D[w]; } // w顶点离v0顶点更近
final[v] = TRUE; // 离v0顶点最近的v加入S集
for (w=0; wG.vexnum; ++w) // 更新当前最短路径及距离
if (!final[w] (min+G.arcs[v][w].adjD[w])) {
// 修改D[w]和P[w], w∈V-S
D[w] = min + G.arcs[v][w].adj;
for(j=0;jG.vexnum;j++) P[w][j] = P[v][j]; //第v行赋值于第w行
P[w][w] = TRUE; // P[w] = P[v]+[w]
}//if
}//for
} // ShortestPath_DIJ
一本书上的练习题,刚编的.注释用的日文字体,看不懂记得提问.
import java.util.*;
public class Search {
Node node[];
Node start;
Node goal;
Search() {
makeStateSpace();
}
private void makeStateSpace() {
node = new Node[10];
// 状态空间の生成
node[0] = new Node("L.A.Airport", 0);
start = node[0];
node[1] = new Node("UCLA", 7);
node[2] = new Node("Hollywood", 4);
node[3] = new Node("Anaheim", 6);
node[4] = new Node("Grand Canyon", 1);
node[5] = new Node("SanDiego", 2);
node[6] = new Node("Downtown", 3);
node[7] = new Node("Pasadena", 4);
node[8] = new Node("DisneyLand", 2);
node[9] = new Node("Las Vegas", 0);
goal = node[9];
node[0].addChild(node[1], 1);
node[0].addChild(node[2], 3);
node[1].addChild(node[2], 1);
node[1].addChild(node[6], 6);
node[2].addChild(node[3], 6);
node[2].addChild(node[6], 6);
node[2].addChild(node[7], 3);
node[3].addChild(node[4], 5);
node[3].addChild(node[7], 2);
node[3].addChild(node[8], 4);
node[4].addChild(node[8], 2);
node[4].addChild(node[9], 1);
node[5].addChild(node[1], 1);
node[6].addChild(node[5], 7);
node[6].addChild(node[7], 2);
node[7].addChild(node[8], 1);
node[7].addChild(node[9], 7);
node[8].addChild(node[9], 5);
}
/***
* 幅优先探索
*/
public void breadthFirst() {
ListNode open = new ArrayListNode();
open.add(start);
ListNode closed = new ArrayListNode();
boolean success = false;
int step = 0;
for (;;) {
System.out.println("STEP:" + (step++));
System.out.println("OPEN:" + open.toString());
System.out.println("CLOSED:" + closed.toString());
// openは空か？
if (open.size() == 0) {
success = false;
break;
} else {
// openの先头を取り出し node とする．
Node node = open.get(0);
open.remove(0);
// node は ゴールか？
if (node == goal) {
success = true;
break;
} else {
// node を展开して子节点をすべて求める．
ArrayListNode children = node.getChildren();
// node を closed に入れる．
closed.add(node);
// 子节点 m が open にも closed にも含まれていなければ，
for (int i = 0; i children.size(); i++) {
Node m = (Node) children.get(i);
if (!open.contains(m) !closed.contains(m)) {
// m から node へのポインタを付ける．
m.setPointer(node);
if (m == goal) {
open.add(0, m);
} else {
open.add(m);
}
}
}
}
}
}
if (success) {
System.out.println("*** Solution ***");
printSolution(goal);
}
}
/***
* 深さ优先探索
*/
public void depthFirst() {
ListNode open = new ArrayListNode();
open.add(start);
ListNode closed = new ArrayListNode();
boolean success = false;
int step = 0;
for (;;) {
System.out.println("STEP:" + (step++));
System.out.println("OPEN:" + open.toString());
System.out.println("CLOSED:" + closed.toString());
// openは空か？
if (open.size() == 0) {
success = false;
break;
} else {
// openの先头を取り出し node とする．
Node node = open.get(0);
open.remove(0);
// node は ゴールか？
if (node == goal) {
success = true;
break;
} else {
// node を展开して子节点をすべて求める．
ArrayListNode children = node.getChildren();
// node を closed に入れる．
closed.add(node);
// 子节点 m が open にも closed にも含まれていなければ，
// 以下を実行．幅优先探索と异なるのはこの部分である．
// j は复数の子节点を适切にopenの先头に置くために位置
// を调整する変数であり，一般には展开したときの子节点
// の位置は任意でかまわない．
int j = 0;
for (int i = 0; i children.size(); i++) {
Node m = (Node) children.get(i);
if (!open.contains(m) !closed.contains(m)) {
// m から node へのポインタを付ける
m.setPointer(node);
if (m == goal) {
open.add(0, m);
} else {
open.add(j, m);
}
j++;
}
}
}
}
}
if (success) {
System.out.println("*** Solution ***");
printSolution(goal);
}
}
/***
* 分岐限定法
*/
public void branchAndBound() {
ListNode open = new ArrayListNode();
open.add(start);
start.setGValue(0);
ListNode closed = new ArrayListNode();
boolean success = false;
int step = 0;
for (;;) {
System.out.println("STEP:" + (step++));
System.out.println("OPEN:" + open.toString());
System.out.println("CLOSED:" + closed.toString());
// openは空か？
if (open.size() == 0) {
success = false;
break;
} else {
// openの先头を取り出し node とする．
Node node = open.get(0);
open.remove(0);
// node は ゴールか？
if (node == goal) {
success = true;
break;
} else {
// node を展开して子节点をすべて求める．
ListNode children = node.getChildren();
// node を closed に入れる．
closed.add(node);
for (int i = 0; i children.size(); i++) {
Node m = (Node) children.get(i);
// 子节点mがopenにもclosedにも含まれていなければ，
if (!open.contains(m) !closed.contains(m)) {
// m から node へのポインタを付ける．
m.setPointer(node);
// nodeまでの评価値とnode-mのコストを
// 足したものをmの评価値とする
int gmn = node.getGValue() + node.getCost(m);
m.setGValue(gmn);
open.add(m);
}
// 子节点mがopenに含まれているならば，
if (open.contains(m)) {
int gmn = node.getGValue() + node.getCost(m);
if (gmn m.getGValue()) {
m.setGValue(gmn);
m.setPointer(node);
}
}
}
}
}
open = sortUpperByGValue(open);
}
if (success) {
System.out.println("*** Solution ***");
printSolution(goal);
}
}
/***
* 山登り法
*/
public void hillClimbing() {
start.setGValue(0);
boolean success = false;
// Start を node とする．
Node node = start;
for (;;) {
// node は ゴールか？
if (node == goal) {
success = true;
break;
} else {
// node を展开して子节点をすべて求める．
ArrayListNode children = node.getChildren();
System.out.println(children.toString());
for (int i = 0; i children.size(); i++) {
Node m = children.get(i);
// m から node へのポインタを付ける．
m.setPointer(node);
}
// 子节点の中に goal があれば goal を node とする．
// なければ，最小の hValue を持つ子节点 m を node
// とする．
boolean goalp = false;
Node min = children.get(0);
for (int i = 0; i children.size(); i++) {
Node a = children.get(i);
if (a == goal) {
goalp = true;
} else if (min.getHValue() a.getHValue()) {
min = a;
}
}
if (goalp) {
node = goal;
} else {
node = min;
}
}
}
if (success) {
System.out.println("*** Solution ***");
printSolution(goal);
}
}
/***
* 最良优先探索
*/
public void bestFirst() {
ListNode open = new ArrayListNode();
open.add(start);
ListNode closed = new ArrayListNode();
boolean success = false;
int step = 0;
for (;;) {
System.out.println("STEP:" + (step++));
System.out.println("OPEN:" + open.toString());
System.out.println("CLOSED:" + closed.toString());
// openは空か？
if (open.size() == 0) {
success = false;
break;
} else {
// openの先头を取り出し node とする．
Node node = open.get(0);
open.remove(0);
// node は ゴールか？
if (node == goal) {
success = true;
break;
} else {
// node を展开して子节点をすべて求める．
ListNode children = node.getChildren();
// node を closed に入れる．
closed.add(node);
for (int i = 0; i children.size(); i++) {
Node m = (Node) children.get(i);
// 子节点mがopenにもclosedにも含まれていなければ，
if (!open.contains(m) !closed.contains(m)) {
// m から node へのポインタを付ける．
m.setPointer(node);
open.add(m);
}
}
}
}
open = sortUpperByHValue(open);
}
if (success) {
System.out.println("*** Solution ***");
printSolution(goal);
}
}
/***
* A* アルゴリズム
*/
public void aStar() {
ListNode open = new ArrayListNode();
open.add(start);
start.setGValue(0);
start.setFValue(0);
ListNode closed = new ArrayListNode();
boolean success = false;
int step = 0;
for (;;) {
System.out.println("STEP:" + (step++));
System.out.println("OPEN:" + open.toString());
System.out.println("CLOSED:" + closed.toString());
// openは空か？
if (open.size() == 0) {
success = false;
break;
} else {
// openの先头を取り出し node とする．
Node node = open.get(0);
open.remove(0);
// node は ゴールか？
if (node == goal) {
success = true;
break;
} else {
// node を展开して子节点をすべて求める．
ListNode children = node.getChildren();
// node を closed に入れる．
closed.add(node);
for (int i = 0; i children.size(); i++) {
Node m = children.get(i);
int gmn = node.getGValue() + node.getCost(m);
int fmn = gmn + m.getHValue();
// 各子节点mの评価値とポインタを设定する
if (!open.contains(m) !closed.contains(m)) {
// 子节点mがopenにもclosedにも含まれていない场合
// m から node へのポインタを付ける．
m.setGValue(gmn);
m.setFValue(fmn);
m.setPointer(node);
// mをopenに追加
open.add(m);
} else if (open.contains(m)) {
// 子节点mがopenに含まれている场合
if (gmn m.getGValue()) {
// 评価値を更新し，m から node へのポインタを付け替える
m.setGValue(gmn);
m.setFValue(fmn);
m.setPointer(node);
}
} else if (closed.contains(m)) {
if (gmn m.getGValue()) {
// 子节点mがclosedに含まれていて fmn fm となる场合
// 评価値を更新し，mからnodeへのポインタを付け替える
m.setGValue(gmn);
m.setFValue(fmn);
m.setPointer(node);
// 子节点mをclosedからopenに移动
closed.remove(m);
open.add(m);
}
}
}
}
}
open = sortUpperByFValue(open);
}
if (success) {
System.out.println("*** Solution ***");
printSolution(goal);
}
}
/***
* 解の表示
*/
public void printSolution(Node theNode) {
if (theNode == start) {
System.out.println(theNode.toString());
} else {
System.out.print(theNode.toString() + " - ");
printSolution(theNode.getPointer());
}
}
/***
* Vector を Node の fValue の升顺（小さい顺）に列べ换える．
*/
public ListNode sortUpperByFValue(ListNode theOpen) {
ListNode newOpen = new ArrayListNode();
Node min, tmp = null;
while (theOpen.size() 0) {
min = (Node) theOpen.get(0);
for (int i = 1; i theOpen.size(); i++) {
tmp = (Node) theOpen.get(i);
if (min.getFValue() tmp.getFValue()) {
min = tmp;
}
}
newOpen.add(min);
theOpen.remove(min);
}
return newOpen;
}
/***
* Vector を Node の gValue の升顺（小さい顺）に列べ换える．
*/
public ListNode sortUpperByGValue(ListNode theOpen) {
ListNode newOpen = new ArrayListNode();
Node min = null, tmp = null;
while (theOpen.size() 0) {
min = theOpen.get(0);
for (int i = 1; i theOpen.size(); i++) {
tmp = theOpen.get(i);
if (min.getGValue() tmp.getGValue()) {
min = tmp;
}
}
newOpen.add(min);
theOpen.remove(min);
}
return newOpen;
}
/***
* Vector を Node の hValue の升顺（小さい顺）に列べ换える．
*/
public ListNode sortUpperByHValue(ListNode theOpen) {
ListNode newOpen = new ArrayListNode();
Node min, tmp = null;
while (theOpen.size() 0) {
min = (Node) theOpen.get(0);
for (int i = 1; i theOpen.size(); i++) {
tmp = (Node) theOpen.get(i);
if (min.getHValue() tmp.getHValue()) {
min = tmp;
}
}
newOpen.add(min);
theOpen.remove(min);
}
return newOpen;
}
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
String s = in.next();
if (s.length() != 1) {
System.out.println("USAGE:");
System.out.println("java Search [Number]");
System.out.println("[Number] = 1 : Bredth First Search");
System.out.println("[Number] = 2 : Depth First Search");
System.out.println("[Number] = 3 : Branch and Bound Search");
System.out.println("[Number] = 4 : Hill Climbing Search");
System.out.println("[Number] = 5 : Best First Search");
System.out.println("[Number] = 6 : A star Algorithm");
} else {
int which = Integer.parseInt(s);
switch (which) {
case 1:
// 幅优先探索
System.out.println("\nBreadth First Search");
(new Search()).breadthFirst();
break;
case 2:
// 深さ优先探索
System.out.println("\nDepth First Search");
(new Search()).depthFirst();
break;
case 3:
// 分岐限定法
System.out.println("\nBranch and Bound Search");
(new Search()).branchAndBound();
break;
case 4:
// 山登り法
System.out.println("\nHill Climbing Search");
(new Search()).hillClimbing();
break;
case 5:
// 最良优先探索
System.out.println("\nBest First Search");
(new Search()).bestFirst();
break;
case 6:
// A*アルゴリズム
System.out.println("\nA star Algorithm");
(new Search()).aStar();
break;
default:
System.out.println("Please input numbers 1 to 6");
}
}
}
}
class Node {
String name;
ArrayListNode children;
MapNode, Integer childrenCosts;
Node pointer; // 解表示のためのポインタ
int gValue; // コスト
int hValue; // ヒューリスティック値
int fValue; // 评価値
boolean hasGValue = false;
boolean hasFValue = false;
Node(String theName, int theHValue) {
name = theName;
children = new ArrayListNode();
childrenCosts = new HashMapNode, Integer();
hValue = theHValue;
}
public String getName() {
return name;
}
public void setPointer(Node theNode) {
this.pointer = theNode;
}
public Node getPointer() {
return this.pointer;
}
public int getGValue() {
return gValue;
}
public void setGValue(int theGValue) {
hasGValue = true;
this.gValue = theGValue;
}
public int getHValue() {
return hValue;
}
public int getFValue() {
return fValue;
}
public void setFValue(int theFValue) {
hasFValue = true;
this.fValue = theFValue;
}
/***
* theChild この节点の子节点 theCost その子节点までのコスト
*/
public void addChild(Node theChild, int theCost) {
children.add(theChild);
childrenCosts.put(theChild, theCost);
}
public ArrayListNode getChildren() {
return children;
}
public int getCost(Node theChild) {
return ((Integer) childrenCosts.get(theChild)).intValue();
}
public String toString() {
String result = name + "(h:" + hValue + ")";
if (hasGValue) {
result = result + "(g:" + gValue + ")";
}
if (hasFValue) {
result = result + "(f:" + fValue + ")";
}
return result;
}
}
我用的是递归调用方法，有个小问题就是在打印步数的时候是返向的，原因是就是程序不断的调用自己，到最后判断基值位准退出调用。这才开始从栈里取出方法进行执行的原因。
代码欣赏：
public static int step = 1;
public static StringBuffer printStep = new StringBuffer();
public static int[][] maze ={{1,1,1,1,1,1,1,1,1,1,1},
{1,0,1,0,1,0,0,0,0,0,1 },
{1,0,1,0,0,0,1,0,1,1,1 },
{1,0,0,0,1,0,1,0,0,0,1 },
{1,0,1,1,0,0,1,0,0,1,1 },// 0代表可以通过，1代表不可通过
{1,0,1,0,1,1,0,1,0,0,1 },
{1,0,0,0,0,0,0,0,1,0,1 },
{1,0,1,0,1,0,1,0,1,0,1 },
{1,0,0,1,0,0,1,0,1,0,1 },
{1,1,1,1,1,1,1,1,1,1,1 } };
public static void main(String[] args) {
int i, j; //循环记数变量
Sample.way(1, 1);//二维数组起始值从下标1，1开始
System.out.println("起点从坐标 x = 1, y = 1开始");
System.out.println("终点坐标是 x = 8, y = 9结束");
System.out.println("这是迷宫图表");
System.out.println(" 0 1 2 3 4 5 6 7 8 9 10");
System.out.println(" +---+---+---+---+---+---+---+---+---+---+---+---+---+");
for(i = 0; i 10; i++){
System.out.print(" " + i + "‖");
for(j = 0; j 11; j++)
System.out.print("-" + maze[i][j] + "-‖");
System.out.println("");
System.out.println(" +---+---+---+---+---+---+---+---+---+---+---+---+---+");
}
//打印显示步数
System.out.print(printStep.toString());
}
public static boolean way(int x, int y){
if(maze[8][9] == 2)//代表递归终止条件（也就是当走出出口时标记为 2）
return true;
else{
if(maze[y][x] == 0){
maze[y][x] = 2;
/*
* 下面if判断条件代表当前坐标为基点，
* 根据判断对当前位置进行递归调用：如：
* 往上、往右上、往右、往右下、往下、
* 往左下、往左、往左上的坐标是否可走，
* 判断是否可走的返回条件是：
* 2代表可通过、1代表不能通过、3表示已经走过，但是未能走通。
*/
if(way(x, y - 1)){
printStep.append("第 " + step + " 步的所走的位置是 x = " + x + " y = " + y + "\n");
step++;
return true;
}else if(way(x + 1, y - 1)){
printStep.append("第 " + step + " 步的所走的位置是 x = " + x + " y = " + y + "\n");
step++;
return true;
}else if(way(x + 1 , y)){
printStep.append("第 " + step + " 步的所走的位置是 x = " + x + " y = " + y + "\n");
step++;
return true;
}else if(way(x + 1, y + 1)){
printStep.append("第 " + step + " 步的所走的位置是 x = " + x + " y = " + y + "\n");
step++;
return true;
}else if(way(x, y + 1)){
printStep.append("第 " + step + " 步的所走的位置是 x = " + x + " y = " + y + "\n");
step++;
return true;
}else if(way(x - 1, y + 1)){
printStep.append("第 " + step + " 步的所走的位置是 x = " + x + " y = " + y + "\n");
step++;
return true;
}else if(way(x - 1, y)){
printStep.append("第 " + step + " 步的所走的位置是 x = " + x + " y = " + y + "\n");
step++;
return true;
}else if(way(x - 1, y - 1)){
printStep.append("第 " + step + " 步的所走的位置是 x = " + x + " y = " + y + "\n");
step++;
return true;
}else{
maze[y][x] = 3;
return false;
}
}else
return false;
}
}
复制代码前需要楼主自己创建个 类
Sample.way(1, 1);这句代码是我的类的静态调用，改下XXXXX.way(1, 1);
XXXXX代表你创建的类。
下面是这个程序运行后的截图
