Hey! Sign in to get help with your study questionsNew here? Join for free to post

how to do this chinese postman problem?!

Announcements Posted on
Take our survey to be in with the chance of winning a £50 Amazon voucher or one of 5 x £10 Amazon vouchers 28-05-2016
  1. 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
  2. File Type: pdf AQA-MD01-W-MS-JAN08.PDF (437.9 KB, 63 views)
  3. 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.
  4. Offline

    ReputationRep:
    and usually you find the shortest lengths by inspection (comparing them and working it out from what you see)
  5. 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!
  6. 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 :/
  7. Offline

    ReputationRep:
    Why does the postman have to be Chinese?
  8. Offline

    ReputationRep:
    (Original post by Mr Dangermouse)
    Why does the postman have to be Chinese?
    no clue. sorry
  9. Offline

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

    I think we should call it Kwan's algorithm.
  10. Offline

    ReputationRep:
    (Original post by Mr Dangermouse)
    Why does the postman have to be Chinese?
    haha, it was invented by a chinese guy!
  11. 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!
  12. 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.
  13. 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.
  14. Offline

    ReputationRep:
    I thought someone was being racist!
  15. 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. Oops, you need to agree to our Ts&Cs to register
  2. Slide to join now Processing…

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.

Today on TSR

Don't be a half-term hermit

How to revise this week and still have a life

Poll
What's your biggest deadly sin?
Useful resources

Make your revision easier

Maths

Maths Forum posting guidelines

Not sure where to post? Read here first

Equations

How to use LaTex

Writing equations the easy way

Student revising

Study habits of A* students

Top tips from students who have already aced their exams

Study Planner

Create your own Study Planner

Never miss a deadline again

Polling station sign

Thinking about a maths degree?

Chat with other maths applicants

Can you help? Study help unanswered threads

Groups associated with this forum:

View associated groups
Study resources
Quick reply
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.