Matlab BGL

Open Travelling Salesman Problem

Asked by Mohit

Hi!

I wanted to use the A* search implementation in MatlabBGL for solving the Open Traveling Salesman problem with a given starting node (i.e. the salesman doesn't have to return to the starting node but just has to cover the whole graph). Can you kindly give me some pointers where I should be looking for additional documentation/examples.

I am trying to understand how to change the stopping criterion in A* from finding the goal node to traveling all the nodes (path length).

Also I would need to add graph properties so if you can share those examples as well.

Thanks a ton!
#M
PS: I am a beginner with these graph libraries but do know matlab

Question information

Language:
English Edit question
Status:
Answered
For:
Matlab BGL Edit question
Assignee:
No assignee Edit question
Last query:
Last reply:
Revision history for this message
David Gleich (dgleich) said : 		#1

Here is the example for astar search.

% load graphs/bgl_cities.mat
% goal = 11; % Binghamton
% start = 9; % Buffalo
% % Use the euclidean distance to the goal as the heuristic
% h = @(u) norm(xy(u,:) - xy(goal,:));
% % Setup a routine to stop when we find the goal
% ev = @(u) (u ~= goal);
% [d pred f] = astar_search(A, start, h, ...
% struct('visitor', struct('examine_vertex', ev)));

What you have to change is just remove the stopping criteria:

% [d pred f] = astar_search(A, start, h, struct('visitor', struct()));

I believe that should do what you want.

David

Can you help with this problem?

Provide an answer of your own, or ask Mohit for more information if necessary.

To post a message you must log in.