# A Fault Section Location Method for Distribution Networks Based on Divide-and-Conquer
## 4 Fault Section Location Method for Distribution Networks Based on Divide-and-Conquer
### Algorithm Design
According to Theorem 8, the algorithm returns the section with the largest approximation gain as the location result at this time. Among them, the subroutine FIND-MAX returns the position and value of the largest element in the array. Lines 10-32 correspond to the recursive case of \(\mathbf{G}_{i}\) containing T-type sections. Lines 10-17 are the \"Divide\" steps that determine the diagnostic range of the subnetwork \(\mathbf{G}_{u}\) and \(\mathbf{G}_{v}\). Lines 10-11 identify the starting section \(x_{ui}\) and \(x_{vi}\) of \(\mathbf{G}_{u}\) and \(\mathbf{G}_{v}\) from the adjacency list of section \(x_{k}\). Because the section numbers are consecutive, lines 12-18 find the sections \(x_{uj}\) and \(x_{pj}\) with the largest number in \(\mathbf{G}_{u}\) and \(\mathbf{G}_{v}\) by comparing the sizes of \(ui\) and \(vi\). Lines 19-20 are the \"Conquer\" steps, which recursively invoke the algorithm to find the fault candidate sets \(\mathbf{X}_{u}\),\(\mathbf{X}_{v}\) of \(\mathbf{G}_{u}\),\(\mathbf{G}_{v}\) and their approximation gains \(\Delta_{\mathbf{X}_{u}}\),\(\Delta_{\mathbf{X}_{v}}\). Lines 21-32 are the \"Combine\" steps. Line 21 finds the section with the largest approximation gain in the set of sections \(\mathbf{E}_{i-t}\) to form \(\mathbf{X}_{i-t}\) and its approximation gains \(\Delta_{\mathbf{X}_{i-t}}\). Lines 22-23 construct \(\mathbf{X}_{u\mathbf{k}v}\) and calculate \(\Delta_{\mathbf{X}_{u\mathbf{k}v}}\). Lines 24-32 find largest one from \(\Delta_{\mathbf{X}_{i-t}}\), \(\Delta_{\mathbf{X}_{u}}\), \(\Delta_{\mathbf{X}_{v}}\), \(\Delta_{\mathbf{X}_{u\mathbf{k}v}}\), and return its corresponding \(\mathbf{X}\) and \(\Delta\) as the result of the fault location for \(\mathbf{G}_{i}\). In summary, the flow chart of the algorithm in this paper is shown in Figure 5.  
```
1:\(k=i\)
2:\(\Delta_{k}=D+2I(k)-1\)
3:while\(\mathbf{T}(k)\
eq 0\) and \(\Delta_{k}=D+2I(k)-1\)do
4:\(k=k+1\)
5:\(\Delta_{k}=D+2I(k)-1\)
6:endwhile
7:if\(k=j\)then// base case
8:return(FIND-MAX (\(\Delta[i:j]\)))
9:endif
10:\(ui=Adj(k)(1)\)// divide
11:\(vi=Adj(k)(1)\)
12:if\(ui>vi\)then
13:\(uj=j\)
14:\(vj=ui-1\)
15:else
16:\(vj=j\)
17:\(uj=vi-1\)
18:endif
19:\((\mathbf{X}_{u},\Delta_{\mathbf{X}_{v}})=\mathrm{DACFL}(ui,uj,\mathrm{ Graph},\boldsymbol{I},\Delta_{k})\)// conquer
20:\((\mathbf{X}_{v},\Delta_{\mathbf{X}_{v}})=\mathrm{DACFL}(vi,vj,\mathrm{ Graph},\boldsymbol{I},\Delta_{k})\)
21:\((\mathbf{X}_{i-t},\Delta_{\mathbf{X}_{i-t}})=\mathrm{FIND}-\mathrm{MAX}( \Delta[i:k])\)// combine
22:\(\Delta_{\mathbf{x}_{\mathrm{idx}}}=\Delta_{\mathbf{x}_{u}}+\Delta_{\mathbf{X} _{v}}\)
23:\(\Delta_{\mathbf{x}_{uu}}=\Delta_{\mathbf{X}_{u}}+\Delta_{\mathbf{X}_{v}}- \Delta_{k}\)
24:if\(\Delta_{\mathbf{x}_{u}}=\max(\Delta_{\mathbf{x}_{u}},\Delta_{\mathbf{x}_{v}}, \Delta_{\mathbf{X}_{uu}})\)then
25:return\((\mathbf{X}_{u},\Delta_{\mathbf{X}_{v}})\)
26:elseif\(\Delta_{\mathbf{X}_{v}}=\max(\Delta_{\mathbf{X}_{u-t}},\Delta_{\mathbf{X}_{v}}, \Delta_{\mathbf{X}_{v}},\Delta_{\mathbf{X}_{uu}})\)then
27:return\((\mathbf{X}_{v},\Delta_{\mathbf{X}_{v}})\)
28:elseif\(\Delta_{\mathbf{X}_{i-t}}=\max(\Delta_{\mathbf{X}_{i-t}},\Delta_{\mathbf{X}_{v}}, \Delta_{\mathbf{X}_{v}},\Delta_{\mathbf{X}_{v}})\)then
29:return\((\mathbf{X}_{i-t},\Delta_{\mathbf{X}_{i-t}})\)
30:else
31:return\((\mathbf{X}_{u\delta v},\Delta_{\mathbf{X}_{uu}})\)
32:endif
```  
**Algorithm 1** DACFL (\(i,j,\) Graph, \(\boldsymbol{I},D\))  
It should be noted that Formulas (32) and (33) calculating the approximation gains \(\Delta_{k}\) and \(\Delta_{\mathbf{X}_{\mathrm{ade}}}\) have a linear time operation cost. To improve computational efficiency, lines 2, 5, and 23 of the algorithm use constant time operations to calculate \(\Delta_{k}\) and \(\Delta_{\mathbf{X}_{\mathrm{ade}}}\). The correctness of this calculation method is demonstrated in Appendices E and F.