Mae Siôn Corn yn paratoi at ei daith flynyddol i ogofâu ar draws y Canolbarth cyn y Nadolig. Bydd yn dechrau ac yn gorffen ei daith yn Aberystwyth, lle mae'r sled wedi'i llenwi ac mae'r ceirw yn ysu am gael cychwyn. Ei dasg? Ymweld â phob tref unwaith yn union, dosbarthu'r nwyddau Nadoligaidd, a dychwelyd i Aberystwyth cyn iddi nosi.

I helpu Siôn Corn i gynllunio ei daith i'r ogofâu, rydym wedi rhoi'r pellteroedd rhwng pob pâr o drefi mewn tabl cyfeirio defnyddiol. Mae rhai o'r llwybrau wedi'u dangos yn y map isod - ond mae'r rhwydwaith llawn yn cynnwys pob cysylltiad uniongyrchol posib, sy'n golygu y gall Siôn Corn ddewis y llwybr mwyaf effeithlon ar gyfer ei sled.

Y map anghyflawn:

Y tabl cyfeirio:

Sut i ddatrys yr her

Dyma enghraifft o Broblem y Trafaeliwr Gwerthu (neu Broblem y Gwerthwr Teithiol). Mae sawl ffordd wahanol o ddatrys y rhain. Bydd y rhan hon yn eich tywys trwy'r dull mathemategol y gwnaethom ni ei ddefnyddio.

Cam 1: Y map

Fel y dywedwyd, mae'r map a roddir gyda'r pos hwn yn anghyflawn. Felly, efallai y bydd angen i chi ail-lunio'r map gyda'r holl gysylltiadau a mesuriadau i'ch helpu i weld y broblem hon.

Dangos y map llawn

Cam 2: Coeden Rychwantu Leiaf (MST)

I'r broblem hon, fe ddewisasom ni lunio rhywbeth o'r enw Coeden Rychwantu Leiaf, a ddatblygwyd gan ddefnyddio dull o'r enw Algorithm Prim. Mae hyn yn cysylltu'r holl leoedd â'i gilydd gan ddefnyddio'r llwybrau byrraf posib. Gadewch i mi fynd â chi trwy sut mae hyn yn gweithio.

1. Edrychwch ar Aberystwyth a nodi'r llwybr byrraf sy'n arwain i ffwrdd ohoni.

   Datgelu'r datrysiad i'r cam hwn

   



2. Nawr mae angen dod o hyd i'r llwybr byrraf i ffwrdd o'r naill neu'r llall o'r nodau cysylltiedig hyn. Ond arhoswch - mae dau opsiwn! Mae hyn yn golygu y bydd angen i ni greu ail goeden rychwantu fel y gallwn ddilyn y ddau bosibilrwydd.

   Datgelu'r datrysiad i'r cam hwn

   Llwybr 1:

   

   Llwybr 2:

   



3. Y cam nesaf yw ystyried p'un yw'r llwybr byrraf sydd ar gael i gysylltu tref arall â'n rhwydwaith. Bob tro rydyn ni'n gwneud hyn rydym ni'n cysylltu trefi newydd â'n rhwydwaith.

   Datgelu'r datrysiad i'r cam hwn

   Llwybr 1:

   

   Llwybr 2:

   

4. Ailadroddwch y cam blaenorol i ychwanegu'r trefi olaf at ein rhwydwaith.

   Datgelu'r datrysiad i'r cam hwn

   Llwybr 1:

   

   Llwybr 2:

   

Cam 3: Ffurfio'r ddolen

Erbyn hyn mae gennym ni ddwy Goeden Rychwantu Leiaf sy'n cysylltu ein trefi â'i gilydd drwy'r llwybrau byrraf. Serch hynny, nid yw'r llwybrau hyn yn addas ar gyfer ein her ni, oherwydd er mwyn teithio i bob lle ac yn ôl i Aberystwyth, fe fyddai'n rhaid i Siôn Corn fynd drwy rai mannau fwy nag unwaith.

Felly, mae angen i ni ystyried sut i roi'r llwybr ar ffurf dolen.

I wneud hyn, gadewch i ni edrych ar ein llwybrau. Yn y ddau achos mae ein llwybr yn ymrannu yn y Drenewydd. Mae angen i ni edrych ar sut y gallwn gael gwared ar yr un hiraf o'r rhain a rhoi, yn ei le, ddolen sy'n cysylltu yn ôl ag Aberystwyth.

Ateb

Santa is preparing for his annual pre-Christmas grotto tour across Mid Wales. He'll be starting and finishing his journey in Aberystwyth, where the sleigh is stocked and the reindeer are raring to go. His mission? To visit each town exactly once, deliver festive supplies, and return to Aberystwyth before nightfall.

To help Santa plan his grotto drop-offs, we've gathered the distances between each pair of towns into a handy reference table. Some of these routes are shown in the map below - but the full network includes every possible direct connection, so Santa can choose the most efficient path for his sleigh

The incomplete map:

The reference table:

How to solve

This is an example of a Travelling Salesperson Problem (TSP). There are several different approaches to solving these. This section will take you through the mathematical method we used.

Step 1: The map

As stated, the map provided with this puzzle is incomplete. So, you may need to redraw the map with all connections and measurements as a visual aid to this problem.

Reveal full map

Step 2: Minimum Spanning Tree (MST)

For this problem, we chose to produce something called a Minimum Spanning Tree developed using an approach called Prim's Algorithm. This connects all the places together with the shortest possible routes. Let me take you through how this works.

1. Look at Aberystwyth and identify the shortest route leading away.

   Reveal stage solution

   



2. Now find the shortest route away from either of these connected nodes. But wait - there are two options! This means we will need to create a second spanning tree so we can follow both possibilities.

   Reveal stage solution

   Route 1:

   

   Route 2:

   



3. The next step involves looking at which is the shortest route available to connect a different town to our network. Each time we do this we are connecting new towns to our network.

   Reveal stage solution

   Route 1:

   

   Route 2:

   

4. Repeat the previous step to attach the last to towns to our network.

   Reveal stage solution

   Route 1:

   

   Route 2:

   

Step 3: Forming the loop

We now have two Minimum Spanning Trees connecting our towns with the shortest routes. However, these routes are not suitable for the challenge set as to travel to each place and back to Aberystwyth, Santa would have to stop at some places more than once.

So, we need to consider how to form this into a loop.

To do this, let us look at our routes. In both cases our route splits at Newtown. We need to look at how we can remove the longest of these splits and replace them with a loop connecting back to Aberystwyth.

Answer