The Student Room Group

how to do this chinese postman problem?!

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:smile:
Reply 1
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.
Reply 2
and usually you find the shortest lengths by inspection (comparing them and working it out from what you see)
Reply 3
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!
Reply 4
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 :/
Why does the postman have to be Chinese?
Reply 6
Original post by Mr Dangermouse
Why does the postman have to be Chinese?


no clue. sorry :frown:
Reply 7
The algorithm was invented in 1968 by a Chinese mathematician, Kwan Mei-Ko.

I think we should call it Kwan's algorithm.
Reply 8
Original post by Mr Dangermouse
Why does the postman have to be Chinese?


haha, it was invented by a chinese guy!
Reply 9
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!
(edited 11 years ago)
Reply 10
Original post by Mr Dangermouse
Why does the postman have to be Chinese?

I'm surprised it took 4 posts before someone asked this.
coz it was a chinese man that came up with this algorithm i think. about the only i did actually know for this exam.
I thought someone was being racist!
Original post by fdhsdfwe
ONLINE STORE :

====( fullmalls.com )=====


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

====( fullmalls.com )=====


Well that's definitely not how I would solve this problem.

Quick Reply

Latest