## 2012年10月15日 星期一

### [ Algorithm ] Route search problem - Using A* algorithm

Question :

Greedy Best-first Search:

f(n) = h(n)

1. package c3.route;
2.
3. import java.util.HashMap;
4. import java.util.PriorityQueue;
5. import java.util.Set;
6. import java.util.TreeSet;
7.
8. import ai.utils.searchs.Graph;
9. import ai.utils.searchs.SNode;
10. import ai.utils.searchs.proto.INode;
11.
12. public class GreedyBFS {
13.     public static String GOAL= "Bucharest";     /*Setup your goal*/
14.     public static String INITIAL = "Arad";      /*Setup your initial state here.*/
15.     public static Graph g;
16.     public static HashMap heuristicMap = new HashMap();
17.     public static Set deadEndSet = new TreeSet();
18.     public static boolean IS_DONE = false;
19.
20.     public static class NodeWrapper implements Comparable{
21.         INode node;
22.         int sld=0;
23.         public NodeWrapper(INode n, int v){node=n; sld=v;}
24.
25.         @Override
26.         public int compareTo(NodeWrapper o) {
27.             if(sld < o.sld) return -1;
28.             else if(sld > o.sld) return 1;
29.             return 0;
30.         }
31.     }
32.
33.     /**
34.      * BD : Create Romania graph
35.      * @return
36.      */
37.     public static Graph prepareRomania()
38.     {
39.         Graph g = new Graph();
60.
84.
86.         heuristicMap.put("Bucharest"0);
87.         heuristicMap.put("Craiova"160);
88.         heuristicMap.put("Drobeta"242);
89.         heuristicMap.put("Eforie"161);
90.         heuristicMap.put("Fagaras"176);
91.         heuristicMap.put("Giurgiu"77);
92.         heuristicMap.put("Hirsova"151);
93.         heuristicMap.put("Iasi"226);
94.         heuristicMap.put("Lugoj"244);
95.         heuristicMap.put("Neamt"234);
97.         heuristicMap.put("Pitesti"100);
98.         heuristicMap.put("Rimnicu Vilcea"193);
99.         heuristicMap.put("Sibiu"253);
100.         heuristicMap.put("Timisoara"329);
101.         heuristicMap.put("Urziceni"80);
102.         heuristicMap.put("Vaslui"199);
103.         heuristicMap.put("Zerind"374);
105.         return g;
106.     }
107.
108.
109.     public static void RecvBFS(INode node, INode from, String path, int depth)
110.     {
111.         // If the current node is Goal, stop searching.
112.         if(node.getName().equals(GOAL))
113.         {
114.             System.out.printf("\t[Info] Path: %s->%s\n", path, GOAL);
115.             IS_DONE = true;
116.             return;
117.         }
118.
119.         if(depth>0 && !IS_DONE)
120.         {
121.             /* 1) Get all connected nodes from current node*/
122.             Set conn = g.getConnectNodes(node);
123.
124.             /* 2) If only one connected node and it is the 'from' node. Skip it and add into dead-end set.*/
125.             if(conn.size()==1 && conn.iterator().next().equals(from))
126.             {
128.                 return;
129.             }
130.
131.             if(conn!=null)
132.             {
133.                 PriorityQueue queue = new PriorityQueue();
134.                 for(INode sn:conn)
135.                 {
136.                     /* 3) Skip expansion for dead-end or the 'from' node*/
138.
139.                     /* 4) Add node into priority queue. Next will pickup the 'best-first' node with smallest estimation cost.*/
141.                 }
142.
143.                 /* 5) Expand the connected node(s).*/
144.                 while(!queue.isEmpty())
145.                 {
146.                     NodeWrapper n = queue.poll();
147.                     RecvBFS(n.node, node, path.isEmpty()?node.getName():String.format("%s->%s", path, node.getName()), depth-1);
148.                     if(IS_DONE) break;
149.                 }
150.             }
151.         }
152.         else
153.         {
154.             // If the depth outside the limit or the searching is done.
155.         }
156.     }
157.
158.     /**
159.      * @param args
160.      */
161.     public static void main(String[] args) {
162.         g = prepareRomania();
164.         RecvBFS(arad, null""10); // Limit depth to within 10 during searching.
165.     }
166. }

A* Search :

f(n) = g(n) + h(n)

1. package c3.route;
2.
3. import java.util.HashMap;
4. import java.util.PriorityQueue;
5. import java.util.Set;
6. import java.util.TreeSet;
7.
8. import ai.utils.searchs.Edge;
9. import ai.utils.searchs.Graph;
10. import ai.utils.searchs.SNode;
11. import ai.utils.searchs.proto.INode;
12.
13. public class AStarSearch {
14.     public static String GOAL= "Bucharest"/*Setup your goal*/
15.     public static String INITIAL = "Arad";      /*Setup your initial state here.*/
16.     public static Graph g;
17.     public static HashMap heuristicMap = new HashMap();
18.     public static Set deadEndSet = new TreeSet();
19.     public static boolean IS_DONE = false;
20.
21.     public static class ENode implements Comparable
22.     {
23.         public double gcost = 0;
24.         public double estim = 0;
25.         public INode curNode = null;
26.         public String from="";
27.
28.         public ENode(ENode s, INode en, double cost, double estim)
29.         {
30.             if(s!=null)
31.             {
32.                 from = String.format("%s->%s", s.from, en.getName());
33.                 gcost = s.gcost+cost;
34.             }
35.             else
36.             {
37.                 from = en.getName();
38.                 gcost = cost;
39.             }
40.             curNode = en;
41.         }
42.
43.         /**
44.          * BD: Evaluation f(n) = g(n) + h(n)
45.          * @return
46.          */
47.         public double overallCost(){return gcost+estim;}
48.
49.         @Override
50.         public int compareTo(ENode n) {
51.             if(overallCost()>n.overallCost()) return 1;
52.             else if(overallCost()return -1;
53.             return 0;
54.         }
55.
56.     }
57.
58.     /**
59.      * BD: Create Romania graph
60.      * @return
61.      */
62.     public static Graph prepareRomania()
63.     {
64.         Graph g = new Graph();
65.         // Nodes
86.
87.         // Edges
111.
112.         // Heuristic function/map
114.         heuristicMap.put("Bucharest"0);
115.         heuristicMap.put("Craiova"160);
116.         heuristicMap.put("Drobeta"242);
117.         heuristicMap.put("Eforie"161);
118.         heuristicMap.put("Fagaras"176);
119.         heuristicMap.put("Giurgiu"77);
120.         heuristicMap.put("Hirsova"151);
121.         heuristicMap.put("Iasi"226);
122.         heuristicMap.put("Lugoj"244);
123.         heuristicMap.put("Neamt"234);
125.         heuristicMap.put("Pitesti"100);
126.         heuristicMap.put("Rimnicu Vilcea"193);
127.         heuristicMap.put("Sibiu"253);
128.         heuristicMap.put("Timisoara"329);
129.         heuristicMap.put("Urziceni"80);
130.         heuristicMap.put("Vaslui"199);
131.         heuristicMap.put("Zerind"374);
133.         return g;
134.     }
135.
136.     /**
137.      * @param args
138.      */
139.     public static void main(String[] args) {
140.         /* 0) Prepare Romania graph*/
141.         g = prepareRomania();
142.
143.         /* 1) Decide initial state and put into priority queue*/
145.         PriorityQueue enQueue = new PriorityQueue();
147.
148.         /* 2) Loop to search the goal*/
149.         //   2.1: Pickup smallest f(n) of node to expand
150.         //   2.2: Check if the selected node is Goal. Yes to terminate the loop
151.         //   2.3: Put the expanded nodes into priority queue.
152.         while(!enQueue.isEmpty())
153.         {
154.             ENode en = enQueue.poll();
155.             if(en.curNode.getName().equals(GOAL))
156.             {
157.                 System.out.printf("\t[Info] Path=%s(%.01f)\n", en.from, en.overallCost());
158.                 break;
159.             }
160.             Set edgeSet = g.getConnectEdge(en.curNode);
161.             for(Edge e:edgeSet)
162.             {
163.                 //System.out.printf("%s\n", e);
164.                 enQueue.add(new ENode(en, e.to, e.weight, heuristicMap.get(e.to.getName())));
165.             }
166.         }
167.     }
168. }

A* Search 可以找到從 Arad 到 Bucharest 的最佳路徑 (cost=418), 演算法的過程如下示意圖:

### [ Python 常見問題 ] python generator “send” function purpose?

Source From  Here   Question   Can someone give me an example of why the "send" function associated with Python generator function...