Improving recursive maze-solver-like function for TTBD simulation.

Introduction: We are simulating TTBD (Time to Breakdown) of metal-insulator-metal structure. We divided the whole structure of insulator (2D) in subdomains (cell). The mathematical model is a matrix (of size height x width) of 1 and 0s. It may happen, with high electric field, that a cell breaks and becomes conductive (failed cell). In the matrix (of all zeros at the very start) every element represents a cell (0 if still insulating, 1 if failed). We need a function to find if there exists a path of 1s (adiacent failed cells -not diagonal-) that links the first row to the bottom of the matrix. So this function has to give a result that tells me if there is a Breakdown or not. Example of matrices:

matrix(height,width)=[0 0 1; 0 1 1; 0 1 0] -> Breakdown (***possible loop which is explained later)

matrix(height,width)=[0 0 1; 0 0 1; 0 1 0] -> No Breakdown

matrix(height,width)=[0 0 1; 0 1 1; 0 0 0] -> No Breakdown

Function: The function receives as inputs: (x,y) coordinates, size of the matrix, the actual matrix and a flag matrix (its utility will be clear later).

How it works: The function is called ONLY if a 1 is detected in first row. The code (commented for the sake of clarity) is the following:

function Check = CheckFailedCellNearby(x,y,width,height,M,Mf)           %Mf-matrix of flags take trace of the
                                                                        %path that we are following                                     
    if (y > 0 && y <= width && x <= height && Mf(x,y) == 0)             %if we are in the structure and the cell
        Mf(x,y) = 1;                                                    %has not been checked yet...
        if (M(x,y) == 0)                                                %if not failed
            Check = 0;
        elseif (M(x,y) == 1 && x == height)                             %if we are on the bottom
            Check = 1;
            global BD;                                              %raise global variable
            BD = 1;
        elseif(CheckFailedCellNearby(x,y+1,width,height,M,Mf))
            Check = 1;
        elseif(CheckFailedCellNearby(x,y-1,width,height,M,Mf))
            Check = 1;
        elseif(CheckFailedCellNearby(x+1,y,width,height,M,Mf))
            Check = 1;
        else
            Check = 0;
        end
    else
        Check = 0;
    end
end

The matrix of flags is my personal (and probably not optimized) solution to avoid loops, which happen if there are adiacent 1s on the same row since the function search righthandside and lefthandside before checking the cell below. So what happens is that the two 1 continue to find an adiacent 1 looping for eternity. As you can see, the function is very simple and it works (tested on 18x18 size matrix). I just want to optimize it and make it faster (take into account that it will be called at every cycle after a 1 appears in first row).

Things that can be improved:

1. The way the function communicate if there is a Breakdown. I went for a global variable change, which I really do not like, having the feeling that it is not a good thing to do.
2. The mechanism to avoid loop.

Extra: Code before the function:

[width, height] = size(M);
Mf = zeros(width, heigth);
global BD;
BD = 0;
%Line of code that has to call the function if a 1 (in position (x_start,y_start) appears in first row
CheckFailedCellNearby(x_start,y_start,height,width,M,Mf);

Every suggestion is well accepted, even if it may change the whole structure of the function. To conclude I would like to underlying the the function works, I just want to make some improvements. Hope to have been clear enough. Thank you very much.

[Matteo Greatti]

Up

Answer 1

[Abhinaya Kennedy]

Hi Jurij,

To optimize the 'CheckFailedCellNearby' function for faster execution and cleaner code:

1. Avoiding Global Variables:

• Replace the global variable 'BD' with a function return value.
• Set 'Check' to 1 only if a path to the bottom is found, otherwise return 0.

2. Optimizing Loop Prevention:

• Instead of the flag matrix 'Mf', use a set to keep track of visited cells.
• Add the current cell coordinates (x, y) to the set before making recursive calls.
• Check if the cell is already in the set before exploring its neighbors.

3. Early Termination:

• If a path to the bottom '(x == height)' is found during recursion, immediately return 1.

function Check = CheckFailedCellNearby(x, y, width, height, M, visited)

    % Check for valid cell and not visited
    if (y > 0 && y <= width && x <= height && ~ismember([x, y], visited))
        visited = [visited; [x, y]]; % Add current cell to visited set

        % Base cases
        if (M(x, y) == 0)
            Check = 0;
        elseif (x == height)  % Reached bottom
            Check = 1;
            return;
        end

        % Recursive exploration (check neighbors and avoid revisiting)
        Check = CheckFailedCellNearby(x+1, y, width, height, M, visited) || ...
               CheckFailedCellNearby(x, y+1, width, height, M, visited) || ...
               CheckFailedCellNearby(x, y-1, width, height, M, visited);
    else
        Check = 0;
    end
end

Initialize the visited set as an empty set before calling the function.

visited = [];
Check = CheckFailedCellNearby(x_start, y_start, height, width, M, visited);