نمونه مثال برای الگوریتم a* astar که می تواند برای دانشجویان رشته هوش مصنوعی مفید باشد این الگوریتم به صورت گرافیکی گره ها رو گرفته و الگوریتم آ استار رو اجرا میکند و به زبان سی شارپ می باشد
? Introduction: what is it supposed to do
I dedicated myself to creating a .NET component that allows the building of graphs and the performance of some operations on these structures. In particular A*, the famous path finding algorithm, can be run to find the best path between two places.
First and foremost it should be kept in mind that a graph is defined with :
- A list of nodes
- A list of arcs
Each node is defined with the following data :
- A geographical position in space (co-ordinates X,Y,Z)
- The collection of the outgoing arcs
- The collection of the incoming arcs
?*what is a
Imagine that you are on a node and that you want to reach another position somewhere else on the graph. Then ask : “Which way will I follow, and why ?”. The main factor to take into account here is the cost of moving. It must be minimal. The cost criterion is basically a function of the distance (sum of arcs’ lengths). However, it can also be adjusted and varied with other data, which describe for example the slope, the harshness/practicability of the ground. You can even model a traffic jam.
To achieve the best path, there are many algorithms which are more or less effective, depending on the particular case. Efficiency depends not only on the time needed for calculation, but also on the reliability of the result. A* is able to return the best path (if it exists) between two nodes, according to accessibility/orientation and, of course, cost of arcs.
Among the variety of existing algorithms, some do not always actually return the best path, but they can give precedence to speed over accuracy. Efficiency depends on the number of nodes and on their geographical distribution. However in most cases A* turns out to be the most effective, because it combines optimized search with the use of a heuristic.
A heuristic is a function that associates a value with a node to gauge it. One node is considered better than another, if the final point is reached with less effort (e.g. shorter distance).
A* will always return the shortest path if, and only if, the heuristic is admissible; that is to say, if it never overestimates. On the other hand, if the heuristic is not admissible, A* will find a path in less time and with less memory usage, but without the absolute guaranty that it is the best one. Here are three admissible heuristics which correspond to a particular distance between the node of evaluation and the target node :
- Euclidean distance > Sqrt(Dx²+Dy²+Dz²)
- Manhattan distance > |Dx|+|Dy|+|Dz|
- Maximum distance > Max(|Dx|, |Dy|, |Dz|)
These functions give an estimation of the remaining distance for each node that can be explored. Thus the search can be oriented toward the ‘best’ nodes. For a given node, the sum [Current cost + Heuristic value] is an estimation of the cost of reaching the ending node from the starting node, passing by the current one. This value is used to continuously choose the most promising path.
In practice, the algorithm maintains 2 lists of nodes that are filled and modified during the search :
- The first one, called
Open, contains the tracks leading to nodes that can be explored. Initially, there is only the starting node. At each step, the best node of
Openis taken out. Then, the best successor of this node (according to the heuristic) is added to the list as a new track. One doesn’t know where the nodes that are in
Openlead, because they have not been propagated yet. However, the best one is examined at each new step.
- The second one, called
Closed, stores the tracks leading to nodes that have already been explored.
دانلود کد سورس الگوریتم a* به همراه فایل اجرایی (این کد سورس به زبان سی شارپ می باشد)
لطفا کپی رایت رو رعایت فرمایید در غیر این صورت دزدی محسوب می شود.