Application of A Star Algorithm
INTRODUCTION
In computer science, A* is a computer algorithm that is widely used in path finding and graph traversal, the process of plotting an efficiently directed path between multiple points, called nodes. It enjoys widespread use due to its performance and accuracy. However, in practical travel-routing systems, it is generally outperformed by algorithms which can pre-process the graph to attain better performance, although other work has found A* to be superior to other approaches.
Peter Hart, Nils Nilsson and Bertram Raphael of Stanford Research, first described the algorithm in 1968. It is an extension of Edsger Dijkstra#39;s 1959 algorithm. A* achieves better performance by using heuristics to guide its search.
HISTORY
In 1968, AI researcher Nils Nilsson was trying to improve the path planning done by Shakey the Robot, a prototype robot that could navigate through a room containing obstacles. This path-finding algorithm, which Nilsson called A1, was a faster version of the then best known method, Dijkstra#39;s algorithm, for finding shortest paths in graphs. Bertram Raphael suggested some significant improvements upon this algorithm, calling the revised version A2. Then Peter E. Hart introduced an argument that established A2, with only minor changes, to be the best possible algorithm for finding shortest paths. Hart, Nilsson and Raphael then jointly developed a proof that the revised A2 algorithm was optimal for finding shortest paths under certain well-defined conditions.
Concept of A star Logarithm
A* is a network searching algorithm that takes a 'distance-to-goal path-cost' score into consideration. As it traverses the network searching all neighbors, it follows lowest score path keeping a sorted priority queue of alternate path segments along the way. If at any point the path being followed has a higher score than other encountered path segments, the higher score path is abandoned and a lower score sub-path traversed instead. This continues until the goal is reached.
Properties
A* has the following properties:
- It is complete; it will always find a solution if it exists.
- It can use a heuristic to significantly speed up the process.
- It can have variable node to node movement costs. This enables things like certain nodes or paths being more difficult to traverse, for example an adventurer in a game moves slower across rocky terrain or an airplane takes longer going from one destination to another.
- It can search in many different directions if desired.
How it works
It works by maintaining two lists; the open list and the closed list. The open listrsquo;s purpose is to hold potential best path nodes that have not yet been considered, starting with the start node. If the open list becomes empty then there is no possible path. The closed list starts out empty and contains all nodes that have already been considered/visited.
The core loop of the algorithm selects the node from the open list with the lowest estimated cost to reach the goal. If the selected node is not the goal it puts all valid neighboring nodes into the open list and repeats the process.
Part of the magic in the algorithm is that all created nodes keep a reference to their parent. This means that itrsquo;s possible to backtrack back to the start node from any node created by the algorithm.
Algorithm description
A* is an informed search algorithm, or a best-first search, meaning that it solves problems by searching among all possible paths to the solution (goal) for the one that incurs the smallest cost (least distance travelled, shortest time, etc.), and among these paths it first considers the ones that appear to lead most quickly to the solution. It is formulated in terms of weighted graphs: starting from a specific node of a graph, it constructs a tree of paths starting from that node, expanding paths one step at a time, until one of its paths ends at the predetermined goal node.It does so based on an estimate of the cost (total weight) still to go to the goal node. Specifically, A* selects the path that minimizes
f(n)=g(n) h(n){\displaystyle f(n)=g(n) h(n)}
where n is the last node on the path, g(n) is the cost of the path from the start node to n, and h(n) is a heuristic that estimates the cost of the cheapest path from n to the goal. The heuristic is problem-spe
全文共20845字，剩余内容已隐藏，支付完成后下载完整资料
A星算法的应用
介绍
在计算机科学中，A星是一种计算机算法，被广泛应用于路径发现和图的遍历。策划有效路径之间的多个点的过程，称为节点。它的广泛使用由于其性能和精度。然而，在实际的行驶路线系统，它一般是优于算法的预处理过程图以达到更好的性能。其他工作者已经发现了一个要优于其他方法的A星。Peter Hart，Nils(尼尔森)和Bertram Raphael(斯坦福)的研究，1968年首次介绍了算法。这是一个扩展Edsger Dijkstra1959算法。A星采用启发式指导其搜索性能。
背景
在1968年，AI研究员nils nilsson试图提高路径规划的Shakey机器人，机器人系统可以通过房间中的障碍。这个路径寻找算法，尼尔森称之为A1，是一个更快的版本，当时也是最著名的方法，Dijkstra算法，最短路径图。伯特伦拉斐尔提出了一些显着的改进后，该算法，调用修订版A2。然后彼得E哈特介绍了一个论点，建立A2，只有轻微的变化，是寻找最短路径的最佳算法。哈特，尼尔森和拉斐尔又共同开发了一个证明，修订的A2算法是在某些明确的条件下寻找最短路径的最佳选择。
星对数概念
A星是一种以“距离目标路径代价”为代价的网络搜索算法。当它遍历搜索所有邻居的网络时，它遵循最低分数路径，保持沿途的备用路径段的排序优先级队列。如果在任何时间点跟踪的路径具有比其他遇到的路径段更高的分数，则更高的分数路径被放弃，而较低的分数子路径被代替。这一直持续到目标达成。
属性
A 星具有以下属性：
- 是完整的；它总是会找到一个解决方案，如果它存在。
- 可以使用启发式显着加快的过程。
- 可以有变量节点到节点的移动成本。这使得某些节点或路径变得更难以遍历，例如游戏中的冒险家在岩石地形上移动较慢，或者飞机从一个目的地到另一个目的地需要更长的时间。
- 可以搜索许多不同的方向发展，如果需要的话。
运作原理
它通过维护两个列表来工作：开启列表和关闭列表。开放列表的目的是保存尚未考虑的潜在的最佳路径节点，从起始节点开始。如果开启列表变为空，则没有可能的路径。关闭列表开始清空，包含已被考虑/访问的所有节点。
算法的核心循环从开启列表中选择具有最低估计成本的节点来实现目标。如果所选节点不是目标，则将所有有效的相邻节点放入开启列表中并重复该过程。
算法的一部分魔法是所有创建的节点都保留对其父节点的引用。 这意味着可以从算法创建的任何节点回溯到起始节点。
算法描述/介绍
A星是一个知情的搜索算法，或最佳优先搜索，这意味着解决问题时，通过搜索所有可能的路径中的解决方案（目标）的一个招成本最小（最小距离、短时间、等），在这些路径首先认为出现来最快的解决方案导致的。它是在加权图表述：从一个特定的节点一图，构建了一个路径从节点树 扩张路径，一步一个脚印，直到其中一个路径的末端在预定的目标node.it是基于成本估算（总重量）还是到目标节点。具体而言，A星选择的路径，最大限度地减少
f(n)=g(n) h(n){\displaystyle f(n)=g(n) h(n)}
在N在路径上的节点，G（n）从开始节点n的路径的成本，和h（n）是启发式估计最便宜的路径成本从N的目标。启发式是问题的具体。为找到实际的最短路径的算法，启发式函数必须受理，这意味着它不会高估到最近的目标节点的实际成本。
A星典型的实现使用一个优先级队列执行最小的重复选择（估计）成本节点扩展。这是优先级队列称为开集或条纹。在算法的每一步，以最低的f（x）的节点 值从队列中移除，F和G的值邻国相应的更新，而这些邻居都添加到队列。该算法将持续到目标节点有一个较低的F值比队列中的任何节点（或直到队列为空）。的F价值目标则是最短路径的长度，因为H的目标是零容许启发式。
迄今为止所描述的算法只给出最短路径的长度。为了找到实际的步骤序列，该算法可以很容易地修改，以便在路径上的每个节点跟踪其前身。该算法运行后，结束节点将指向它的前身，等等，直到一些节点的前身是开始节点。
例如，当在地图上搜索最短路径，H（X）可能代表直线距离的目标，因为这是身体上的任何两点之间的最小距离。
如果启发式H满足附加条件H（X）le;D（X，Y） H（Y）每边（X，Y）的图（其中D表示该边的长度），然后他叫单调，或一致。在这种情况下，一个可以更有效地实现粗略地讲，任何节点需要处理超过一次（seeclosed集以下）和A*相当于与降低成本D运行Dijkstra算法 Drsquo;（X，Y）= D（x，y） H（Y）minus; h（x）。
P/伪代码
功能A星（开始，目标）
closedset：=空集 /节点已经评价集。
阐述：=集包含初始节点 /试验节点进行评估设定。
g_score [开始]：= 0 / /距离开始沿着最优路径。
h_score [开始]：= heuristic_estimate_of_distance（开始，目标）
f_score [开始]：= h_score [开始] / /预计总距离从开始到目标
当开启列表不是空
x：=节点在开集具有最低的f_score [ ]值
如果X =目标
回到reconstruct_path（came_from，删除目标）
把X从开启列表中删掉
将X添加关闭列表中
Foreach Y在neighbor_nodes（x）
如果y 在closedset
继续
tentative_g_score：= g_score [x] dist_between（X，Y）
如果Y不在开启列表中
将Y添加到开启列表中
tentative_is_better：=真
另外
tentative_is_better：=假
如果tentative_is_better： =真
came_from [Y]
g_score [Y]：= tentative_g_score
h_score [Y]：= heuristic_estimate_of_distance（Y，目标）
f_score [Y]：= g_score [Y] h_score [Y]
返回失败
功能重建路径（当前节点）
如果[当前节点]被设置
p =重建路径（来自[当前节点]）
返回（P 当前节点）
另外
返回当前节点
特性
像广度优先搜索，一个是完成永远如果存在提供固定找到解决的办法。如果启发式函数H是受理，这意味着它不会高估了达到目标的实际成本最小化，然后A星本身是容许的（oroptimal）如果我们做不要使用一个闭集。如果一个封闭的装置，然后H也必须单调（或 一致）为A星是最优的。这意味着，任何对相邻节点的X和Y，哪里表示它们之间的边的长度，我们必须：
h(x) le;d(x,y) h(y)
这将确保任何路径X从初始节点到X：
L(x) h(x)le;L(x) d(x,y) h(y)=L(Y) h(y)
在L是表示一个路径长度的函数，和Y是路径X扩展到包括Y。换句话说，它是不可能减少（总有那么远的距离估计的剩余距离）通过扩展路径包括相邻节点。（这是类似于限制的非负边权重在Dijkstra算法。）单调性意味着当在受理任何目标节点本身的启发式估计为零，因为（让P=（f，V1，V2，hellip;，Vn，G）是一个最短路径从任何节点F的最近的目标G）：
h(f)le;d(f,v1) h(v1)le;d(f,v1) d(v1,v2) h(v2)le;hellip;le;L(P) h(g)=L(P)
A星也是最佳的高效的启发式的h，这意味着没有优化算法采用相同的启发式扩展节点比A星少，除了当有多个部分的解决方案，H准确预测最优路径的成本。即使在这种情况下，对于每个图中存在的优先级队列中的一些断裂的顺序，这样一个A*检查最少的可能的节点。
特殊情况;
一般来说，深度优先搜索和广度优先搜索是A星算法的两种特殊情况。Dijkstra算法，作为另一个例子，一个最好的搜索算法，是一个A星h（x）= 0的特殊情况所有X。深度优先搜索，我们可以考虑有一个全局计数器C具有非常大的值初始化。每一次我们过程中的一个节点我们分配C其所有新发现的邻居。每次分配后，我们将计数器C减一。因此早期的节点被发现，更高的h（x）价值。
实施细节
有许多简单的优化或实现细节，可以显着影响性能的A星实现。要注意的第一个细节是优先级队列处理连接的方式在某些情况下对性能有显著影响。如果关系破裂，队列的行为在一个后进先出的方式，一个不会像深度优先搜索等成本路径之间。如果连接被破坏，所以队列的行为在FIFO的方式，一个A星将表现为广度优先搜索平等的成本路径。当搜索结束时需要一条路径时，将每个节点与该节点的父节点保持一致是很常见的。在搜索结束时，这些引用可以被用来恢复最佳路径。如果这些引用被保留，那么重要的是，同一个节点不会出现在优先级队列中不止一次（每个条目对应于不同的路径的节点，并且每一个不同的成本）。这里的标准方法是检查在优先级队列中是否将要添加的节点是否出现。如果有，则将优先级和父指针更改为对应于较低成本的路径。当在队列中找到一个节点执行此检查时，许多标准实现的最小堆需要O（n）的时间。用哈希表充实堆可以将其减少到常数时间。
为什么A星是可以接受和计算最优的
一个是容许且考虑节点比其他任何容许的搜索算法具有相同的启发式少，因为作品从一条路径的成本的一个“乐观”的估计，通过每一个节点，它认为乐观是真实成本的路径通过节点到目标将至少为估计是伟大的。但是，严格地说，就“知道”而言，乐观的估计可能是可以实现的。
当一个A星终止其搜索时，根据定义，它找到了一条路径，其实际成本低于任何开放节点的任何路径的估计成本。但由于这些估计是乐观的，一个A星可以安全地忽略这些节点。换句话说，一个A星永远不会忽视的可能性较低的成本路径，所以是允许的。
现在假设其他搜索算法B终止搜索路径的实际成本是 不 小于路径的估计成本，通过一些开放的结。算法B不能排除的可能性，它的启发式信息的基础上，通过该节点的路径可能有一个较低的成本。因此，虽然B可能考虑较少的节点比一个A星，它不能被允许。因此，A星认为任何允许的搜索算法，使用一个更准确的启发式估计的节点最少的节点。
这是唯一真实的A星使用容许启发式。否则，A星不保证扩展更少的节点比另一个搜索算法具有相同的启发式。
A星只解决一个搜索问题而不是一系列相似的搜索问题。否则，一个不能保证扩大节点比 增量启发式搜索算法少 。
星对数的复杂性
A星时间复杂度取决于启发式。在最坏的情况下，节点的数量扩张是指数在解的长度（最短路径），但它是多项式当搜索空间是一棵树，有一个单一的目标状态，和启发式函数H满足以下条件：
|h (x) minus;h*(x)| =O(log h*(x))
在H*是最优的启发式，即从X对目标的精确成本。换句话说，对H误差不增长比“完美的启发式”H*返回从X真实距离目标的对数更快。
可采性和最优性
一个是 容许 考虑节点比其他任何容许的搜索算法具有相同的启发式少。这是因为一个A星使用一个“乐观”的成本估计的路径通过每一个节点，它认为乐观的真正成本的路径通过该节点的目标将至少一样大的估计。但是，严格地说，就“知道”而言，乐观的估计可能是可以实现的。
为了证明A星的可容许性，算法返回的解路径如下：
当A星终止搜索时，它发现了一条路径，其实际成本低于任何开放节点的任何路径的估计成本。但由于这些估计是乐观的，一个A星可以安全地忽略这些节点。换句话说，一个A星永远不会忽视的可能性较低的成本路径，所以是允许的。现在假设一些其他的搜索算法B终止搜索路径的实际成本是 不 小于路径的估计成本，通过一些开放的结。基于启发式信息，算法B不能排除的可能性，通过该节点的路径具有较低的成本。因此，虽然B可能考虑较少的节点比A星少，它不能被允许。因此，A星认为任何允许搜索算法的节点最少。
如果这是真的：只有A星使用 容许启发式。否则，A星不保证扩展更少的节点比另一个搜索算法具有相同
全文共6784字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[144617]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
