7 replies to this topic

[msshapira]

Hi,
This function is a solution for recursivly finding the lowest cost path between two points in a 2D matrix. the cost of each step is its ".value". it's passed with the cordinates for the start and end points.
However, somethings not working here and I get the wrong results.
i think this is similar to the A* pathfinder but the only examples i have seen are not recurisive...

LARGE is the limit of "long int"
all nodes ".bestFromStart" all initilized as LARGE

long int GetMin(Node** matrix,int currentR,int currentC,int endR,int endC,

				int rows,int columns,Node* father)

{

	long int result;


	//if out of bounds return max of field

	if (currentR==rows || currentC==columns || currentR<0 || currentC<0)

		return LARGE;


	//if reached end

	if (currentC==endC && currentR==endR)

		return (matrix[currentR][currentC].value);


	//if already checked here

	if (matrix[currentR][currentC].status==OPEN)

		return LARGE;


/*record distance from beggining*/

	//if first node

	if (father==NULL)

		//assign first value as best value

		matrix[currentR][currentC].bestFromStart=

			matrix[currentR][currentC].value;

	//if not first node

	else

	{

		//if bestFromStart old value higher than current value 

		if ( (matrix[currentR][currentC].value +

			father->bestFromStart ) <

			matrix[currentR][currentC].bestFromStart )

			//then...

			matrix[currentR][currentC].bestFromStart=

				matrix[currentR][currentC].value+				

				father->bestFromStart;

		else

			/*this is a bad path - 

			this way is not shorter than previously found way*/

			return LARGE;

	} 	

	

	//if not reached end	

	matrix[currentR][currentC].status=OPEN;

	result=Smallest4(

		GetMin(matrix,currentR,currentC+1,endR,endC,rows,columns,

		&(matrix[currentR][currentC])),

		GetMin(matrix,currentR,currentC-1,endR,endC,rows,columns,

			&(matrix[currentR][currentC])),

		GetMin(matrix,currentR+1,currentC,endR,endC,rows,columns,

			&(matrix[currentR][currentC])),

		GetMin(matrix,currentR-1,currentC,endR,endC,rows,columns,

			&(matrix[currentR][currentC])));


	//set current status to closes- can try here again	

	matrix[currentR][currentC].status=CLOSED;

	

	//if was blocked all directions

	if (result==LARGE)

		return LARGE;


	return matrix[currentR][currentC].value+result;

}

[WingedPanther]

It would help if you included what a node is, and explained your logic.

[Lance]

Looks like a typical dynamic programming problem. And yes, it can be solved recursively. Loop is generally more efficient though.

			matrix[currentR][currentC].value+				
				father->bestFromStart;

What if either matrix[currentR][currentC].value or father->bestFromStart is LARGE?

LARGE+10 may well be 9, naturally you can not expect correct result from your program.

Edited by Lance, 10 February 2009 - 07:31 PM.
is -> if

[msshapira]

LARGE is the MAX value for long int 2147483646
it not fault tolerent, but in the same way, its not fault tolerent to any number greater than this....

[Lance]

You do know LARGE(maxinum unsigned integar) is equivalent to -1 in this case, don't you?

You need a code before addition, ie, if one of the oprands is LARGE, the result is LARGE, mathematically, it means INFINITE.

inline unsigned check_add(unsigned dist1, unsigned dist2)

{

          return dist1==LARGE || dist2==LARGE ? LARGE

                          : dist1+dist2;

}

[Lance]

You don't use it to signal INFINITE and as a regular number at the same time.

Or even better, if the result of an addition is less than any of the operands, the result should be deemed INFINITE, so you have

unsigned check_add(unsigned d1, unsigned d2)
{
       unsigned r=d1+d2;
       return r<d1 || r<d2 ? LARGE : r;
}

[msshapira]

oops, foget to add i have know clue how to program c++, as you see, i have been coding in C
also I think i have a condition for what you're talking about:

	if (result==LARGE)
		return LARGE;

[Lance]

No it did not.

And language barrier is not at issue in this case. You can do the same with plain old C.