9 svar
48 visningar
Tinelina är nöjd med hjälpen!
Tinelina 111
Postad: 6 nov 2019

Grafteori/ Kombinatorik algoritmer

Jag ska hitta en algoritm som ger det kortaste värdet på vägen hem för två personer A och B. De går först tillsammans och skiljs sen åt och går sista biten hem till sig. De ska gå tillsammans så långt som möjligt.

 

Jag tänkte så här: Att man hittar den väg med lägst värde för ena personen hem och sen för den andra. Till sist ser man på kortaste vägen från A till B. Därefter ser man på skärningspunkten, det är här de ska skiljas åt.

 

Verkar det vettigt?

Laguna 6313
Postad: 6 nov 2019

Om de börjar i X, går tillsammans till Y, och sedan var för sig till hemmen A och B, är det då XY + YA + YB som ska minimeras, eller räknar man XY två gånger?

 

Vad menar du med skärningspunkten? Det kan väl inträffa att vägen AB inte har någonting gemensamt med de andra vägarna i uppgiften?

Kan du skriva av uppgiften ord för ord, alternativt lägga in en bild? Jag förstår inte vad som menas med uppgiften.

Tinelina 111
Postad: 7 nov 2019

XY+2YA +2YB ska minimeras

Tinelina 111
Postad: 7 nov 2019

Jag kom precis på att det är centerpunkten för a och b jag ska hitta, dvs den punkt som ger kortast väg för både A och B.

Smaragdalena skrev:

Kan du skriva av uppgiften ord för ord, alternativt lägga in en bild? Jag förstår inte vad som menas med uppgiften.

Du  har fortfarande inte lämnat tillräckligt med information för att vi skall kunna hjälpa dig. Vi vet inte var A och B startar, var A bor eller var B bor. Vi vet kort sagt ingenting, så vi kan inte hjälpa dig med din uppgift.

Tinelina 111
Postad: 7 nov 2019

A och B är godtyckliga. De startar i punkt X och ska hem till sig med kortast väg. XY+2YB+2YA ska minimeras. A och B bor inte så långt ifrån varandra, får jag från uppgiften. Alla kanter har värden och vi har ett ändligt antal hörn. Det är det jag har att gå på också.

 

Jag försöker hitta ett Y så att XY blir maximalt och 2YB och 2YA blir så små som möjligt. Jag tänker därför att man kanske kan använda sig av begreppet "central" som innebär att Y är den punkt som ger kortast avstånd till både A och B. Jag vill kunna välja mellan alla hörn förutom X som kandidat till Y, men jag vill endast avse avståndet till A och B.

 

Om min tanke kanske blir tydligare så

För tredje gången:

Kan du skriva av uppgiften ord för ord, alternativt lägga in en bild?

Vi behöver den exakta formuleringen av uppgiften, inte din tolkning av vad den handlar om.

Laguna 6313
Postad: 7 nov 2019 Redigerad: 7 nov 2019

Det är ganska vagt att "a och b är nära varandra". Behöver algoritmen inte fungera annars?

 

Jag skulle börja med att räkna ut kortaste avstånden från alla noder till A, B och X, i brist på bättre idéer. 

Smutsmunnen 110
Postad: 9 nov 2019

Denna uppgift var en del av en examinerande inlämning.

Svara Avbryt
Close