Interesting-Chinese postman problem

macan · Post by **macan** » Sun Mar 06, 2005 10:12 pm

hi,
i'm new in this "programming world" and i need help on basic graph algorithms, specialy on the basic problem: Chinese postman problem. It consist on calculating the minimum cost for traveling from one vertex going trough all the edges and returning back to the initial vertex.
The solution is calculating the cost of all edges and then add the cost of the minimum pair matching cost of the odd vertexs.
For now i have used the flouyd algorithm, but now i don't know how to calculate the minimum matching cost of the odd vertexs

Thanks in advanced

Observer · Post by **Observer** » Mon Mar 07, 2005 3:47 am

Hi,

You may use backtracking/recursion to find the minimum pair matching cost.

Yes I also like Chinese Postman Problem very much~

macan · Post by **macan** » Mon Mar 07, 2005 5:55 pm

Thanks, but I do not know anything about backtraking. I've searched for information but it's really difficult to understand the main objective of this recursion, 'cause if never heard of it.
I just ask for help on this topic (backtracking/recursion) and if there exists any basic algorithm to implement it in C, how it works (what's the input and what's the output), and how could implement this algorithm to this problem (minimum matching cost between the odd vertexs)

Thanks

Observer · Post by **Observer** » Mon Mar 07, 2005 6:43 pm

Hi,

I actually mean trying all matchings, with pruning (= cutting hopeless branches).

FYI, 10296 Jogging Trails is a Chinese Postman task. The judge solution also uses this idea.

Google search "branch and bound" if you need more information on pruning.

macan · Post by **macan** » Mon Mar 07, 2005 9:18 pm

ok, i'm starting to get it.
So i should try out one combination, then start cutting hopeless branches.
For example:
node node cost
1 2 5
2 3 3
2 3 5
3 4 2
3 5 4

My first try is (only odd vertex)
1,2 4,5 cost=5+2+4=11
then if i try
1,5 the cost already is 12 then i won't try this kind of combinations
That's the idea, right?
But then how i make an algorithm to try out all the possible combinationts and not including the combinations that i know that are going to cost more than the better one i have in each iteration?
Is there any basic algorithm that alredy does it?
Thanks

Per · Post by **Per** » Tue Mar 08, 2005 10:12 pm

Observer wrote:You may use backtracking/recursion to find the minimum pair matching cost.

There are also poly-time algorithms for finding a minimum weight matching, but they're quite complicated.