Mathematica系列——FindShortestPath示例程序拆解
Mathematica系列——FindShortestPath示例程序拆解

Mathematica系列——FindShortestPath示例程序拆解

前言

有一天,我在探索Mathematica的帮助文档时,发现了这么一个东西:

这么简洁的代码,让我大吃一惊

哪个男生不想拥有一个迷宫生成器呢?

短短十几行代码就搞定了这个问题,MMA太强了吧,在这么想的同时,才发现远远看上去阳间的代码,仔细一看,不能再阴间了。

瞧瞧这Module, AnnotationValue, Sow-Reap对, 还有Do, While, With循环, 最可怕的还是/. /; /[Not]这些符号,代码短了,可代码可读性也太低了吧(那是你看不懂而已

所以必须要好好分析一下这段阴阳两隔的代码(后经证实,非常阳间且人性化

FindShortestPath——求指定顶点间的最短路径

FindShortestPath[g,s,t]
求图 g 中从源顶点 s 到目标顶点 t 的最短路径.

FindShortestPath[{v->w,...},...]
使用规则 v->w 指定图 g.

FindShortestPath 可用于无向图、有向图、加权图、多重图和混合图.

示例程序——通过对网格图的随机深度优先搜索创建一个迷宫

g = GridGraph[{20, 30}]

m = Graph[VertexList[g], 
   Module[{stack = {RandomChoice[VertexList[g]]}},
       Do[
        AnnotationValue[{g, v}, "Visited"] = False, {v, 
         VertexList[g]}];
       AnnotationValue[{g, First@stack}, "Visited"] = True;
       While[Not[stack == {}],
        With[{v = First@stack},
         With[{adj = 
            Cases[EdgeList[g, 
               v - _] /. {v - u_ :> u,
                u_ \[UndirectedEdge] v :> u}, 
             x_ /; \[Not] AnnotationValue[{g, x}, "Visited"]]},
          If[adj == {},
           stack = Rest@stack,
           With[{w = RandomChoice[adj]},
            PrependTo[stack, w];
            AnnotationValue[{g, w}, "Visited"] = True;
            Sow[v - w]]]]]]] // Reap // Last // 
    First, VertexCoordinates -> GraphEmbedding[g]];

HighlightGraph[m, 
 PathGraph@
  FindShortestPath[m, First@VertexList[m], Last@VertexList[m]]]
RandomChoice[VertexList[g]]

out: 591 得到图g的顶点{1,2,…,599,600}中的任意一个数

AnnotationValue[{obj,itemspec},key]

gives the annotation value associated with key for items specified by itemspec in obj.
Do[AnnotationValue[{g, v}, "Visited"] = False, {v, VertexList[g]}];

out: 将图g中的v(VertexList[g]={1,···,600})个顶点的Visited标记设为False;

AnnotationValue[{g, First@stack}, "Visited"] = True;

而栈顶的Visited标记设为True;

While[Not[stack == {}],
 With[{v = First@stack},
  With[{adj = 
     Cases[EdgeList[g, 
        v \[UndirectedEdge] _] /. {v \[UndirectedEdge] u_ :> u, 
        u_ \[UndirectedEdge] v :> u}, 
      x_ /; \[Not] AnnotationValue[{g, x}, "Visited"]]},
   If[adj == {},
    stack = Rest@stack,
    With[{w = RandomChoice[adj]},
     PrependTo[stack, w];
     AnnotationValue[{g, w}, "Visited"] = True;
     Sow[v \[UndirectedEdge] w]]]]]]

第一层——While循环

While[test,body]
重复计算 test,然后是 body,直到 test 第一次不能给出 True.

当栈非空时进行循环

第二层——With循环

With[{x=x0,y=y0,...},expr]
指定在 expr 中出现的符号 x、y、...应当由x0、y0、... 替换.

说人话就是将expr中的符号替换
With[{v = First@stack},...]

将v设置为栈顶元素并交给后面的表达式

EdgeList[g, v-_ ] /. {v-u :> u,u_ [- v :> u}

第三层——With循环

With[{adj = Cases[EdgeList[g,v-_]/.{v-u_:>u,u_-v:>u},x_/;!AnnotationValue[{g,x},"Visited"]]},
...]
EdgeList[g, v - _] 为图g中节点v与任意连接节点的集合
例: EdgeList[g, 55 - _] %_ for blank
out: {35 - 55, 54 - 55, 55 - 56, 55 - 75}
ReplaceAll (/.) 全部替换
expr/.rules
应用一个规则或规则列表尽可能转换一个表达式 expr 的每个子部分.

例:
用模式把变量和匹配的部分结合在一起:
1 + x^2 + x^4 /. x^p_ :> f[p]
out:1 + f[2] + f[4]
EdgeList[g,v-_]/.{v-u_:>u,u_-v:>u}

Condition (/;) 条件
patt/;test
是一个模式,仅当 test 为 True 时才匹配.
lhs:>rhs/;test
表示一个规则,仅当 test 为 True 时才应用.
lhs:=rhs/;test
是一个仅当 test 为 True 时使用的定义.

例:
对符合负值条件的所有元素进行替换:
{6, -7, 3, 2, -1, -2} /. x_ /; x < 0 -> w
out: {6, w, 3, 2, w, w}
x_ /; \[Not] AnnotationValue[{g, x}, "Visited"]

作为Cases的条件,含义是图g中节点x的标记为假

Cases  模式匹配
Cases[{e1,e2,...},pattern(->rhs)]
给出了匹配模式pattern的 e1 (的 rhs 值)的列表.

例:
从每一个匹配的 f[x_] 内部返回 x :
Cases[{1, 1, f[a], 2, 3, y, f[8], 9, f[10]}, f[x_] -> x]
out: {a, 8, 10}
{adj = Cases[EdgeList[g,v-_]/.{v-u_:>u,u_-v:>u},x_/;!AnnotationValue[{g,x},"Visited"]]}

adj为Cases返回的, 在图g中节点v(栈顶)的邻接节点中未被访问(Visited == False)的节点列表.

不妨称adj为未访问过的邻接表a.

第五层——if条件

If[adj == {},
stack = Rest@stack,
With[{w = RandomChoice[adj]},
PrependTo[stack, w];
AnnotationValue[{g, w}, "Visited"] = True;
Sow[v - w]]]

如果表a为空, 则说明该节点已经无路可走, 则从栈顶移去

stack等于去掉首位的stack

第六层——With循环

With[{w = RandomChoice[adj]},
  PrependTo[stack, w];
  AnnotationValue[{g, w}, "Visited"] = True;
  Sow[v - w]]

在表a中随机选择一个节点w放置到栈顶并将w的Visit标记设为True.

Sow  散布
Sow[e]
指定 e 可以从最近的封闭的 Reap 中提取.
Sow[e,{tag}]
指定 e 可以从最近的封闭的 Reap 中提取,其中它的模式匹配 {tag}.

Reap  收获
Reap[expr]
给出表达式 expr 的值,以及在计算中已经应用 Sow 的所有表达式. 使用 Sow[e] 或具有不同标记的 Sow[e,Subscript[tag, i]] "散布"的表达式在不同列表中给出.

在广义循环中, 使用Sow记录每一步e的值, 再由Reap收获
Sow[v - w]

散布了原栈顶结点与新栈顶节点(原栈顶节点的邻接节点)的无向图

跳离循环

收获之后, 很显然第一个元素是null {null,{..}}, 所以要选择Last{{…}}, 再选择第一个{…}, 将g的绘图坐标转交给m.

结果

HighlightGraph[m, 
 PathGraph@
  FindShortestPath[m, First@VertexList[m], Last@VertexList[m]]]

阳间

如果作为程序编写者而言,这样的代码是非常符合思考逻辑的,可以无缝的将思路转换为代码,可谓极致阳间了。

对于阅读者而言,只要了解了语法,怎么会看不懂呢?(XD

2条评论

发表回复

您的电子邮箱地址不会被公开。

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据