A newbie's dynamic programming example in need of advice if there's any errors
Author
Dear pros, I am not pushing all the debugging work to you guys but it''s just that this piece of code took me three days to get the solution(I know I''m slow).
And now that I''ve just completed, I believe I''ll be able to get more errors spotted if I''ve asked for your professional help and guidance. Thanks =)
I''ve just written this piece of code which I hope could get some feedback on errors from the pros here....
purpose: To find the shortest route, distance to be travelled in a directed graph.
data dictionary:
Node defines a Record
location isoftype Num//numeric representation
linkage isoftype ptr toa Link_Node
endRecord
Link_Node defines a Record
distance isoftype Num
p isoftype ptr toa Node
next isoftype ptr toa Link_Node
endRecord
DESTINATION is a Num constant which denotes the ending point.
"^" denotes pointer dereference
"." same as in C++
"in [ARG]" denotes read-only/local parameter
function Calculate_Distance returnsa Num(arg isoftype in ptr toa Link_Node)
//purpose: to get a link,calculate & return min.
if(arg^.p^.location = DESTINATION) then
return arg^.distance
else
return distance + Min(arg^.p)
print("go ", arg^.p^.location)
endif
endfunction
procedure Get_Min(ln isoftype in ptr toa Link_Node,min isoftype out Num)
shortest, temp isoftype Num
shortest <- 99999//assume longest distance
loop
exit when (ln = nil)
temp <- Calculate_Distance(ln)
if(temp < shortest) then
shortest <- temp
endif
ln <- ln^.next
endloop
min <- shortest
endprocedure
procedure Min(arg isoftype in ptr toa Node,min isoftype out Num)
Get_Min(arg^.linkage,min)
endprocedure
The road may be long, wind may be rough. But with a will at heart, all shall begone. ~savage chant
Question: What keeps your recursion from examining the same node more than once? (i.e. A links to B, B links to C, C links A, etc.)
botman
botman
No, nothing to do with pointers.
Your algorithm (if I understand it correctly) is this...
1) Start at a point. Loop through all the paths from this point to other points that it connects to.
2) Get the point that is connected to by the shortest path from step 1, if this point is not the destination, call Step 1 with this point.
If you have the following graph...
A -> B (distance = 10)
A -> D (distance = 20)
A -> E (distance = 30)
B -> C (distance = 10)
B -> E (distance = 20)
C -> A (distance = 10)
C -> F (distance = 30)
D -> F (distance = 10)
E -> C (distance = 20)
E -> F (distance = 20)
...and your task was to go from A to F, you would never get there because you would do this...
1. Find the shortest path from A to somewhere else, well, that''s B.
2. Find the shortest path from B to somewhere else, well, that''s C.
3. Find the shortest path from C to somewhere else, well, that''s A.
4. Find the shortest path from A to somewhere else, well, that''s B.
5. (see step 2).
You just get into an endless loop because you don''t keep track of where you''ve been.
botman
Your algorithm (if I understand it correctly) is this...
1) Start at a point. Loop through all the paths from this point to other points that it connects to.
2) Get the point that is connected to by the shortest path from step 1, if this point is not the destination, call Step 1 with this point.
If you have the following graph...
A -> B (distance = 10)
A -> D (distance = 20)
A -> E (distance = 30)
B -> C (distance = 10)
B -> E (distance = 20)
C -> A (distance = 10)
C -> F (distance = 30)
D -> F (distance = 10)
E -> C (distance = 20)
E -> F (distance = 20)
...and your task was to go from A to F, you would never get there because you would do this...
1. Find the shortest path from A to somewhere else, well, that''s B.
2. Find the shortest path from B to somewhere else, well, that''s C.
3. Find the shortest path from C to somewhere else, well, that''s A.
4. Find the shortest path from A to somewhere else, well, that''s B.
5. (see step 2).
You just get into an endless loop because you don''t keep track of where you''ve been.
botman
Author
Oops... forgot to mention that it is based on the assumption that nodes only move from starting point to the ending point(ie. (C -> A) is not an element of the relation).
I understand that it sounds pretty strange to pros, but it tries not to be too complicated.
I understand that it sounds pretty strange to pros, but it tries not to be too complicated.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement