Traverse a directed graph visiting all edges at least once?

7 visualizaciones (últimos 30 días)
Michael Bockwoldt
Michael Bockwoldt el 24 de Mzo. de 2021
Comentada: Christine Tobler el 25 de Mzo. de 2021
I am working on a project utilizing the Chinese Postman Problem where I want to find the shortest path in a directed matrix that visits each edge at least once starting from a specified node. Are there any Graph Theory functions that deal with this kind of problem?

Respuestas (1)

Christine Tobler
Christine Tobler el 24 de Mzo. de 2021
There aren't any functions for MATLAB's graph object that solve this problem. Possibly you can formulate this as an optimization problem? See https://www.mathworks.com/help/optim/ug/traveling-salesman-problem-based.html for an example of how to solve the related Traveling Salesman Problem using the optimization toolbox.
  4 comentarios
Michael Bockwoldt
Michael Bockwoldt el 25 de Mzo. de 2021
Introducing a new node in the middle of each edge could potentially work.
Doing some more research, I found some code you made/commented on from 2018 on another question thread. Can this code be manipulated such that all nodes must be traversed, but nodes can be visited more than once if needed?
Thanks again for your help!
W = [5 1 5 4 6 1 1 4 7 2 6 7 3 2 1 2 3 8 2 8];
DG = sparse([1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6],...
[2 3 1 3 4 5 1 2 4 5 2 3 5 6 2 3 4 6 4 5],W);
g = graph(DG);
% Construct all possible ways that we could traverse all nodes, starting at
% node 1 and ending at node 6:
paths = perms(2:5);
paths = [ones(size(paths, 1), 1) paths 6*ones(size(paths, 1), 1)];
% Check if a path is feasible (edges exist between all node pairs), and how
% long it is
dist = NaN(size(paths, 1), 1);
for ii=1:size(paths, 1)
path = paths(ii, :);
edgeID = findedge(g, path(1:end-1), path(2:end));
if all(edgeID ~= 0)
dist(ii) = sum(g.Edges.Weight(edgeID));
end
end
[~, id] = min(dist)
paths(id, :)
p = plot(g, 'EdgeLabel', g.Edges.Weight);
highlight(p, paths(id, :), 'EdgeColor', 'red')
Christine Tobler
Christine Tobler el 25 de Mzo. de 2021
This could be used to solve the Traveling Salesman problem (not efficiently), but not for the variant your looking for.
Here I'm just going through all possible ways of visiting each node exactly once, and then taking the minimum of that large set of possibilities. But when nodes can be visited many times, there's no way to just write up all possible orders of visiting the nodes, there are infinitely many ways to do this.

Iniciar sesión para comentar.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by