% Define the problem domain
% Sample state transitions between cities.
% You can adapt this for your specific problem.
transition(city_a, city_b, 10).
transition(city_a, city_c, 5).
transition(city_b, city_d, 15).
transition(city_b, city_e, 20).
transition(city_c, city_e, 10).
transition(city_d, city_f, 5).
transition(city_e, city_f, 8).
transition(city_e, city_g, 12).

% Define the heuristic function. This is problem-specific.
% In this example, it's the straight-line distance between cities.
heuristic(city_a, H) :- H is 15. % Assuming city_a to city_f is 15 units away.
heuristic(city_b, H) :- H is 12. % Assuming city_b to city_f is 12 units away.
heuristic(city_c, H) :- H is 20. % Assuming city_c to city_f is 20 units away.
heuristic(city_d, H) :- H is 8.  % Assuming city_d to city_f is 8 units away.
heuristic(city_e, H) :- H is 5.  % Assuming city_e to city_f is 5 units away.
heuristic(city_f, H) :- H is 0.  % The goal state.

% best_first_search/3 is the main predicate.
best_first_search(Start, Goal, Path) :-
    best_first_search([[Start, 0]], [], Goal, Path).

% best_first_search/4 handles the BFS algorithm.
best_first_search([[Node, _] | _], _, Goal, [Node | []]) :- Node = Goal.
best_first_search([[Node, Cost] | Rest], Visited, Goal, Path) :-
    findall([Child, NewCost], (
        transition(Node, Child, StepCost),
        NewCost is Cost + StepCost,
        heuristic(Child, H),
        NewCost + H, Child
    ), Children),
    append(Children, Rest, NewOpen),
    best_first_search(NewOpen, [Node | Visited], Goal, Path).

% Sample query:
% best_first_search(city_a, city_f, Path).