The best path to get the maximum sum

[shaowu459]

(for language reasons, the content below is the result of automatic machine translation)

Hi All

Recently, I encountered a problem with finding the optimal path and have been unsuccessful despite numerous attempts. I am looking for a solution using spreadsheet function and formulas. Theoretically, using recursion combined with path recording should work, but for a 10*10 matrix, the computational load is too large to be practical. The specific details of the problem are as follows:

1）There is a 10x10 matrix, and all elements in the matrix are positive integers.
2）A person starts at the top-left corner of the matrix and must reach the bottom-right corner. Each move can be to an adjacent cell directly above, below, to the left, or to the right. However, the move is only allowed if the target cell has a number greater than or equal to that of the current cell.
3）It is not allowed to step outside the matrix or revisit any cell that has been previously walked on.
4）Please plan a route from the top-left to the bottom-right corner that maximizes the sum of the numbers on all cells along the path.
5）On the left are some example results, with the cells marked in brown indicating the optimal path.

Any help would be greatly appreciated.

Office version: 365+Beta channel with TRIMRANGE

Help.xlsx
	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X
1													Max
2		2	2	4	5	6	8	9	11	13	15		431		1）There is a 10x10 matrix, and all elements in the matrix are positive integers.
3		3	4	4	5	8	9	9	12	13	15
4		4	4	6	6	7	10	11	13	14	17				2）A person starts at the top-left corner of the matrix and must reach the bottom-right corner. Each move can be to an adjacent cell directly above, below, to the left, or to the right. However, the move is only allowed if the target cell has a number greater than or equal to that of the current cell.
5		5	6	7	8	9	11	13	13	16	16
6		6	7	8	9	11	11	14	15	16	18
7		7	7	9	10	11	13	15	16	18	19
8		8	10	11	13	13	15	16	19	19	22
9		10	11	12	14	14	17	18	20	20	23				3）It is not allowed to step outside the matrix or revisit any cell that has been previously walked on.
10		12	13	14	16	16	18	19	20	24	24
11		13	14	16	17	18	19	22	24	25	27
12															4）Please plan a route from the top-left to the bottom-right corner that maximizes the sum of the numbers on all cells along the path.
13													Max
14		1	2	3	4	6	7	8	10	12	13		380
15		1	3	5	5	6	8	9	12	12	15				5）On the left are some example results, with the cells marked in brown indicating the optimal path.
16		4	3	5	6	7	9	11	12	15	16
17		5	6	6	7	8	10	12	14	16	18
18		6	7	8	8	10	12	13	15	17	19
19		7	9	8	11	12	13	14	16	17	19
20		9	9	10	12	12	15	17	17	19	21
21		10	10	12	13	15	17	17	19	21	22
22		12	12	13	15	17	18	19	22	22	25
23		13	15	15	18	18	20	21	24	24	26
24
25													Max
26		2	2	3	4	6	8	9	11	13	14		451
27		1	4	4	6	8	8	9	11	14	15
28		3	3	5	5	9	9	10	12	14	15
29		5	5	7	8	9	10	12	13	15	17
30		7	7	8	9	11	12	14	16	17	19
31		8	8	9	10	13	14	14	16	17	19
32		9	9	11	13	14	14	16	18	19	22
33		10	12	13	13	16	15	17	20	22	22
34		13	13	15	16	16	18	20	22	22	24
35		13	14	16	17	17	21	21	22	24	26
36
Sheet1

 

[Rijnsent]

Interested to see if anyone can come up with formulas for this, it sounds horribly complex. My first thoughts:
- start with a smaller grid (e.g. 4x4)
- start only going right & down (so leave up&left out)
Even with these two simple rules I can use VBA to solve it, but formulas are much, much harder to use.

 

[shaowu459]

Interested to see if anyone can come up with formulas for this, it sounds horribly complex. My first thoughts:
- start with a smaller grid (e.g. 4x4)
- start only going right & down (so leave up&left out)
Even with these two simple rules I can use VBA to solve it, but formulas are much, much harder to use.

Thank you for taking the time to look at my post. If only moving right and down were allowed, dynamic programming would be very convenient for solving this problem（using formulas）. Now, since it's possible to move in four directions, it does not meet the requirement of "without aftereffect" in dynamic programming, making it more complex.