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

1 次查看（过去 30 天）
Jurij Lorenzo Mazzola
回答： Abhinaya Kennedy 2024-5-16
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.

请先登录，再回答此问题。

回答（1 个）

Abhinaya Kennedy
Abhinaya Kennedy 2024-5-16
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);

类别

在 Help Center 和 File Exchange 中查找有关 Labyrinth problems 的更多信息

标签

产品


版本

R2021a

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by