离散事件动态系统作业 #Petri网 #可达图 #赋时Petri

本文章由作者独立创作，为研究生某课程作业，仅供参考

首先吐槽一点：CSDN无法使用svg矢量图（人家写markdown都支持）

1. 图的类型

1.1 有向图是一个二元组

$$\begin{gathered} G=(V,E) \\ \{\begin{array}{l}V:结点或定点的集合\\ E:有向弧或者有向边的集合\end{array} \end{gathered}$$

E = { ( V 2 , V 1 ) , ( V 2 , V 3 ) , ( V 4 , V 1 ) , ( V 4 , V 3 ) } E=\{\:(V2,V1),(V2,V3),(V4,V1),(V4,V3)\:\} E={(V2,V1),(V2,V3),(V4,V1),(V4,V3)}

1.2 二分图是一个三元组

$$\begin{gathered} G=(\bar{V},\hat{V},E) \\ V=\bar{V}\cup \hat{V} \\ \forall (x,y)\in E,(x\in \bar{V}\cap y\in \hat{V})\cup (x\in \hat{V}\cap y\in \bar{V}) \end{gathered}$$

1.3 加权图是一个三元组

$$\begin{array}{rl}& G=(V,E,W)\\ & W:E\to R\end{array}$$

2. Petri网

​ $Petri$网是德国当代数学家$C.A.Petri$ 定义的一种通用的数学模型，用以描述存在于条件与事件间的关系。这一工作进行于1960~1962年间。此后各国学者，例如美国$MIT$（麻省理工学院）及欧洲的众多大学，对网作了大量的研究。1980年以来，“$Petri$网理论及应用欧洲研讨会”每年召开一次年会，交流新的研究成果。法国的科研人员为此做出了贡献。早在1972~1973年，已利用$Petri$网模型来描述逻辑控制器，它对$Grafcet$的建立产生了影响。

​ $Petri$网的模型是丰富的，既有严格的数学表达式，又有形象生动的图形化结构，能够描述离散事件动态系统中的顺序、选择、互斥、并发等事件关系，能对具有并行（$parallelism$）、并发（$concurrency$）、同步（$synchronization$）、资源分享（$resourcesharing$）等特性建立模型并使之形象化。$Petri$网在离散事件动态系统的建模、分析、仿真、形式化验证、故障诊断和调度控制等方面都有广泛的应用。

2.1 Petri网的表示

​ $Petri$网是一个四元组，有向二分加权图
$$\begin{gathered} N=(P,T,F,W) \\ \{\begin{array}{l}P:库所集合，圆圈\\ T:变迁集合，矩形(方框)\\ F:有向弧集合\\ W:F\to Z(权值)\end{array} \end{gathered}$$
​ 另外，

​ $C^{-}=P\times T$表示$|P|\times |T|$维的前置关联矩阵；

​ $C^{+}=T\times P$表示$|T|\times |P|$维的后置关联矩阵；

​ $m_0=[0,1,...]$表示初始标识的集合，每个库所中的标识皆称作$token$，$token$用圆点表示，该集合中$token$的总数量为非负整数；

​ $C$表示关联矩阵，其是由前后置关联矩阵计算得到的，$C=C^{-}-C^{+}$

2.2 使能变迁

​ 如果一个变迁的每个输入库所的$token$数不小于该库所到它弧上的权值，那么变迁是使能的。

即
$$m\ge C^{-}(:,t)$$

2.3 氢氧生水Petri网实例

​ 下面以一个氢氧生水的例子来简单描述$Petri$网

​ 前置关联矩阵$C^{-}$，表示每个变迁$(t_1,t_2)$输入的变化，$C^{-}=\left[\begin{array}{cc}2& 0\\ 1& 0\\ 0& 2\end{array}\right]$

​ 后置关联矩阵$C^{+}$，表示每个变迁$(t_1,t_2)$输出的变化，$C^{+}=\left[\begin{array}{cc}0& 2\\ 0& 1\\ 2& 0\end{array}\right]$

​ 关联矩阵$C=C^{+}-C^{-}=\left[\begin{array}{cc}-2& 2\\ -1& 1\\ 2& -2\end{array}\right]$

​ $m_0$为初始状态，即初始每个库所中的$tokrn$数，$m_0=\left[\begin{array}{c}3\\ 1\\ 2\end{array}\right]$

Petri网的激发有如下基本规则：

​ $rule1$：只有使能的变迁才可以激发；

​ $rule2$：变迁的激发耗时为0；

​ $rule3$：如果一个变迁激发，会从它的每个输入库所取走弧上权值个$token$，并给它的输出库所放入弧上权值个$token$；
$$m_{k+1}=m_k+C(:,t)=m_k+C\cdot {\overrightarrow{e}}_{k+1}$$
​ 在氢氧生水的例子中，激发第一次变迁，可以得到
$$\begin{array}{rl}{m}_1& =m_0+C\cdot {\overrightarrow{e}}_1\\ & =\left[\begin{array}{c}3\\ 1\\ 2\end{array}\right]+\left[\begin{array}{cc}-2& 2\\ -1& 1\\ 2& -2\end{array}\right]\cdot \left[\begin{array}{c}1\\ 0\end{array}\right]\\ & =\left[\begin{array}{c}3\\ 1\\ 2\end{array}\right]+\left[\begin{array}{c}-2\\ -1\\ 2\end{array}\right]=\left[\begin{array}{c}1\\ 0\\ 4\end{array}\right]\end{array}$$

2.4 典型的Petri网实例

2.4.1 典型Petri网结构图

2.4.2 典型Petri网matlab代码实现

%% petri_fun.m
function m=petri_fun(k)m0 = [3;1;2;1;2;2;1];m = m0;if k>0C_minus = [2 0 0 0 0 0 0 0 0 0;1 0 0 0 0 0 0 0 0 0;0 2 0 0 0 0 0 0 0 0;0 0 1 0 1 0 0 0 0 0;0 0 0 2 0 1 0 0 0 0;0 0 0 0 0 0 2 0 1 0;0 0 0 0 0 0 0 1 0 1];C_plus =  [0 0 1 0 0 0 0 0 1 0;0 0 0 1 0 0 0 0 0 1;2 0 0 0 0 0 0 0 0 0;0 1 0 0 0 0 1 0 0 0;0 1 0 0 0 0 0 1 0 0;0 0 0 0 1 0 0 0 0 0;0 0 0 0 0 2 0 0 0 0];C = C_plus - C_minus;E = eye(10);for i=1:ke = E(:,i);if all(m0 + C_minus*e >=0)m = m0 + C*e;m0 = m;elsefprintf("当前变迁无法激活，m = \n");endendelseif k==0fprintf("初始状态 m0 = \n");elsefprintf("未发生变迁，m = \n");end
end%% run.m
display(petri_fun(0));
for i=1:10fprintf("第%d次变迁，状态 m%d = \n",i,i);disp(petri_fun(i));
end

2.4.3 执行结果

3. Petri网可达图

3.1 Petri网可达图算法

​ 输入：后置关联矩阵$C^{+}$，前置关联矩阵$C^{-}$，初始标识$m_0$

​ 输出：可达图$G_r=(V,E,W)$，加权有向图

算法步骤：

​ $step1$：设$V_{new}$表示新结点的集合；

​ $step2$：画出可达图的根结点，并将其标为$m_0$，即 V = V ∪ { m 0 } V=V\cup\{m_0\} V=V∪{m0​}；

​ $step3$：将$m_0$标为新结点，即 V n e w = { m 0 } V_{new}=\{m_0\} Vnew​={m0​}；

​ $step4$：$if$ 已经没有待扩展的新结点$(V_{new}=\varnothing )$，则输出可达图$G$，并退出算法；

​ $else$，从$V_{new}$中任意选择一个新结点$m$，并将$m$从$V_{new}$中删除；

​ $step5$：令 T e = { ∀ t ∈ T ∣ m ≥ C − ( : , t ) } T_e=\{\ \forall t \in T \ |m\geq C^-(:,t)\ \} Te​={ ∀t∈T ∣m≥C−(:,t) } ；

​ $step6$：从$T_e$中任意选择一个变迁$t$，并将其从$T_e$中删除；

​ $step7$：$m^{{}^{\prime }}=m+C^{+}(:,t)-C^{-}(:,t)$ ；

​ $step8$：$if$ $m^{{}^{\prime }}$还没出现过$(m^{{}^{\prime }}\notin V)$，则 V = V ∪ { m ′ } V=V\cup \{m^{'}\} V=V∪{m′}，$E=E\cup \{(m,m^{{}^{\prime }})\}$，$W\{(m,m^{{}^{\prime }})\}=t$，并将$m^{{}^{\prime }}$放入$V_{new}$中；

​ $else$，$E=E\cup \{(m,m^{{}^{\prime }})\}$，$W\{(m,m^{{}^{\prime }})\}=t$；

​ $step9$：$if$ $T_e=\varnothing$，返回$step4$；

​ $else$ $T_e\ne \varnothing$，返回$step6$。

3.2 可达图matlab代码实现

注：以下两个文本文档为前置后置关联矩阵，自己创一个.txt即可
C_minus.txt
2 0 1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 1 1 0
0 2 1 0 1 0 0 0 0 0
0 0 0 2 0 1 0 0 1 0
0 2 0 0 0 0 2 1 0 1

C_plus.txt
0 0 1 0 0 0 2 0 1 0
2 0 0 0 2 0 0 0 1 0
0 1 0 0 0 0 0 1 0 0
0 0 0 2 1 0 2 0 1 0
0 0 0 1 0 2 0 0 0 1

%% step1~3: Initial
clear all;
clc;
C_minus = readmatrix("C_minus.txt");
C_plus =  readmatrix("C_plus.txt");
C = C_plus - C_minus
m0 = [4;2;3;1;3];
V = {};
V = [V,m0];
E = {};
W = {};
V_new = {m0};
Te = {};
symbol = 0;
origin = {};
destination = {};
weight = {};%% main circulate
while trueif symbol==0% step4: Exit or select random node[exit,m,V_new] = select_node(V_new,V,E,W,origin,destination,weight); if exit==1break;endTe = crate_Te(Te,m,C_minus);    % step5: Create Teif isempty(Te)else[t,Te]=select_t(Te);        % step6: Select random t from Techild=transition(C,m,t);    % step7: Transitionmask=judge(child,V);        % Judge whether 'child' has ever apperaed% step8: Add to Collection[V,E,W,V_new,origin,destination,weight]=collection(C,m,child,mask, ...t,V,E,W,V_new,origin,destination,weight); symbol = 0;endelse[t,Te]=select_t(Te);            % step6: Select random t from Techild=transition(C,m,t);        % step7: Transitionmask=judge(child,V);            % Judge whether 'child' has ever apperaed% step8: Add to Collection[V,E,W,V_new,origin,destination,weight]=collection(C,m,child,mask, ...t,V,E,W,V_new,origin,destination,weight); end% step9: Return and execute the next circulateif isempty(Te)symbol = 0;elsesymbol = 1;end
end%% step4: Exit or select random node
function [exit,m,V_new]=select_node(V_new,V,E,W,origin,destination,weight)if isempty(V_new)V = cell2mat(V);writematrix(V,'V.txt');fprintf('V=\n');disp(V);fprintf('E=\n');disp(E);W = cell2mat(W);writematrix(W,'W.txt');fprintf('W=\n');disp(W);m = [];exit = 1;G = digraph(origin,destination);figure(1)plot(G,"EdgeLabel",weight,"LineWidth",1.5,"MarkerSize",6, ..."ArrowSize",9,"NodeColor",'red','EdgeFontSize',9, ...'NodeFontSize',10)figure(2)plot(G,"EdgeLabel",weight,"LineWidth",1.5,"MarkerSize",6, ..."ArrowSize",9,"NodeColor",'red','EdgeFontSize',9, ...'NodeFontSize',10,'Layout','force3')elseindex = randi([1,length(V_new)]);m = V_new(index);V_new(index) =[];           % delete m from V_newexit = 0;end
end
%% step5: Create Te
function Te=crate_Te(Te,m,C_minus)sign = 0;I = eye(10);m = cell2mat(m);while truesign=sign+1;if sign>10 || length(find( m-C_minus(:,sign) <0))~=0break;elsetemp = {I(:,sign)};Te = [Te,temp];endend
end
%% step6: Select random t from Te
function [t,Te]=select_t(Te)if isempty(Te)returnelsesign = randi(length(Te));t = Te(sign);Te(sign) =[];               % delete t from Teend
end
%% step7: Transition
function child=transition(C,m,t)t = cell2mat(t);m = cell2mat(m);child = m + C*t;
end
%% Judge whether 'child' has ever apperaed
function mask=judge(child,V)child_cell = {child};mask = 0;for i=1:length(V)if ~isequal(child_cell,V(1,i))elsemask = i;               % appera,recordbreak;endend
end
%% step8: Add to Collection
function [V,E,W,V_new,origin,destination,weight]=collection(C,m,child,mask, ...t,V,E,W,V_new,origin,destination,weight)m = cell2mat(m);t = cell2mat(t);temp = sprintf('m%d',length(V));origin = [origin,temp];if mask==0arc = [m,child];V = [V,child];temp = sprintf('m%d',length(V));destination = [destination,temp];E = [E,arc];W = [W,C*t];temp = sprintf('t%d',length(W));weight = [weight,temp];V_new = [V_new,child];elsechild = V(1,mask);child = cell2mat(child);arc = [m,child];temp = sprintf('m%d',mask);destination = [destination,temp];E = [E,arc];W = [W,C*t];temp = sprintf('t%d',length(W));weight = [weight,temp];end
end

3.3 Petri网可达图执行结果

​ 输出可达图如下所示：

​ 输出三维力导向图如下：

​ 窗口输出V, E, W 如下所示：

4. 赋时Petri网

4.1 赋时Petri网模型

​ 所谓赋时Petri网就是在普通Petri网的基础上加入了时间因素，需要引入 $d_k,x_k,{\lambda }_k$ 这几个时间变量
$$\{\begin{array}{l}G=(N,d,m_0)\\ X_k=m_k,v_k,g_k\end{array}$$

其中，
$$\{\begin{array}{l}N是一个Ptri网结构\\ d是时延\\ m_0是初始标识\\ m_k是经过k次变迁激发到达的标识\\ v_k是token在库所中已经等待的时间\\ g_k是Petri网到达x_k时已经等待的时间\end{array}$$
激发条件：
$$\{\begin{array}{l}{m}_k-C^{-}(:,e_k)>0\\ v_k(p)\ge d(p)\end{array}$$
定义：

​ ${\lambda }_k$表示第$k$次和第$k+1$次变迁之间的时间间隔

定理：

​ 对于$G=(N,d,m_0)$，对处于第$k$个激发时刻的状态$X_k$，${\lambda }_{k+1}$表示第$k+1$个变迁还需等待的时间，那么：
$$\{\begin{array}{l}{m}_k\ge C^{-}(:,e_{k+1})\\ \lambda =max(d(p)-v_k(p))\\ m_{k+1}=m_k+C(:,e_{k+1})\\ v_{k+1}=v_k-diag(v_k)\cdot C^{-}(:,e_{k+1})+{\lambda }_{k+1}\cdot (m_{k+1}-C^{+}(:,e_{k+1}))\\ g_{k+1}=g_k+{\lambda }_{k+1}\end{array}$$

4.2 赋时Petri网可达图算法

​ 输入：$C^{-},C,d,m_0,m_g$

​ **输出：**赋时$Petri$网可达图

​ 步骤如下：

​ （1）初始化$X_0=(m_0,v_0,g_0)$，其中$m_0$作为初始标识，$v_0=0$，${\lambda }_0=0$，$g_0=0$；

​ （2）将初始状态$X_0=(m_0,v_0,g_0)$作为可达树的根结点，并标记为$new$；

​ （3）如果$m_0=m_g$，将$X_0$标记为$gaol$，算法退出，否则继续执行下一步；

​ （4）从可达树中任意选择一个$new$结点，表示为$X_k=(m_k,v_k,g_k)$，并将该结点标记为$old$

​ （5）计算$X_k$状态下使能的变迁集合 E k = { t ∈ T ∣ m k ≥ C − ( : , t ) } E_k=\{t\in T \ |\ m_k \geq C^-(:,t) \} Ek​={t∈T ∣ mk​≥C−(:,t)}；

​ （6）$forall{e}_k\in E_k,do$

​ （7） 激发$e_k$，产生新状态$X_{k+1}$，根据公式分别计算${\lambda }_{k+1},m_{k+1},v_{k+1}和g_{k+1}$；

​ （8） 如果$X_{k+1}$是新状态，在可达树中添加一个表示$X_{k+1}$的结点；

​ （9） 画一条从$X_k$指向$X_{k+1}$的弧，弧上标记激发变迁$e_k$；

​ （10） 如果$m_{k+1}=m_g$，将$X_{k+1}$对应的结点记为$goal$，否则记为$new$；

​ （11）$end$

​ （12）如果可达树中存在$new$结点，那么返回第4步。

4.3 赋时Petri网实例

4.3.1 设计赋时Petri网结构

​ 改进了课堂上的赋时$Petri$网例子，如下图所示

​ 为使$P2$不会一直积累，$constraint$:
$$P_2\le 1$$
​ $introduceC,sohave$
$$\begin{gathered} P_2+C=1 \\ which0\ast P_0+0\ast P_1+1\ast P_2+0\ast P_3+0\ast P_4+0\ast P_5+0\ast P_6+C=b \\ w=\left[\begin{array}{ccccccc}0& 0& 1& 0& 0& 0& 0\end{array}\right](w是P_0\sim P_6的系数) \\ \bar{w}=w\ast C=\left[\begin{array}{ccccccc}0& 0& 1& 0& 0& 0& 0\end{array}\right]\ast \left[\begin{array}{ccc}-1& 1& 0\\ -1& 1& 0\\ -1& 0& 1\\ 0& 0& 0\\ 1& -1& 0\\ 1& -1& 0\\ 0& 1& 0\end{array}\right]=\left[\begin{array}{ccc}-1& 0& 1\end{array}\right] \\ {m}_0(c)=b-w\ast m_0=1-\left[\begin{array}{ccccccc}0& 0& 1& 0& 0& 0& 0\end{array}\right]\ast \left[\begin{array}{c}0\\ 0\\ 0\\ 1\\ 1\\ 1\\ 0\end{array}\right]=1-0=1 \end{gathered}$$

​ 因此，$C$的库所初始值为1，在变迁中，$C$从$T_0$获得1个$token$，从$T_1$获得0个$token$，并给$T_2$赋予1个$token$

4.3.2 赋时Petri网可达树matlab代码实现

注：以下两个文本文档为前置后置关联矩阵，自己创一个.txt即可
C_minus.txt
1 0 0
1 0 0
1 0 0
0 0 1
0 1 0
0 1 0
0 0 0
0 0 1

C_plus.txt
0 1 0
0 1 0
0 0 1
0 0 1
1 0 0
1 0 0
0 1 0
1 0 0

%% Time_given_Petri.m
clear;clc;
C_minus = readmatrix("C_minus.txt");
C_plus =  readmatrix("C_plus.txt");
C = C_plus - C_minus;
d = [10 8 0 12 10 8 0 0]';
mg = [1 1 0 1 0 0 6 1]';
%% Step1~2: Initial
X0 = state_X;
Ek = {};
V = [X0];
V_new = [X0];
origin = {};
destination = {};
weight = {};
%% Step3: Judge whether X0 is goal
if isequal(X0.m,mg)X0.goal = true;             % mark X0 as goal, algorithm exitorigin = [origin,'X0 is goal'];destination = [destination,'X0 is goal'];
elsewhile ~isempty(V_new)%% Step4: Random select a node from V_new as Xkindex = randi([1,length(V_new)]);Xk = V_new(index);V_new(index) = [];      % delete Xk from V_new% V = [V,Xk];           % set Xk -> oldfor j = 1:length(V)if isequal(V(j).m,Xk.m)    % if Xk_plus has ever appearfather_index = j; break;endend%% Step5: Calculate Transfer_Collection[Xk,Ek] = Transfer_Collection(Xk,C_minus);%% Step6for i = 1:length(Ek)%% Step7: Calculate lamda, m, v, g of Xk_plusek = Ek(i);Xk_plus = state_X;Xk_plus.m = Xk.m + C(:,ek);Xk_plus.lamda = max(d(C_minus(:,ek)~=0)-Xk.v(C_minus(:,ek)~=0));Xk_plus.v = Xk.v-diag(Xk.v)*C_minus(:,ek)+Xk_plus.lamda*(Xk_plus.m-C_plus(:,ek));Xk_plus.g = Xk.g + Xk_plus.lamda;%% Step8: append Xk_plussign = 1;                   % default Xk_plus is newfor j = 1:length(V)if isequal(V(j).m,Xk_plus.m) % if Xk_plus has ever appearsign = 0; break;endendif sign==1                  % if Xk_plus is new, append to V%% Step9: Digraphtemp = sprintf('X%d',father_index-1);origin = [origin,temp];V = [V,Xk_plus];temp = sprintf('X%d',length(V)-1);destination = [destination,temp];temp = sprintf('t%d',ek-1);weight = [weight,temp];end%% Step10: If Vk_plus.m==mg, mark -> goal, else -> newif isequal(Xk_plus.m,mg)Xk_plus.goal = true;temp = sprintf('X%d is goal',length(V)-1);destination(end) = {temp};break;elseV_new = [V_new,Xk_plus];endendend
end
G = digraph(origin,destination);
figure(1)
plot(G,"EdgeLabel",weight,"LineWidth",1.6,"MarkerSize",6,"ArrowSize", ...11,"NodeColor",'red','EdgeFontSize',9,'NodeFontSize',10, ...'ArrowPosition',0.9,'EdgeLabelColor','blue');
figure(2)
plot(G,"EdgeLabel",weight,"LineWidth",1.6,"MarkerSize",6,"ArrowSize", ...11,"NodeColor",'red','EdgeFontSize',9,'NodeFontSize',10, ...'Layout','force3','ArrowPosition',0.9,'EdgeLabelColor','blue');%% state_X.m
classdef state_Xpropertiesm = [0 0 0 1 1 1 0 1]';         % initial m0, v0, g, lamdav = [0 0 0 0 0 0 0 0]';g = 0;lamda = 0;goal = false;endmethodsfunction [object,Ek] = Transfer_Collection(object,C_minus)Ek = [];for t=1:length(C_minus(1,:))if all(object.m>=C_minus(:,t))Ek = [Ek,t];endendendend
end

4.3.3 赋时Petri网可达树执行结果

​ notes：由于程序中设定随机选择$V_{new}$中的结点扩展，因此程序每次运行的结果不一定相同。

​ 输出可达树如下所示：

​ 输出三维力导向图如下：

5. 有色Petri网

5.1 颜色集

​ C = { g , w , b , . . . } C=\{g,w,b,...\} C={g,w,b,...}

​ $token$上的颜色集：$C_{token}⟹C_{tkn}$

​ 变迁上的颜色集：$C_{transition}⟹C_{trs}$

​ ${\hat{C}}_{tkn}$：由$C_{tkn}$中元素组成的多重集的集合；

​ $m:P\to {\hat{C}}_{tkn}$

5.2 有色Petri网（普通Petri网的折叠）

​ 有色Petri网就是在Petri网的基础上引入颜色的概念，对同类的个体赋予相同的颜色，不同类的个体以不同的颜色加以区分。另外token也增加了颜色，可以描述对象的属性信息，在弧上和变迁上存在着条件表达式和函数，说明弧的权值和颜色属性以及变迁触发的约束条件。

​ 有色Petri网用七元组来表示，即$CPN={{P,T,E,C_{tkn},C_{trs},m_0,W_{arc}} } $

​ （1）$P$ : 库所的有限集合, P = { p 1 , p 2 , . . . , p m } P={\{p_1,p_2,...,p_m}\} P={p1​,p2​,...,pm​};

​ （2）$T$ : 变迁的有限集合, T = { t 1 , t 2 , . . . , t n } T={\{t_1,t_2,...,t_n}\} T={t1​,t2​,...,tn​};

​ （3）$W_{arc}$ : 弧的有限集合，满足$P\cap T=P\cap W_{arc}=T\cap W_{arc}=\varnothing $;

​ （4）$C_{tkn}$ : 每个库所对应的颜色集合

​ （5）$C_{trs}$ : 每个变迁对应的颜色集合

​ （6）$m_0$ : $P\to {\hat{C}}_{tkn}$ (由$C_{tkn}$ 中的每个元素组成的多重集合)

5.3 激发规则与更新规则

​ $\forall C\in C_{trs},t\in T$ ，$m_k\ge C_c^{-}(:,t)$ ，则该颜色对应的变迁可激发

​ $m_{k+1}=m_k+C_c(:,t)$

5.4 可覆盖树算法

​ 输入：前置关联矩阵C${}^{-}$，后置关联矩阵C${}^{+}$，初始标识$m_0$

​ （1）绘制根结点记为$m_0$，并将之标记为新结点$new$；

​ （2）判断可覆盖树中是否含有$new$结点：如果没有，将可覆盖树输出，判断终止，算法结束；反之，执行3；

​ （3）在$new$结点中任意选择一个$m$;

​ （4）$forallt\in T$

​ （5） $if$ $ \ m\geq$$C^{-}(:,t)$, $then$

​ （6） 进行m的更新$m_{k+1}=m_k+C(:,t)=m_k+C\cdot \overrightarrow{e}$

​ （7） 如果树中存在一个标识$m^{‘}$

​ KaTeX parse error: Undefined control sequence: \and at position 16: m^`\geq m^{``} \̲a̲n̲d̲(\ \exists \ p\…

​ （8） $\forall p\in P,m^{‘}(p)>m^{‘‘}(p),m^{‘}(p)=\omega$

​ （9） 遍历树，判断$m^{‘}$是否为旧结点，标记为$old$，反之，标记为新结点$new$

​ （10） $endif$

​ （11）$endfor$

​ （12）返回第2步

致歉

由于课业繁多，且离散系统优化调度不是本人研究方向，因此止步于皮毛，仅供参考。