/sci/ - Science & Math » Thread #11485699

19KiB, 791x299, 35b1858a59b67e87ea6667193458249b.png

View Same Google iqdb SauceNAO

Non poo algorithm

Anonymous Fri 20 Mar 09:05:34 2020 No.11485699 View Reply Original Report

Quoted By: >>11486067 >>11486070

Is there any established algorithm you know of which does pic related?
I'm working on a project and I want to implement this in the least poo way.
>inb4 excel
Excel is just for ease of demonstration.

Anonymous

Anonymous Fri 20 Mar 2020 12:28:24 No.11486031 Report

Quoted By: >>11486126

Breadth-first. Poo but not much

Anonymous

Anonymous Fri 20 Mar 2020 12:38:07 No.11486067 Report

Quoted By: >>11486100 >>11486126

>>11485699
Depth first search. Neighbors are the 4 cells around it, limit the depth to k. Keep track of the maximum sum seen so far.

Anonymous

Anonymous Fri 20 Mar 2020 12:40:47 No.11486070 Report

Quoted By: >>11486100 >>11486126

>>11485699
Seems like a poo problem to begin with. You have to access each cell of the matrix more than once just to check the new largest possible neighbor.

Anonymous

Anonymous Fri 20 Mar 2020 12:50:27 No.11486100 Report

Quoted By: >>11486122 >>11486126

>>11486067
>t. brainlet
>>11486070
that's why this needs to be done using recursion

Anonymous

Anonymous Fri 20 Mar 2020 12:58:10 No.11486122 Report

Quoted By:

>>11486100
wrong

Anonymous

Anonymous Fri 20 Mar 2020 13:02:27 No.11486126 Report

Quoted By: >>11486128

>>11486100
>>11486070
>>11486067
>>11486031
what's the time complexity for implementing Breadth search here? I have thought of it, but for a 10K X 10K matrix its going to fry my shit i think

Anonymous

Anonymous Fri 20 Mar 2020 13:04:03 No.11486128 Report

Quoted By:

>>11486126
especially if I have say 1K steps or some shit lol
it seems like some factor of mnk

Anonymous

Anonymous Fri 20 Mar 2020 13:34:41 No.11486163 Report

Quoted By: >>11486193 >>11486270

Is it asking to create a single patch from the origin based on which neighboring cell is the largest?

Or is it asking to test all possible paths and start locations to see which path has the greatest sum of cells based on only visiting a neighboring cell with the largest value?

Anonymous

Anonymous Fri 20 Mar 2020 13:57:14 No.11486193 Report

Quoted By:

>>11486163
>a single patch
path*

Anonymous

Anonymous Fri 20 Mar 2020 14:05:37 No.11486214 Report

Quoted By:

It's a graph traversal problem

Anonymous

Anonymous Fri 20 Mar 2020 14:43:38 No.11486270 Report

Quoted By: >>11486277 >>11486304

>>11486163
the input would be the matrix ( depending on the language you use, also could be a 1D array of length m x n and 2 scalar values m and n to indicate number of rows and columns in the matrix).
And the output im looking for is the i,j pairs that indicate the path coordinates, in the examples the output is the i,j values of each blue cell .

Anonymous

Anonymous Fri 20 Mar 2020 14:51:19 No.11486277 Report

Quoted By:

>>11486270
go for it.

Anonymous

Anonymous Fri 20 Mar 2020 15:10:31 No.11486304 Report

Quoted By:

>>11486270
It should only take half an hour to write the code. you'll want a boolean 2Darray the same size as your matrix to keep track if a cell has been visited for an iteration. I'll refer to it as p[m][n], initialized as false in each cell.

class path{
startx;
starty;
k;
sum;
}
would help for keeping track of the things you want.
[2][2] array for checking the 4 neighbors
for (a=0; a<2; a++){
?for (b=0; b<2; b++){
??arrchk[a] = -1;
?}
}
if (xx != 0){
?arrchk[0][0] = arr[xx-1][yy]
} if (xx!= m){
?arrchk[1][0] = arr[xx+1][yy]
} if (yy!= 0){
?arrchk[0][1] = arr[xx][yy-1]
} if (yy!= n){
?arrchk[1][1] = arr[xx][yy+1]
}
for (a=0; a<2; a++){
?for (b=0; b<2; b++){
??if (!p[a]){
???if (arrchk[a] > largest){
????largest = arrchk[a]
????largestx = a;
????largesty = b;
???}
??}
?}
}
p[largestx][largesty] = true;
sum += arrchk[largestx][largesty]
}}

idk what you want from /sci/ regarding this.

Capcode	All Only User Posts Only Moderator Posts Only Admin Posts Only Developer Posts
Show Posts	All Only With Images Only Without Images
Deleted Posts	All Only Deleted Posts Only Non-Deleted Posts
Ghost Posts	All Only Ghost Posts Only Non-Ghost Posts
Post Type	All Only Sticky Threads Only Opening Posts Only Reply Posts
Results	All Grouped By Threads
Order	Latest Posts First Oldest Posts First

Your latest searches