George Junglin

Greenhorn
+ Follow
since Sep 14, 2012
Merit badge: grant badges
For More
Cows and Likes
Cows
Total received
0
In last 30 days
0
Total given
0
Likes
Total received
0
Received in last 30 days
0
Total given
0
Given in last 30 days
0
Forums and Threads
Scavenger Hunt
expand Ranch Hand Scavenger Hunt
expand Greenhorn Scavenger Hunt

Recent posts by George Junglin

Winston Gutkowski wrote:

George Junglin wrote:I understand the min function only takes two parameters but for understanding sake.


Right, and that's why I was saying that describing the problem (or in this case, the solution you've been given) is very important.

First: That min() call takes the cell and all its immediate neighbours. Why not make it a method? And if you do, what do you think:
(a) It should look like?
(b) It should be called?

Second: I suspect that 'a' stands for 'adjacent' and 'd' stands for 'diagonal', and that the algorithm is meant to reflect the number of moves that only involve 90-degree turns. So: document it; either at the class level or with a comment on each field.

Third: That algorithm is NOT run on obstacles (you didn't mention that; at least not directly). It's also different if the "centre" cell is on one of the edges of the grid.

Fourth: What about 'rows' and 'columns' instead of 'xmax' and 'ymax'?

Fifth: You could also make your program a lot easier to read by adding a descriptive constant or two, for example:
private static final int OBSTACLE = Integer.MAX_VALUE;
...
private final int FREE_CELL_START_VALUE = rows * columns;
(Question: Why do you think this value is used?)

Sixth: Get out some paper and a pen and work out what happens when you run the algorithm once on every cell (assuming they're properly initialized).
Does that produce what you want?
If not, what do you think you might need to do?
How will you know when you DO have what you want?

You can't code a problem until you understand how it works. And when you DO write your code, making it easily readable for everybody is a major step to becoming a good programmer, rather than just "someone who writes Java code".

HIH

Winston

PS: I broke up that enormous line of yours. They make threads very hard to read. Please re-read the UseCodeTags page. Thoroughly.




I think I have come to a solution thanks to your break down, I was looking at it all wrong.

I appreciate the help and will take your advice about how to lay it out for next time I have a problem
11 years ago

Campbell Ritchie wrote:Welcome to the Ranch

Are you supposed to work out the algorithm for yourself from scratch? Or are you allowed to find it? It should be easy enough to find in an artificial intelligence book (e.g. Russell and Norvig), or on Wikipedia.



That is the algorithm we are supposed to use on each cell...


I understand the min function only takes two parameters but for understanding sake..

11 years ago
Yes, array of an array. As to the original reply, that is basically all I was given, to initialize the goal, obstacle, and free cells, then apply that algorithm. I just do not understand it. I ran a couple of for loops applying the algorithm to every cell but it does not give me what I need. Here is the outline.

Step 1: Initialize the obstacle cells using infinity (highest possible integer value), the goal cell using zero (0), and the free space cells using a large value (the product of Xmax and Ymax is safe).
Step 2: The distance increment for the vertical and horizontal neighbors is a = 1 and for the diagonal neighbors is d = 2. The distance value of a free space cell is evaluated by the following formula.
cell[x,y]=min {cell[x,y],cell[x−1,y+1]+d,cell[x,y+1]+a,cell[x+1,y +1]+d,cell[x+1,y]+a,cell[x+1,y
− 1] + d, cell[x, y − 1] + a, cell[x − 1, y − 1] + d, cell[x − 1, y] + a}
Repeat Step 2 until all of the free space cell values are changed from the initial values.

Implementation
You have to implement the following
1. Implement the distance transform algorithm.
Input: A binary matrix Output: A distance transform matrix 2. Calculate the shortest path
Input: A binary matrix, a starting point, and a goal point Output: A list containing the cell index from starting point to goal point.
3. Calculate the shortest path considering additional safety
Input: A binary matrix, a starting point, a goal point and a safety pa- rameter Output: A list containing the cell index from starting point to goal point.
11 years ago
The goal is the create this..




G is the goal... 0's represent infinity.
11 years ago
Hello everyone, this is a school assignment and I am dead stuck. First of all we are supposed to create a binary matrix, I did so like this:



Then we create a sort of obstacle.. declaring the obstacles as 0, then changing those obstacles to the max value of an integer (Integer.MAX_VALUE)
After that is done I declare my "goal cell," or where I want to get with a zero, whilst changing all the 1's (safe areas) to xmax*ymax.

They then want us to apply this algorithm to change all the free space cells from their initial values. They call is the "Distance Transform Algorithm"

cell[x,y] = min { cell[x,y] , cell[x-1,y+1] + d , cell[x,y+1] + a , cell[x+1,y+1) + d, cell[x+1,y] + a , cell[x+1,y-1] + d , cell[x,y-1]+ a , cell[x-1,y-1] +d , cell[x-1,y] + a }



Now the goal is to show on each cell, how many steps it would take to get to the 0 cell, keeping the obstacles labelled infinity.. Any idea on how to do this I am completely stuck.
I tried simply making a for loop and doing the algorithm but it is obviously the wrong way to go because my minimum value stays around xmax*ymax -1 .


Thank you!!
11 years ago