Find route in a system
Find route in a system
(OP)
Cann someone help me how to find path of a route in sistem,like: if i have a route from A to B i need to get all the cities that traverse from A to B ? how can thsi be done ? thanks
INTELLIGENT WORK FORUMS
FOR COMPUTER PROFESSIONALS Contact USThanks. We have received your request and will respond promptly. Come Join Us!Are you a
Computer / IT professional? Join Tek-Tips Forums!
*Tek-Tips's functionality depends on members receiving e-mail. By joining you are opting in to receive e-mail. Posting Guidelines |
|
Join your peers on the Internet's largest technical computer professional community.
It's easy to join and it's free.
Here's Why Members Love Tek-Tips Forums:
Register now while it's still free!
Already a member? Close this window and log in.
RE: Find route in a system
h
RE: Find route in a system
RE: Find route in a system
oh(1, 2, 3) means there is an edge between nodes 1 and 2 with length 3
Such an information should be in every graph problem, you should adapt it to your own problem.
The main code is in the 'path' predicate. You should see the call:
CODE
1st parameter: CurrentPath = [A] (the starting point only)
2nd parameter: Target = B (the ending point)
3rd parameter: FinalPath = Path (here we will get the result)
4th parameter: CurrentLength = 0 (we are in the starting point)
5th parameter: FinalLength = Length (here we will get the length of the final path)
CODE
path([A | Rest], B, Path, CurrentLength, Length) :-
oh(A, C, X),
\+member(C, [A | Rest]),
NewLength is CurrentLength + X,
path([C, A | Rest], B, Path, NewLength, Length).
Here is the general case:
CurrentPath = [A | Rest]
Target = B (still the initial B, it didn't change)
FinalPath = Path (still the initial variable, unchanged)
CurrentLength = CurrentLength (this is the length of CurrentPath [A | Rest]
FinalLength = Length (still the initial variable, unchanged)
A is the last visited node, we should find somewhere to go from A, we do that by querying the 'oh' predicate which returns a node C and a length X from A to C, we test that C is not a node we already visited by using \+member (not member), we add X to the CurrentLength because we want to go in C so we obtain NewLength and we continue the algorithm from C, so:
CurrentPath = [C, A | Rest]
Target = B (the same)
FinalPath = Path (the same)
CurrentLength = NewLength (old CurrentLength + X)
FinalLength = Length (the same)
Everything stops when a call to 'path' is made with B as the last visited node, this is visible in the first 'path' rule
RE: Find route in a system
RE: Find route in a system
RE: Find route in a system
RE: Find route in a system
Type help(findall) and help(assert) at the Prolog prompt to find out more about them.
RE: Find route in a system
CODE
But its not good how i wrote.Can you help me?
RE: Find route in a system
CODE
"findall values of L that satisfy some_goal(..., L, ...) and put them all in List"
Your second parameter of findall has nothing to do with L.
CODE
Now you have in List all values of L that satisfy the path predicate. You need to select only those elements that are < Len
RE: Find route in a system
CODE
Only one request of help i have,here is my code:
CODE
minn([H|T],Min) :- minn(T,Mum),(H < Mum -> Min = H; Min = Mum).
path(Ori,Dest,Len):-findall(Lenght,route([Ori],Dest,Path,0,Lenght),List),minn(List,M), M < Len,write(Ori),nl,write(Dest).
route([Dest | Rest], Dest, [Dest | Rest], Length, Length).
route([Ori | Rest], Dest, Path, CurrentLength, Length) :-
link(Ori, C,_, X),
\+member(C, [Ori | Rest]),
NewLength is CurrentLength + X,
route([C, Ori | Rest], Dest, Path, NewLength, Length).
Insted or writing Origin city and Destination,i want to print the path ? How can i modify this to show me the path ? Thanks
RE: Find route in a system
You need to modify your findall to generate not a list of lengths, but a list of pairs [Path, Length]
CODE
Now your List will be something like this:
[ [Path1, Length1], [Path2, Length2], [Path3, Length3] ]
All the paths are lists of nodes.
All the lengths are integers.
You need to modify your minn predicate so that it can process lists of this particular form. It should return the pair that has minimum length. Give it a try, you are not very far from a solution.
Also, you can try the findall call at the Prolog prompt, see exactly what it returns
RE: Find route in a system
RE: Find route in a system
1st step - a list of one element would be something like this: [ [Path, Length] ] ... the minimum of such a list is [Path, Length]
In Prolog:
CODE
2nd step - a list with more than one element would be something like this: [ [Path, Length] | Rest ] ... where [Path, Length] is the first element. Then we compute the minimum of Rest which should be something like [Path1, Length1]. Then the comparison between Length and Length1 will tell us who is the overall minimum
In Prolog:
CODE
minimum(Rest, [Path1, Length1]),
Length < Length1,
Path2 = Path,
Length2 = Length.
minimum([[Path, Length] | Rest], [Path2, Length2]) :-
minimum(Rest, [Path1, Length1]),
Length >= Length1,
Path2 = Path1,
Length2 = Length1.
You can replace the two rules with a single one and make use of the conditional operator, but I think it's more easy to understand this way.
RE: Find route in a system
CODE
minimum(List,Min).
RE: Find route in a system
CODE
This is a call with 4 parameters. Do you have 'link' facts that take 4 parameters? Because I would say that 'link' should take 3 parameters: first node, second node and length
RE: Find route in a system
RE: Find route in a system
RE: Find route in a system
CODE
link(timisoara,bucuresti,200,698).
link(timisoara,iasi,110,714).
link(craiova,timisoara,90,370).
link(brasov,craiova,185,399).
link(brasov,bucuresti,190,400).
link(bucuresti,galati,200,285).
link(bucuresti,sibiu,136,403).
link(bucuresti,iasi,195,360).
link(cluj,bucuresti,195,406).
link(cluj,iasi,200,369).
link(cluj,craiova,98,312).
minnn([[Path,Length] | Rest],[Path2,Length2]):-
minnn(Rest,[Path1,Length1]),
Length < Length1,
Path2 = Path,
Length2 = Length.
minnn([[Path,Length] | Rest],[Path2,Length2]):-
minnn(Rest,[Path1,Length1]),
Length >= Length1,
Path2 = Path1,
Length2 = Length1.
short(Ori,Dest,Min):-findall([Path,Lenght],route([Ori],Dest,Path,0,Lenght),List),
minnn(List,Min).
route([Dest | Rest], Dest, [Dest | Rest], Length, Length).
route([Ori | Rest], Dest, Path, CurrentLength, Length) :-
link(Ori, C,_, X),
\+member(C, [Ori | Rest]),
NewLength is CurrentLength + X,
route([C, Ori | Rest], Dest, Path, NewLength, Length).
RE: Find route in a system
PS: You're Romanian, so this means we're co-nationals :)
RE: Find route in a system
PS: glad to be co-nationals :) Thanks for helping a beginer. I am done with the questions for now,sorry for the stress :)
RE: Find route in a system
RE: Find route in a system