12.9 Farandsölumannsvandinn – Stærðfræði í daglegu lífi (IS) | Námsgögn
1212 Netafræði
12.9 Farandsölumannsvandinn
12.9 Farandsölumannsvandinn
Mynd 12.186. Hverjar dyr á leið farandsölumanns má tákna með hnúti í neti. (mynd: „Three in a row, Heriot Row“ eftir Jason Mason/Flickr, CC BY 2.1)
Námsmarkmið
Eftir að hafa lokið þessum hluta átt þú að geta:
Greint á milli tæmandi reiknirita og gráðugra reiknirita.
Skráð allar ólíkar Hamilton-rásir fullkomins nets.
Beitt tæmandi aðferð við verkefni um farandsölumannsvandann.
Beitt aðferð næsta granna við verkefni um farandsölumannsvandann.
Í fyrri hlutum skoðuðum við Hamilton-rásir og Hamilton-vegi. Hér greinum við Hamilton-rásir í fullkomnum vegnum netum til að finna stystu leiðina sem heimsækir tiltekna staði og snýr aftur á upphafsstað. Auk verkefna um stystu vegalengdina eru til verkefni þar sem leitað er að ódýrustu eða fljótlegustu leiðinni. Á vef stærðfræðideildar Waterloo-háskóla í Ontario í Kanada má lesa um nokkur sjaldgæfari notkunarsvið:
Hönnun ljósleiðaraneta
Lágmörkun eldsneytiskostnaðar við tilfærslu gervitungla
Þróun hálfleiðara fyrir örflögur
Aðferð til að kortleggja litninga spendýra við raðgreiningu erfðamengja
Áður en við skoðum leiðir til að leysa slík verkefni skulum við ræða tvær gerðir reiknirita sem við notum.
Tæmandi og gráðug reiknirit
Reiknirit er skrefaröð sem nota má til að leysa tiltekið verkefni. Við höfum leyst mörg verkefni í þessum kafla og aðferðirnar voru mismunandi reiknirit. Hér notum við tvær algengar gerðir: tæmandi reiknirit og gráðugt reiknirit. Tæmandi reiknirit skráir fyrst allar mögulegar lausnir og prófar hverja þeirra þar til besta lausnin finnst. Gráðugt reiknirit leysir verkefni í áföngum, velur það sem virðist best í hverjum áfanga og tengir valkostina síðan saman í heildarlausn sem er ekki endilega sú besta.
Til að skilja muninn skulum við skoða tréð á mynd 12.187. Við viljum finna veg frá vinstri til hægri með hæstu heildarsummuna. Grein A hefur til dæmis summuna 10 + 2 + 11 + 13 = 36.
Mynd 12.187. Stig eftir mismunandi vegum
Til að vera viss um að velja greinina með hæstu summuna mætti skrá summu hverrar greinar:
A:
B:
C:
D:
E:
F:
G:
H:
Þá vitum við með vissu að grein E hefur hæstu summuna.
Mynd 12.188. Grein E
Gerum nú ráð fyrir að þú viljir finna greinina með hæsta gildið en fáir tréð aðeins sýnt í áföngum, eitt skref í einu.
Mynd 12.189. Tré, áfangi 1
Eftir fyrsta áfanga myndirðu velja greinina með 10 og 7. Enn fylgirðu sömu grein. Skoðum næsta áfanga.
Mynd 12.190. Tré, áfangi 2
Eftir annan áfanga myndirðu, miðað við upplýsingarnar sem liggja fyrir, velja greinina með 10, 7 og 4. Nú fylgirðu annarri grein en áður en hún er besti kosturinn samkvæmt fyrirliggjandi upplýsingum. Skoðum síðasta áfangann.
Mynd 12.191. Tré, áfangi 3
Eftir þriðja áfanga velurðu grein G, sem hefur summuna 32.
Að leggja saman gildin á hverri grein og velja hæstu summuna er dæmi um tæmandi reiknirit því allir kostir voru kannaðir nákvæmlega. Að velja grein í áföngum út frá besta kostinum í hverjum áfanga er gráðugt reiknirit. Tæmandi reiknirit gefur bestu lausnina en getur tekið mjög langan tíma. Hugsaðu þér tré með þúsundum eða milljónum greina; hugsanlega er ekki hægt að athuga allar summurnar. Gráðugu reikniriti má hins vegar ljúka tiltölulega fljótt og það gefur yfirleitt góða lausn, en ekki endilega þá bestu.
Dæmi 12.42
Tæmandi og gráðug reiknirit aðgreind
Gjaldkeri skráir sölu að upphæð 4,63 Bandaríkjadalir og viðskiptavinurinn greiðir með fimm dala seðli. Gjaldkerinn vill skila 0,37 dölum með sem fæstum myntum. Nota má 25 senta, 10 senta, 5 senta og eins sents mynt. Fyrst velur gjaldkerinn verðmætustu mynt sem er ekki meira en 0,37 dalir, 25 sent. Þá standa eftir 0,37 − 0,25 = 0,12 dalir. Næst velur hann 10 sent og þá standa eftir 0,12 − 0,10 = 0,02 dalir. Síðan velur hann eins sents mynt tvisvar. Engin upphæð stendur eftir. Hann notaði eina 25 senta mynt, eina 10 senta mynt og tvær eins sents myntir, alls fjórar myntir. Notaðu upplýsingarnar til að svara spurningunum.
Er aðferð gjaldkerans dæmi um gráðugt eða tæmandi reiknirit? Rökstyddu svarið.
Lausn gjaldkerans er sú besta, því fjórar myntir er lágmarksfjöldinn. Samræmist það niðurstöðu reiknirits af þessari gerð? Rökstyddu svarið.
Lausn
Gjaldkerinn notaði gráðugt reiknirit því verkefnið var leyst í áföngum og besti kosturinn valinn í hverjum þeirra. Aðferðin er ekki tæmandi því hann skráði ekki allar mögulegar samsetningar mynta.
Já. Gráðugt reiknirit gefur ekki alltaf bestu niðurstöðuna en gerir það stundum.
Farandsölumannsvandinn
Beinum nú athyglinni að farandsölumannsvandanum (TSP), þar sem finna þarf stystu leið sem heimsækir tiltekna staði og snýr aftur á upphafsstað.
Rifjaðu upp liðsforingjann í bandaríska flughernum við Vandenberg-flugherstöðina sem þurfti að aka til þriggja annarra stöðva í Kaliforníu og aftur til Vandenberg. Hann þurfti að heimsækja hverja stöð einu sinni. Vegið netið á mynd 12.192 táknar stöðvarnar Vandenberg, Edwards, Los Angeles og Beale og fjarlægðirnar milli þeirra.
Mynd 12.192. Net fjögurra flugherstöðva í Kaliforníu
Sérhver leið sem heimsækir hverja stöð og snýr aftur á upphafsstað er Hamilton-rás í netinu. Ef liðsforinginn vill fara stystu vegalengd samsvarar það Hamilton-rás með lægsta vægið. Í töflu 12.11 sáum við að sex ólíkar Hamilton-rásir eru í fullkomnu neti með fjóra hnúta en sumar þeirra liggja á sömu óstefndu rásinni.
Fullkomið net
Rás
Rás
Rás
Hamilton-rás réttsælis
Hamilton-rás rangsælis
Þar sem fjarlægðin milli stöðva er sú sama í báðar áttir skiptir ekki máli hvort farið er réttsælis eða rangsælis. Því eru í raun aðeins þrjár mögulegar vegalengdir eins og mynd 12.193 sýnir.
Mynd 12.193. Þrjár mögulegar vegalengdir
Mögulegar vegalengdir eru:
Hamilton-rás með lægsta vægið er því → E → L → V, eða sama leið í gagnstæða átt. Liðsforinginn ætti að fara frá Vandenberg til Beale, þaðan til Edwards og Los Angeles og aftur til Vandenberg.
Vægi allra Hamilton-rása í fullkomnum netum fundið
Við skráðum allar Hamilton-rásirnar og fundum vægi þeirra þegar við leystum farandsölumannsvandann um liðsforingjann í Vandenberg. Til að tryggja að engin gleymist má reikna fjölda mögulegra Hamilton-rása í fullkomnu neti. Einnig er gagnlegt að vita að helmingur stefndra rása í fullkomnu neti er sama rásin í gagnstæða átt. Því þarf aðeins að reikna helming mögulegra vægja; hitt eru tvítekningar.
Dæmi 12.43
Möguleg vægi Hamilton-rása reiknuð
Gerum ráð fyrir fullkomnu vegnu neti með hnútana N, M, O og P.
Notaðu formúluna (n − 1)! til að reikna fjölda ólíkra Hamilton-rása í netinu.
Notaðu formúluna (n − 1)!/2 til að reikna mesta mögulega fjölda ólíkra vægja Hamilton-rásanna.
Eru allar ólíku Hamilton-rásirnar skráðar? Hvernig veistu það? Rás 1: N → M → O → P → N; rás 2: N → M → P → O → N; rás 3: N → O → M → P → N; rás 4: N → O → P → M → N; rás 5: N → P → M → O → N; rás 6: N → P → O → M → N
Hvaða rásapör hljóta að hafa sama vægi? Hvernig veistu það?
Lausn
Hnútarnir eru fjórir og því er n = 4. Það merkir að (n − 1)! = (4 − 1)! = 3 · 2 · 1 = 6 ólíkar Hamilton-rásir hefjast í hverjum völdum hnúti.
Þar sem n = 4 eru (n − 1)!/2 = (4 − 1)!/2 = 6/2 = 3 möguleg vægi.
Já, þær eru allar ólíkar og eru sex talsins.
Rásir 1 og 6 hafa sama vægi, rásir 2 og 4 sama vægi og rásir 3 og 5 sama vægi því hvert par fer sömu leið um netið í gagnstæðar áttir.
Tæmandi aðferðin
Aðferðin sem við höfum notað til að finna Hamilton-rás með lægsta vægið í fullkomnu neti er tæmandi reiknirit og nefnist því tæmandi aðferðin. Skrefin eru:
Skref 1: Reiknaðu fjölda ólíkra Hamilton-rása og mögulegra vægja.
Skref 2: Skráðu allar mögulegar Hamilton-rásir.
Skref 3: Finndu vægi hverrar rásar.
Skref 4: Tilgreindu Hamilton-rásina með lægsta vægið.
Dæmi 12.44
Tæmandi aðferðinni beitt
Í næsta verkefni þarf liðsforinginn að leggja af stað frá Travis-flugherstöðinni, heimsækja Beale-, Edwards- og Vandenberg-flugherstöðvarnar nákvæmlega einu sinni og snúa aftur til Travis. Ekki þarf að heimsækja Los Angeles-flugherstöðina. Notaðu mynd 12.194 til að finna stystu leiðina.
Mynd 12.194. Fjarlægðir milli fimm flugherstöðva í Kaliforníu
Lausn
Skref 1: Þar sem hnútarnir eru fjórir verða rásirnar (4 − 1)! = 3! = 6. Helmingur þeirra er andhverfa hinna og því verða mögulegar vegalengdir (4 − 1)!/2 = 6/2 = 3.
Skref 2: Skráðu allar Hamilton-rásir í hlutanetinu á mynd 12.195.
Mynd 12.195. Hlutanet með stöðvunum B, E, T og V
Til að finna rásirnar sex skaltu einbeita þér að hnútunum þremur á milli, B, E og V. Raðanir þeirra eru BEV, BVE, EBV, EVB, VBE og VEB. Þær samsvara rásunum sex:
1: T → B → E → V → T
2: T → B → V → E → T
3: T → E → B → V → T
4: T → E → V → B → T
5: T → V → B → E → T
6: T → V → E → B → T
Skref 3: Finndu vægi hvers vegar. Draga má úr vinnunni með því að greina rásir sem eru andhverfur hver annarrar.
1: 84 +410 +207 +396 =1097
2: 84 +396 +207 +370 =1071
3: 370 +410 +396 +396 =1572
4: Andhverfa rásar 2, 1071
5: Andhverfa rásar 3, 1572
6: Andhverfa rásar 1, 1097
Skref 4: Tilgreindu Hamilton-rás með lægsta vægið.
Annar vegurinn, T → B → V → E → T, og andhverfa hans, → → T, hafa lægsta vægið. Liðsforinginn ætti að fara frá Travis-flugherstöðinni til Beale, Vandenberg og Edwards og aftur til Travis, eða fara sömu leið í gagnstæða átt.
Gerum nú ráð fyrir að liðsforinginn þurfi rás sem heimsækir allar fimm flugherstöðvarnar á mynd 12.194. Þá eru (5 − 1)! = 4! = 24 mismunandi raðanir hnúta og (5 − 1)!/2 = 12 vegalengdir sem þarf að bera saman með tæmandi aðferðinni. Fyrir tíu flugherstöðvar væru (10 − 1)! = 9! = 362.880 mismunandi raðanir og (10 − 1)!/2 = 181.440 vegalengdir. Það hlýtur að vera til önnur leið!
Aðferð næsta granna
Þegar tæmandi aðferðin er óhentug fyrir farandsölumannsvandann má nota gráðuga reikniritið aðferð næsta granna, sem velur alltaf næsta eða ódýrasta stað fyrst. Aðferðin finnur Hamilton-rás með tiltölulega lágt vægi í fullkomnu neti. Í hverjum áfanga eru leggir frá núverandi hnúti til óheimsóttra hnúta bornir saman og sá með lægsta vægið valinn. Aðferðin gefur yfirleitt ekki bestu lausnina en oft nægilega góða. Fjöldi skrefa er jafnmargur hnútunum: verkefni með tíu hnúta þarf tíu skref, ekki 362.880.
Frambjóðandi til ríkisstjóra vill halda fundi víða um fylkið. Hann hyggst leggja af stað heiman frá sér í borg A, heimsækja borgir B, C, D, E og F einu sinni hverja og snúa aftur heim. Flugfargjöld milli borganna eru sýnd í netinu á mynd 12.196.
Mynd 12.196. Flugfargjöld milli borga A, B, C, D, E og F
Hjálpum frambjóðandanum að halda ferðakostnaði niðri með aðferð næsta granna. Merkjum upphafshnútinn , „heimsóttur fyrst“. Berum síðan saman vægi leggja frá A til hnúta sem liggja að A: 250, 210, 300, 200 og 100 dalir, eins og á mynd 12.197. Lægsta vægið er 100 dalir á leggnum A–F.
Mynd 12.197. Annar hnúturinn fundinn
Merkjum F sem , „heimsóttur annar“, og berum saman vægi leggja frá F til óheimsóttu hnútanna sem liggja að F: 170, 330, 150 og 350 dalir, eins og á mynd 12.198. Lægsta vægið er 150 dalir á leggnum F–D.
Mynd 12.198. Þriðji hnúturinn fundinn
Merkjum D sem , „heimsóttur þriðji“. Berum næst saman vægi leggja frá D til óheimsóttu hnútanna sem liggja að D: 120, 310 og 270 dalir, eins og á mynd 12.199. Lægsta vægið er 120 dalir á leggnum D–B.
Mynd 12.199. Fjórði hnúturinn fundinn
Merkjum B sem , „heimsóttur fjórði“. Berum loks saman vægi leggja frá B til óheimsóttu hnútanna sem liggja að B: 160 og 220 dalir, eins og á mynd 12.200. Lægra vægið er 160 dalir á leggnum B–E.
Mynd 12.200. Fimmti hnúturinn fundinn
Merkjum E sem og eina hnútinn sem eftir er, C, sem . Þetta sést á mynd 12.201. Vægi leggsins frá E til C er 180 dalir og frá C aftur til A er það 210 dalir.
Mynd 12.201. Sjötti hnúturinn fundinn
Hamilton-rásin sem fannst er A → F → D → B → E → C → A. Vægi hennar er 100 + 150 + 120 + 160 + 180 + 210 = 920 dalir. Hún kann að vera ódýrasta leiðin en er líklega mjög nærri henni, enda eru flest vægin meðal þeirra lægstu í netinu. Við fundum hana í sex skrefum í stað þess að finna 120 Hamilton-rásir og reikna 60 vægi.
Skref 1: Veldu upphafshnút og merktu hann , „heimsóttur fyrst“. Finndu legginn með lægsta vægið milli og óheimsóttu hnútanna.
Skref 2: Merktu hnútinn við enda lægsta leggsins , þar sem n sýnir heimsóknarröðina. Finndu legginn með lægsta vægið milli og hnútanna sem eftir er að heimsækja.
Skref 3: Ef óheimsóttir hnútar eru eftir skaltu endurtaka skref 2. Annars er Hamilton-rás með lágt vægi .
Dæmi 12.45
Aðferð næsta granna notuð
Frambjóðandinn vill halda fundi víða um fylkið en lítill tími er fram að kosningum. Hann vill leggja af stað frá A, heimsækja B, C, D, E og F einu sinni og snúa aftur heim. Ferðatíminn á mynd 12.202 skiptir meira máli en fargjaldið. Notaðu aðferð næsta granna til að finna leið með tiltölulega stuttan ferðatíma og reiknaðu heildartímann.
Mynd 12.202. Ferðatími milli borga A, B, C, D, E og F
Lausn
Skref 1: Merktu hnútinn A sem . Lægsta vægið milli A og óheimsóttu hnútanna er 85 mínútur, á milli A og D.
Skref 2: Merktu hnútinn D sem . Lægsta vægið milli D og óheimsóttu hnútanna B, C, E og F er 70 mínútur, á milli D og F.
Endurtaktu skref 2: Merktu hnútinn F sem . Lægsta vægið milli F og óheimsóttu hnútanna B, C og E er 75 mínútur, á milli F og C.
Endurtaktu skref 2: Merktu hnútinn C sem . Lægsta vægið milli C og óheimsóttu hnútanna B og E er 100 mínútur, á milli C og B.
Endurtaktu skref 2: Merktu hnútinn B sem . Eini óheimsótti hnúturinn er E. Vægi leggsins milli B og E er 95 mínútur.
Skref 3: Hamilton-rás með lágt vægi er A → D → F → C → B → E → A. Tiltölulega fljótleg leið er því frá A til D, F, C, B og E og aftur til A. Heildartíminn er 85 + 70 + 75 + 100 + 95 + 90 = 515 mínútur, eða 8 klukkustundir og 35 mínútur.
Athugaðu skilning þinn
Kostur gráðugs reiknirits er að það er skilvirkara.
Satt
Ósatt
Ókostur tæmandi reiknirits er að það gefur ekki alltaf bestu lausnina.
Satt
Ósatt
Aðferð næsta granna er tæmandi reiknirit.
Satt
Ósatt
Tæmandi aðferðin er gráðugt reiknirit.
Satt
Ósatt
Tæmandi aðferðin finnur Hamilton-rás með lægsta vægið í fullkomnu neti.
Farandsölumannsvandinn felst í að finna stystu leið milli tveggja punkta.
Satt
Ósatt
Farandsölumannsvandann má tákna sem leit að Hamilton-rás með lægsta vægið í vegnu neti.
Satt
Ósatt
Alltaf eru fleiri en ein Hamilton-rás með lægsta vægið: tiltekin rás og andhverfa hennar.
Satt
Ósatt
Mesti mögulegi fjöldi ólíkra vægja Hamilton-rása fullkomins nets með n hnúta er (n − 1)!
Satt
Ósatt
Verkefni úr hluta 12.9
Ákvarðaðu hvort lýst reiknirit sé gráðugt eða tæmandi.
1.
Reikniritið til að lita net fólst í að lita fyrst hnútinn með hæsta stigið, síðan sem flesta aðra hnúta með hverjum lit í lækkandi stigaröð og endurtaka ferlið fyrir hnútana sem eftir voru.
2.
Vörubretti á að flytja á tíu pallbílum með þyngdartakmörk. Allar mögulegar skiptingar vörunnar í tíu hópa eru skráðar og heildarþyngd hvers hóps reiknuð til að ákveða samlestun.
3.
Brúðkaupsskipuleggjandi raðar gestum til borðs. Parið hefur tilgreint hvaða gestir þurfa að sitja saman og vill nota sem fæst borð. Skipuleggjandinn skráir allar mögulegar sætaraðanir og velur eina sem uppfyllir skilyrðin.
4.
Pakka þarf að hlaða í lestarvagna og æskilegt er að nota sem fæsta. Í hvern vagn er fyrst settur sá pakki með mesta ummálið sem rúmast og það endurtekið þar til vagninn er fullur. Þá er næsti vagn hlaðinn.
Notaðu myndina til að reikna fjölda ólíkra Hamilton-rása sem hefjast í gefnum hnúti. Hve margar þeirra gætu haft ólíkt vægi?
5.
Net A, hnútur a
6.
Net B, hnútur e
7.
Net C, hnútur k
8.
Net D, hnútur o
Notaðu myndina til að skrá allar ólíkar Hamilton-rásir sem hefjast í gefnum hnúti. Tilgreindu hvaða rásapör eru andhverfur hvert annars.
9.
Net A, hnútur a
10.
Net B, hnútur e
11.
Net C, hnútur k
12.
Net D, hnútur o
Notaðu myndina og tæmandi aðferðina til að finna Hamilton-rás með lægsta vægið sem hefst í gefnum hnúti. Hvert er vægi rásarinnar?
13.
Net A, hnútur a
14.
Net B, hnútur e
15.
Net C, hnútur k
16.
Net D, hnútur o
Notaðu myndina og aðferð næsta granna til að finna Hamilton-rás með lágt vægi sem hefst í gefnum hnúti. Hvert er vægi rásarinnar?
17.
Net A, hnútur a
18.
Net B, hnútur e
19.
Net C, hnútur k
20.
Net D, hnútur o
Notaðu lausnir verkefna 13–20 til að bera saman tæmandi aðferðina og aðferð næsta granna fyrir hvert net. Segðu hvort Hamilton-rásirnar og vægin hafi verið eins eða ólík. Ef vægin eru ólík, hvor aðferðin gaf lægra vægi? Samræmist það eiginleikum tæmandi og gráðugra reiknirita? Rökstyddu svarið.
21.
Net A, hnútur a
22.
Net B, hnútur e
23.
Net C, hnútur k
24.
Net D, hnútur o
Notaðu töfluna til að búa til fullkomið vegið net þar sem hnútarnir eru gefnu borgirnar og vægin fjarlægðirnar milli þeirra.
Borgir
U
V
W
X
Y
Z
U
0
89
37
49
54
28
V
89
0
76
68
92
112
W
37
76
0
45
52
49
X
49
68
45
0
66
47
Y
54
92
52
66
0
29
Z
28
112
49
47
29
0
25.
U, V, W, X
26.
U, W, Y, Z
27.
U, X, Y, Z
28.
U, V, W, X, Y
29.
U, W, X, Y, Z
30.
U, V, W, X, Y, Z
Notaðu lausnir verkefna 25–30 og aðferð næsta granna til að finna Hamilton-rás sem gefur hæfilega stutta leið frá borg
U
um allar hinar borgirnar og aftur til borgar
U
Tilgreindu vegalengd leiðarinnar.
31.
U, V, W, X
32.
U, W, Y, Z
33.
U, X, Y, Z
34.
U, V, W, X, Y
35.
U, W, X, Y, Z
36.
U, V, W, X, Y, Z
Notaðu lausnir verkefna 25–30 og tæmandi aðferðina til að finna Hamilton-rás með lægsta vægið fyrir stystu leið frá borg
U
um allar hinar borgirnar og aftur til borgar
U
Tilgreindu vegalengd leiðarinnar.
37.
U, V, W, X
38.
U, W, Y, Z
39.
U, X, Y, Z
40.
U, V, W, X, Y
41.
U, W, X, Y, Z
Notaðu tilgreind verkefni til að bera saman tæmandi aðferðina og aðferð næsta granna fyrir farandsölumannsvandann um hæfilega stutta leið frá borg
U
um allar hinar borgirnar og aftur til borgar
U
Tilgreindu hvort gráðuga reikniritið gaf Hamilton-rás með sama, lægra eða hærra vægi. Samræmist það eiginleikum reikniritanna? Rökstyddu svarið.
42.
Verkefni 32 og 38: U, W, Y, Z
43.
Verkefni 31 og 37: U, V, W, X
44.
Verkefni 34 og 40: U, V, W, X, Y
45.
Verkefni 35 og 41: U, W, X, Y, Z
46.
Verkefni 33 og 39: U, X, Y, Z
Vörur verksmiðju eru framleiddar í áföngum. Sami búnaður er notaður í öllum áföngum en þarf að stilla hann á mismunandi hátt. Tíminn til að skipta milli stillinga er gefinn í töflu 12.13. Notaðu töfluna og aðferð næsta granna til að finna verkefnaröð sem lágmarkar stillitíma og endar með sömu stillingu og í upphafi svo verksmiðjan sé tilbúin fyrir næstu lotu. Engar skorður eru á röð verkefna. Athugaðu allar mögulegar upphafsstillingar því aðferðin getur gefið ólíkar niðurstöður eftir upphafshnúti.
