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?
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.
XY+2YA +2YB ska minimeras
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.
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.
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.
Denna uppgift var en del av en examinerande inlämning.
