ALevel-CS Chapter 22
Artificial Intelligence(AI)
22.01 An overview
Artificial Intelligence Overview
Artificial Intelligence is concerned with “how to make computers do things at which, at the moment, people are better.”
22.02 How graphs can be used in AI
How graphs can be used in AI
A graph is a collection of nodes or vertices between which there can be edges. Each node has a name. An edge can have an associated label which is a numerical value.
Nodes represent places and the edge labels represent the distances between those places.
Edges are only included in the graph when there is a route available for direct travel between the pair of nodes.
path | distance |
---|---|
For A to B to C to D | overall distance is 40 + 10 + 40 = 90 |
For A to B to F to E to D | overall distance is 40 + 15 + 20 + 5 = 80, which is the shortest |
For A to F to E to D | overall distance is 60 + 20 + 5 = 85 |
For A to F to B to C to D | overall distance is 60 + 15 + 10 + 40 = 125 |
图论预习知识
Dijkstra 算法
Dijkstra算法是典型最短路算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。
大概过程:
创建两个表,OPEN, CLOSE。
OPEN表保存所有已生成而未考察的节点,CLOSED表中记录已访问过的节点。
1. 访问路网中里起始点最近且没有被检查过的点,把这个点放入OPEN组中等待检查。
2. 从OPEN表中找出距起始点最近的点,找出这个点的所有子节点,把这个点放到CLOSE表中。
3. 遍历考察这个点的子节点。求出这些子节点距起始点的距离值,放子节点到OPEN表中。
4. 重复2,3,步。直到OPEN表为空,或找到目标点。
Dijkstra 和 A* 算法比较
dijkstra 算法
A* 算法
- Dijkstra算法计算源点到其他所有点的最短路径长度,A*关注点到点的最短路径(包括具体路径)。
- Dijkstra算法建立在较为抽象的图论层面,A*算法可以更轻松地用在诸如游戏地图寻路中。
- Dijkstra算法的实质是广度优先搜索,是一种发散式的搜索,所以空间复杂度和时间复杂度都比较高。对路径上的当前点,A*算法不但记录其到源点的代价,还计算当前点到目标点的期望代价,是一种启发式算法,也可以认为是一种深度优先的算法。
- 由第一点,当目标点很多时,A*算法会带入大量重复数据和复杂的估价函数,所以如果不要求获得具体路径而只比较路径长度时,Dijkstra算法会成为更好的选择。
Dijkstra’s algorithm
Dijkstra’s algorithm finds the shortest path to each of the other nodes starting from one of the nodes.
Structured English
Identify the source node (S) where the path starts.
Create an empty set called the ShortestPath set.
Create another set called RemainingNodes and put all of the nodes into this including the source node (S).
Create a record that stores:
node names
calculated values for the distance to the node from the source node
the sequence of nodes in the route to the node.
Set the distance value for the source node S to be 0.
Set the distance value for all other nodes to be INFINITY where this is to be set as a large value greater than any value that will be calculated.
While the ShortestPath set does not include all of the nodes do the following:
Pick the node (N) from the RemainingNodes set that has the lowest distance value.
Move this node into the ShortestPath set.
For each node in the RemainingNodes set that is adjacent to N:
Calculate a new distance value by adding the value given by the label of the edge connecting the two nodes to the already stored distance for N.
If this value is less than the value currently stored replace this stored value by the new one that has been calculated.
If a new value has been stored enter the sequence of nodes used to obtain this value.
A* algorithm
A algorithm* - find the best route from one node to just one other node
# Dijkstra
Calculate a new distance value by adding the value given by the label of the edge
connecting the two nodes to the already stored distance for N.
# A*
Calculate a new distance value by adding the value given by the label of the edge
connecting the two nodes to the already stored distance for N.
Calculate an estimated value for the distance of N from the destination node and
add this to the new distance value.
22.03 Machine learning
Key Terms
- Machine learning - where a system improves its performance through analysis of previous performance
- Unsupervised learning - where the machine learning takes place entirely through the system analysing and categorising the available data
- Supervised learning - where sample data is supplied to the system with associated data relating to the outcome of its use
- Reinforcement learning - where an agent learns by receiving graded rewards for actions taken
- Regression analysis - finding a mathematical function that provides the best fit to the actual outcomes when outcomes are calculated from previous inputs
监督学习(supervised learning)
监督学习(supervised learning)的任务是学习一个模型,使模型能够对任意给定的输入,对其相应的输出做出一个好的预测。
即:利用训练数据集学习一个模型,再用模型对测试样本集进行预测。
分类问题(离散)与回归问题(连续)等都是监督学习。
无监督学习(unsupervised learning)
无监督学习(unsupervised learning)为直接对数据进行建模。没有给定事先标记过的训练范例,所用的数据没有属性或标签这一概念。事先不知道输入数据对应的输出结果是什么。
自动对输入的资料进行分类或分群,以寻找数据的模型和规律。
聚类,降维
强化学习
强化学习是机器学习的另一个领域。它关注的是软件代理如何在一个环境中采取行动以便最大化某种累积的回报。一句话:给定数据,学习如何选择一系列行动,以最大化长期收益。
动态规划、马尔科夫决策
Machine learning
- a computer-based system has a defined task or tasks to perform
- knowledge is acquired through the experience of performing the tasks
- as a result of this experience and the knowledge gained the performance of future tasks is improved.
unsupervised learning
In unsupervised learning the system has to draw its own conclusions from its experience of the results of the tasks it has performed.
Powerful computer systems having access to massive data banks are regularly used to make decisions based on previous actions recorded.
supervised learning
In supervised learning the system is fed knowledge with associated classification.
A special case of supervised learning is where an expert system is being developed. An expert system always has a focus on a narrowly defined domain of knowledge.
Reinforcement learning
Reinforcement learning has some features similar to unsupervised learning and other features similar to supervised learning.
- An agent is learning how best to perform in an environment.
- The environment has many defined states.
- At each step the agent takes an action.
- An agent has a policy that guides its actions.
- The policy is influenced by the recorded history and the knowledge of the current state of the environment.
- An action changes the environment to a new state.
- The agent receives a reward following an action which is a measure of how effective the action was in relation to the achievement of the overall goal.
- The policy will guide the agent in deciding whether the next action should be exploiting knowledge already known or exploring a new avenue.
In summary, the aim is to maximise the reward values by improving the quality of the policy. It is a trial-and-error search for optimum performance. It requires many repeated attempts at the same problem.
Regression analysis methods
In some applications the aim of the AI is to predict and provide, as output numerical values for some defined quantity, on the basis of data values for different quantities that have been input to the AI algorithm.
The simplest application of regression analysis is when values for only one quantity are to be input and when a linear relationship is expected between these values and the values to be predicted.
22.04 Artificial neural networks
Key Terms
- Back propagation of errors - An algorithm for machine learning that optimises the values for parameters which are adjustable. It is applied first to the nodes in the output layer and then works backward through the nodes in hidden layers until finally the input nodes are considered.
- Deep learning - where a system uses an artificial neural network with an exceptionally large number of hidden layers
神经网络辅助阅读
Neural networks
Artificial neural networks should be considered as a foundation for artificial intelligence systems.
Neural networks
schematic representation
Deep Learning
With the increasing computing power now available, artificial neural networks are being introduced with large numbers of hidden layers which are attempting to achieve something similar. These are known as Deep Learning systems.