You are Here: Home >< Maths

# how to do this chinese postman problem?!

Announcements Posted on
Why bother with a post grad course - waste of time? 17-10-2016
1. i have got the mark scheme here for you guys to see, or if it doesnt work its from AQA D1 Jan 08.
its question 4, and i'm having some trouble!
i've done the dijkstra's algorithm and worked everything out correctly. then you have to use chinese postman to find the length of an optimum route. ive identified the odd vertices D, K, A and H, but am confused as how to find the shortest lengths.
i get with the AD, AK and AH edges, the shortest lengths will just be the label i have for them from doing the Dijkstra.
however, i dont get how the mark scheme gets the values for DK, DH and KH.
how are you supposed to identify the shortest routes?do you still use the Dijkstra labels somehow?
i'm confused!
any help would be much appreciated, thanks
Attached Images
2. AQA-MD01-W-MS-JAN08.PDF (437.9 KB, 64 views)
3. hi, i did D1 with edexcel but i assume it's the same.
firstly you select the odd order vertices, as you have done, then you work out the distances of all the possibilities of repeating them, so repeating either
AD and KH, AH and KD or AK and HD.
AD and KH would be 27(ABD) +30(KJH) =57
AH and KD would be 20(ACH) + 20(KID)=40
AK and HD would be 46(ABEIK) + 40(DIFJH) =86
you repeat AH and KD because it is shortest and then add that to the weight of the network, so 308 + 40 = 348minutes
hope that helped.
4. and usually you find the shortest lengths by inspection (comparing them and working it out from what you see)
5. (Original post by AndrewD95)
and usually you find the shortest lengths by inspection (comparing them and working it out from what you see)
oh, see this was the only bit i'm confused about. so you just have to look and try and see the shortest distance, you don't use the dijkstra labels?
thanks!
6. i think it is, in the exam board i do it in it usually isn't in the same question as dijksra's algorithm. when is your d1 exam then because i just had myy D1 retake :/
7. Why does the postman have to be Chinese?
8. (Original post by Mr Dangermouse)
Why does the postman have to be Chinese?
no clue. sorry
9. The algorithm was invented in 1968 by a Chinese mathematician, Kwan Mei-Ko.

I think we should call it Kwan's algorithm.
10. (Original post by Mr Dangermouse)
Why does the postman have to be Chinese?
haha, it was invented by a chinese guy!
11. (Original post by AndrewD95)
i think it is, in the exam board i do it in it usually isn't in the same question as dijksra's algorithm. when is your d1 exam then because i just had myy D1 retake :/
ok! thanks. er its next thursday!
12. (Original post by Mr Dangermouse)
Why does the postman have to be Chinese?
I'm surprised it took 4 posts before someone asked this.
13. coz it was a chinese man that came up with this algorithm i think. about the only i did actually know for this exam.
14. I thought someone was being racist!
15. (Original post by fdhsdfwe)
ONLINE STORE :

====( ************* )=====

n2012 comes, in order to thank everyone, characteristic, novel style, varieties, low price and good quality, and the low sale price. Thank everyone

free shipping

competitive price

any size available

accept the paypal

jordan shoes \$32

nike shox \$32

Christan Audigier bikini \$23

Ed Hardy Bikini \$23

Smful short_t-shirt_woman \$15

ed hardy short_tank_woman \$16

Sandal \$32

christian louboutin \$80

Sunglass \$15

COACH_Necklace \$27

handbag \$33

AF tank woman \$17

puma slipper woman \$30

====( ************* )=====
Well that's definitely not how I would solve this problem.

## Register

Thanks for posting! You just need to create an account in order to submit the post
1. this can't be left blank
2. this can't be left blank
3. this can't be left blank

6 characters or longer with both numbers and letters is safer

4. this can't be left empty
your full birthday is required
1. Oops, you need to agree to our Ts&Cs to register

Updated: May 18, 2012
TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Today on TSR

### A level maths

Which modules should I take?

Poll
Useful resources

## Make your revision easier

### Maths Forum posting guidelines

Not sure where to post? Read here first

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams

Can you help? Study help unanswered threads

## Groups associated with this forum:

View associated groups
Study resources

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.