当我在考虑最短路径算法和人生的时候我在想什么
In this article, I just want to illustrate two main questions that confused me recently. One is the assignment project in Artificial Intelligent, the other one is about the life. Strictly speaking, they are two unrelated things at all, however, when I considered it at the same time, I might coincidently find some relation between them, so I just mix them together and figure out what I am thinking about.
What is Pathfinding?
In graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized.
It’s so lucky that Pathfinding has its absolute definition, however, the real life problem doesn’t have one.
How to solve it?
The problem will become more easily to solve after setting up some formal notation. Let’s just use this graph for example.
SupposeA
is the start node, and I
is the end node, and set V
is a set of all nodes(vertex) in the graph,V = {n | n = A,B,C,D,E,F,G,H,I}
. The set E
is a set of all edges, simply we can use a 9*9 map to interpret each edge and its weight. Now we can just find the path from A
toI
, and just calculate the sum of weights, find the shortest one.
I used Matlab to implement it, and map(i,j)
represent the route cost between city i and j. Otherwise, map(i,j)=-1
means there is no route between city i and j. The function h(x)
represent the heuristic function value of city x to the endNode. With the heuristic function, we can call this type of searching technic as informed search. So we can calculate the function f(x)=f(x-1)+map(x)+h(x)
as the cost compared during searching.
Greedy (A*) algorithm
In my first case, I apply greedy algorithm to implement it. And there is recursion to keep expanding the best(lowest evaluation function value g(x)
,g(x)=map(x)+h(x)
) node, and because it is a greedy algorithm, the choice of the least costly node will not be revised. This is a very simple way to find the suboptimal path at the benefit of improvement of running time, however, because it doesn’t expand all nodes, thus it is usually not the true shortest path. Here is my implementation function search1():
|
|
A* algorithm
However, to find the optimal path, thanks to my partner, we need to implement other algorithm. Here we use A* algorithm, which means, with the admissible heuristics, we still need to use the uniform cost search method whose result ca be revised if another shortest path is found. The reason why adding the heuristics can help us to reduce the searching time is that we can faster find shorter path with less revision of the result(which means we try to assign the shortest path to each node at a less cost of time). Especially, if the heuristics are larger, the efficiency will be better. For example, a node’s cost may be the least in this loop, however, the path following it is very costly, and it is actually not the right node to be chosen. Therefore, to avoid this kind of situation, we plus the estimate cost (heuristic value)of the following path started from this node, which can help us discriminate the true low cost path easier and quicker.
a*的h()不等于零的情况下,能够比迪杰斯特拉算法高效的原因是,在结点的优先级上,因为加上了考虑h()函数,因此实际最终会被选择的结点被优先考虑选择的可能性更大。另外,在到达最终结点时,如果最终结点的开销比其他任何结点都还要小的时候,就可以结束循环,不需要等到所有未extend的结点(open队列中的)都遍历过,因为其他结点的f()值肯定是比经过这个结点的路径真实开销要小的,
h(n)<=g(end-n) -> real cost = g(n)+g(end-n)<=f()=g(n)+h(n),
,但是它仍然比目前到达终点的这条路径的开销大,因此可以判断,就算extend它,它的真实开销肯定会比目前已有的路径大(类似于minimax的剪枝),这个时候的heuristics就是admissible的,可以发现如果h(n)>g(end-n)
,就很有可能会变成局部最优而没有办法extend真实的最优路径了。
Here is the implementation of A*, the prequisite is that h(n)<=g(end-n)
|
|
How to solve real life problem?
Whereas, my life has no notation. What if I try to give it some notation? I try to conceptualise the real life problem by the algorithmic scope. For example, suppose the choices in my life are the vertexes, and the set of it is
|
|
But it is infinite, because I am not the “god”, I can not depict every vertexes now. I only know the nodes that I have met and the next reachable choices, however, I hardly know what will happen after I choose any one of them. Therefor, V* is an infinite set until I kill my life.
I want to seek happiness, suppose my start node is “be born”, and my end node is “be happy”(not “be dead”, I don’t need to find the shorted path to death….)which is my goal. Then the question can be translated like “how can I become happy with the lowest total cost.” The single cost is the weight of each path to complete the choice. who can help me add the weights?
Key Difficulties
- Usually the cost of choosing certain node remains unknown until you choose it, however, once the node has been chosen, usually it is not allowed to revise the node.
生活中的选择成本难以确定,多半要在选择后才能知道实际的成本。生活中的大部分选择,一旦选择后, 就没有办法回溯。 Due to the lack of samples to calculate or estimate the real cost, people would only achieve the local optimal route, instead of perceiving the global optimal one.
由于缺乏足够的观测样本,生活中的选择只能确保局部最优,并不保证全局最优,因为人们很多时候无法 察觉当时之后或情形之外(时间与空间上的全局)的情况。The pathes between nodes can be changed as time passes by.
生活中的顶点,路径都是动态化的,不是一成不变的。- Because of the impact bias, people usually focus more on the effect of loss than gain, also we could overestimate our happiness. Availability will impact your prediction about future happiness or unhappiness because it will be set as an anchor in your mind when you make the prediction. For example, if your favorite team’s super star is injured, so the availability of winning will decrease, then the anchor is as well as become more negative, which will be closer to the lowest degree of unhappiness and your prediction on how unhappy if they lose will be based on this anchor, which is not that overestimate because you have kind of received the worst result already. The impact bias will become more notable if the availability(the anchor) is much more deviated from the prediction result. In other words, if the anchor of the team is that they can nearly to win, however when you predict your unhappiness if they loss, you will overestimate how unhappy you would be because you think that you were quite sure that they could win, so this deviation will lead to the overestimation of your future feeling. But when the availability to win is lower, which means the anchor is closer to the situation you predict, you would predict less degree of unhappiness which will not be an overestimation.
Therefore, in the most occasions, the goals of humans are not absolutely objective, whereas, they are normally combined with the subjective factors that self-awareness、cognition and emotions of humans.
很多时候人对于“开心”的预测并不是绝对客观的而是容易产生偏见的。也就是说,对于同样的结果,不同的产生方式会导致人们表现出不一样的开心或难过的程度。例如,若选择做一件难以完成的事后取得成功,相比于做一件容易的事情,人会认为这更令人兴奋。又例如,人更倾向于被动得选择不做某事,而不是主动选择做某事,因为主动的选择往往会产生更多的后悔与懊恼的成分。因此,最终人们的追求并不是一种完全的客观存在,而更多是混杂着人们的自我认知、情绪甚至包括社会意识形态等主观成分,而这一部分内容是目前A.I.等科学领域尚未能触及得到的。这也是KM所试图去厘清的关键。
Design my algorithm
Because it is not revisable, maybe the best method is that we can just use a greedy algorithm to pursue a suboptimal path.
To be continued