Clever Geek Handbook

Algorithm for a Chinese postman where some edges are optional

I have a graph that contains edges to be visited as well as edges that are optional. The edges have different weights and can be moved in any direction and as many times as required. I am trying to figure out a route that minimizes the overall weight.

As I understand it, the Chinese postman problem is related to graphs, where each edge of the graph must be visited at least once. Can anyone tell me if the above option has a "name" or points me towards algorithms that can deal with a solution of this type of plot?

I am trying to program a solution in Python, so any solutions that use this will be great, otherwise I am confident I can work with the solution.

I am just looking at Python development / using algorithms, etc., so if the question is above then I ask you to forgive me! Any information would be appreciated.

Thank,

Adam

+3


source to share


1 answer


The problem you are trying to solve is called the village postman problem, it is NP-hard. Searching for this will yield many documents, most of which deal with heuristics, for example:



+3


source






More articles:


All Articles