File size: 3,370 Bytes
d211a7b |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
% neighbor/2 predicate to define neighbors (replace with your own logic)
neighbor(Node, Neighbor) :- eta(Node, Neighbor, _).
neighbor(Node, Neighbor) :- eta(Neighbor, Node, _).
get_cost(Node, Neighbor, Cost) :- eta(Node, Neighbor, Cost).
get_cost(Node, Neighbor,Cost) :- eta(Neighbor, Node, Cost).
calculate_cost([_],0).
calculate_cost([Head|[Second|Rest]],Cost):-
get_cost(Head, Second, C1),
calculate_cost([Second|Rest], CRest),
Cost is C1 + CRest.
%Depth-first Search Implementation
depth_first_search(Start, Goal,Path):-
dfs(Start, Goal, [Start], Path).
% dfs/4 Goal node found.
dfs(Goal, Goal,_,[Goal]).
% dfs/4 Recurvice depth search.
dfs(Start, Goal, Visited, [Start|Path]):-
neighbor(Start, Node),
not(member(Node,Visited)),
dfs(Node, Goal, [Node|Visited], Path).
%Breadth-first Search Implementation
breadth_first_search(Start, Goal, Path) :-
bfs([0-(Start, [Start])], Goal, RevPath),
reverse(RevPath, Path).
% bfs/3 Goal node found.
bfs([_C-(Node, Path) | _], Node, Path).
% bfs/3Recursive case: Continue BFS
bfs([_C-(_Node, Path) | Rest], Goal, FinalPath) :-
expand(Path, NewNodes),
append(Rest, NewNodes, NewQueue),
keysort(NewQueue, SortedQueue),
bfs(SortedQueue, Goal, FinalPath).
% expand/2 predicate to generate neighboring nodes
expand([Node|Path], Neighbors) :-
findall(C-(Neighbor,[Neighbor | [Node|Path]]),
(neighbor(Node, Neighbor), not(member(Neighbor, Path)), calculate_cost([Neighbor | [Node|Path]], C)),
Neighbors).
% A* Search Implementation
a_star_search(Start, Goal, Path) :-
heuristic(Start, Goal, F),
a_star([F-(0, Start, [Start])], Goal, RevPath),
reverse(RevPath, Path).
% Base case: Goal node found
a_star([_F-(_G, Node, Path) | _], Node, Path).
% Recursive case: Continue A* search
a_star([_F-(G, _Node, Path) | Rest], Goal, FinalPath) :-
expand(Path, NewNodes, G, Goal),
append(Rest, NewNodes, NewQueue),
keysort(NewQueue, SortedQueue),
a_star(SortedQueue, Goal, FinalPath).
% expand/5 predicate to generate neighboring nodes with cost
expand([Node|Path], Neighbors, G_prev, Goal) :-
findall(F-(G, Neighbor, [Neighbor | [Node|Path]]),
(neighbor(Node, Neighbor), not(member(Neighbor, Path)),
calculate_cost([Neighbor|[Node|Path]], Cost),
heuristic(Neighbor, Goal, H),
G is G_prev + Cost, F is G + H),
Neighbors).
% Heuristic function to calculate the estimated distance between nodes using latitude and longitude.
heuristic(Node, Destination, Heuristic) :-
location(Node, Lat1, Lon1),
location(Destination, Lat2, Lon2),
haversine_distance(Lat1, Lon1, Lat2, Lon2, Heuristic).
% Convert degrees to radians
degrees_to_radians(Degrees, Radians) :-
Radians is Degrees * (pi / 180).
% Haversine formula to calculate the distance between two points on Earth
haversine_distance(Lat1, Lon1, Lat2, Lon2, Distance) :-
degrees_to_radians(Lat1, Lat1Rad),
degrees_to_radians(Lon1, Lon1Rad),
degrees_to_radians(Lat2, Lat2Rad),
degrees_to_radians(Lon2, Lon2Rad),
DLat is Lat2Rad - Lat1Rad,
DLon is Lon2Rad - Lon1Rad,
A is sin(DLat / 2) ** 2 + cos(Lat1Rad) * cos(Lat2Rad) * sin(DLon / 2) ** 2,
C is 2 * atan2(sqrt(A), sqrt(1 - A)),
Radius is 6371, % Earth's radius in kilometers
Distance is Radius * C.
|