Results are out! Find what you need...fast. Get quick advice or join the chat
Hey there Sign in to join this conversationNew here? Join for free

how to do this chinese postman problem?!

Announcements Posted on
Applying to Uni? Let Universities come to you. Click here to get your perfect place 20-10-2014
    • Thread Starter
    • 1 follower
    Offline

    ReputationRep:
    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 Files
  1. File Type: pdf AQA-MD01-W-MS-JAN08.PDF (437.9 KB, 42 views)
    • 2 followers
    Offline

    ReputationRep:
    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.
    • 2 followers
    Offline

    ReputationRep:
    and usually you find the shortest lengths by inspection (comparing them and working it out from what you see)
    • Thread Starter
    • 1 follower
    Offline

    ReputationRep:
    (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!
    • 2 followers
    Offline

    ReputationRep:
    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 :/
    • 5 followers
    Offline

    ReputationRep:
    Why does the postman have to be Chinese?
    • 2 followers
    Offline

    ReputationRep:
    (Original post by Mr Dangermouse)
    Why does the postman have to be Chinese?
    no clue. sorry
    • 8 followers
    Online

    ReputationRep:
    The algorithm was invented in 1968 by a Chinese mathematician, Kwan Mei-Ko.

    I think we should call it Kwan's algorithm.
    • Thread Starter
    • 1 follower
    Offline

    ReputationRep:
    (Original post by Mr Dangermouse)
    Why does the postman have to be Chinese?
    haha, it was invented by a chinese guy!
    • Thread Starter
    • 1 follower
    Offline

    ReputationRep:
    (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!
    • 0 followers
    Offline

    ReputationRep:
    (Original post by Mr Dangermouse)
    Why does the postman have to be Chinese?
    I'm surprised it took 4 posts before someone asked this.
    • 0 followers
    Offline

    ReputationRep:
    coz it was a chinese man that came up with this algorithm i think. about the only i did actually know for this exam.
    • 56 followers
    Offline

    ReputationRep:
    I thought someone was being racist!
    • 4 followers
    Offline

    ReputationRep:
    (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.

Reply

Submit reply

Register

Thanks for posting! You just need to create an account in order to submit the post
  1. this can't be left blank
    that username has been taken, please choose another Forgotten your password?
  2. this can't be left blank
    this email is already registered. Forgotten your password?
  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. By joining you agree to our Ts and Cs, privacy policy and site rules

  2. Slide to join now Processing…

Updated: May 18, 2012
New on TSR

What is sixth form like?

Share your story!

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