|
这种算法希望找到一条路径, 能够将A地到Z地的航班数搞到最少. 算法使用的启发信息是: 算法认为航线长度越长, 那么接近目标的几率就越大, 于是航班的数量就会越少. 从AI的角度说, 这叫”爬山搜索”. 爬山算法选择看起来最接近目标的节点作为下一步处理的节点. 这里, 改动的是find()方法: FlightInfo find(String from) //找出离出发城市最远的航班 { int pos = -1; int dist = 0; for(int i=0; i < numFlights; i++) { if(flights[i].from.equals(from) && !flights[i].skip) { if(flights[i].distance > dist) { pos = i; dist = flights[i].distance; } } } if(pos != -1) { flights[pos].skip = true; FlightInfo f = new FlightInfo(flights[pos].from, flights[pos].to,flights[pos].distance); return f; } return null; } 一般来说, 爬山搜索都能找到比较理想的解, 因为它减少发现目标之前需要访问的节点数. 但是, 这种算法存在3个问题: (这是从人工智能的书上面弄下来的) 1. 存在所谓”错误山峰”的问题(即局部最优问题), 这会导致大量的回退; 2. “高原问题”: 在这种情况下, 所有下一步节点看起来都是一样的好(or 坏). 在这种情况先, 爬山搜索和深度优先搜索是一样的; 3. “山脊问题”: 这种情况将导致性能的降低, 因为在回退的时候, 算法会导致多次通过某个山脊. |
|
|
