Laboration 4: Sökning efter kortaste vägen i en graf

Målsättning

I denna laboration ska ni skriva ett Java-program som använder sig av flera färdiga abstrakta datatyper (köer, mängder och hashtabeller) för att hitta den enklaste lösningen till ett icketrivialt problem: att mäta upp en viss mängd vatten med hjälp av en uppsättning hinkar i olika storlekar.

Följande saker ska du kunna när du är klar med labben:

Uppgift

Tänk dig följande problem: Du har tre hinkar som rymmer femton, tjugoen och trettiofem liter. Med hjälp av dessa ska du mäta upp exakt sjutton liter vatten ur en sjö. Hinkarna är inte graderade på något sätt så det enda sättet man kan mäta exakt är att helt fylla en hink från sjön eller från en annan hink. Man kan också tömma allt innehåll från någon hink tillbaka i sjön eller i en annan hink. När man är klar ska det finnas sjutton liter i någon av hinkarna.

För att lösa problem av denna typ måste man antingen ha en intuitiv känsla för problemet eller komma på en systematisk strategi för att hitta en lösning. Er uppgift är att skriva ett program som använder en sådan systematisk strategi för att lösa problemet. En fördel med en systematisk strategi är att den ofta är användbar för att lösa en hel grupp av likartade problem. Det program ni skriver ska kunna användas för att lösa alla "hinkhällningsproblem", d.v.s. antalet hinkar och deras volym samt den önskade volymen vatten ska kunna varieras.

Programmet ska skriva ut lösningen på lämpligt sätt. Om det finns flera lösningar så ska programmet svara med den kortaste lösningen (den med minsta antalet hällningar). Om uppgiften inte går att lösa så ska programmet upptäcka det.

Formalisering av problemet

Detta är en besvärlig typ av problem eftersom det är svårt att i förväg kunna ana vilka hällningar som leder åt rätt håll och vilka som i själva verket leder bort från målet. Därför är det svårt att i varje läge bestämma sig för vad som är ett lämpligt "drag". Istället ska vi använda oss av en algoritm där man systematiskt provar igenom alla möjligheter i varje läge.

Ett "läge" i detta problem är helt enkelt mängden vatten i de olika hinkarna. Vi kallar dessa lägen för situationer och kan t.ex. representera dem som en lista av tal där varje tal betyder mängden vatten i respektive hink. I vårt fall är då startsituationen <0 0 0>, vilket betyder att alla tre hinkarna är tomma. Från startsituationen kan vi i ett steg komma till situationerna <15 0 0>, <0 21 0> och <0 0 35> genom att fylla den första, andra respektive tredje hinken från sjön.

Från var och en av dessa situationer kan man göra nya hällningar och därigenom nå nya situationer. Till slut ska man hamna i en situation där någon av hinkarna innehåller den önskade mängden vatten. Vi kallar detta för en målsituation.

Man kan organisera situationerna i form av ett träd där startsituationen utgör roten och varje situation ger upphov till ett antal grenar, en för varje tillåten hällning. Flera situationer i detta träd kommer att vara målsituationer, men eftersom vi söker den kortaste lösningen så är vi ute efter den målsituation som ligger närmast roten. Om flera målsituationer skulle finnas med samma avstånd till roten så räcker det med att vi hittar någon av dem.

Situationerna kan organiseras i form av ett träd där startsituationen utgör roten. Situationer som man kan nå med ytterligare en hällning bildar nästa nivå i trädet. I figuren visas endast några få av alla de situationer som ingår.

Lösningsmetod

För att hitta den målsituation som finns närmast roten måste man söka av trädets situationer, nivå för nivå, med början vid roten. Denna typ av sökning kallas för breddenförst-sökning, en strategi som man kan använda i många lägen där det gäller att hitta den enklaste lösningen till ett problem där man måste prova sig igenom många olika alternativa dellösingar.

Breddenförst-genomgång innebär att situationerna i trädet behandlas "våning för våning". Detta innebär att den första målsituationen man stöter på också har den kortaste vägen från startsituationen.

Från varje situation kan vi räkna ut vilka nya situationer vi kan komma till i ett steg. Därför kan man tycka att det i princip skulle kunna vara möjligt att bygga upp hela trädet i någon form av datastruktur och därefter hitta den målsituation som ligger närmast roten. Det finns dock ett mycket allvarligt problem med denna metod: eftersom det från varje situation alltid finns ytterligare situationer att nå så kommer trädet att vara obegränsat, d.v.s. oändligt stort! Det finns alltså inga möjligheter att lagra hela trädet.

Man blir därför tvungen att successivt beräkna de nya situationerna som ska analyseras. Ett sätt att åstadkomma detta är att använda rekursion som vanligt. Här blir det då frågan om trädrekursion eftersom man rekursivt undersöker alla de situationer som genererades i ett steg. Om man använder en sådan rent rekursiv strategi kommer man emellertid inte att söka igenom trädet i rätt ordning. Vid ren rekursion gör man nämligen färdigt behandlingen av en gren innan man ger sig på nästa, d.v.s. man går på djupet i varje gren direkt, s.k. djupetförst-sökning. Detta kommer inte att ge den kortaste lösningen på något enkelt sätt och, var värre är, man blir aldrig klar ens med den första grenen eftersom trädet inte bara är oändligt stort utan också oändligt djupt.

Istället måste man använda någon metod där man väntar med att behandla situationer på nästa nivå tills man är klar med alla på den nuvarande. Ett smidigt sätt att hantera detta är att, istället för att rekursivt omedelbart behandla situationerna man kan komma till, spara dem i en tills det är dags att behandla dem. Genom att successivt ta den första situationen ur kön och lägga in de situationer denna ger upphov till i slutet av kön så kommer man automatiskt att gå igenom situationerna i breddenförst-ordning. Så fort man vid denna genomgång stöter på en målsituation har man funnit lösningen till problemet.

Det finns ett allvarligt problem med denna lösningsmetod. Eftersom det alltid finns flera möjliga hällningar i varje läge så kommer antalet situationer som genereras på varje nivå att bli större och större. Många av dessa kommer dock att vara identiska med situationer vi redan har stött på, t.ex. är det ju tillåtet att hälla vatten fram och tillbaka flera gånger mellan samma hinkar, men detta leder ju knappast till en kort lösning. Om vi inte gör något åt detta så kommer programmet ganska snart att ägna i stort sett all tid åt dessa multipla kopior av samma delproblem. En följd av detta är också att vi aldrig kan veta när det är dags att ge upp för att det inte finns någon lösning.

Med en enkel förbättring kan vi dock ändra algoritmen så att den både blir rimligt snabb och att den klarar av att upptäcka att det inte finns någon lösning. Varje gång en situation är på väg behandlas kan vi först kontrollera om den är likadan som någon situation vi har stött på tidigare. Om så är fallet finns det igen anledning att behandla den igen eftersom denna aldrig kan ge en kortare lösning än den som påträffats tidigare. Detta gäller t.ex. situationen <0 0 0> på tredje nivån i figuren som är likadan som startsituationen. Vi har alltså inget att vinna på att undersöka delträdet under denna situation vidare.

Med denna förbättring kommer man aldrig att behöva behandla de delar av trädet som är kopior av grenar som redan påträffats högre upp i trädet. Om det inte finns någon lösning till problemet så kommer kön så småningom att bli tom eftersom alla möjligheter snart blir uttömda.

Generering av nya situationer

En central del i algoritmen är att man måste räkna ut vilka situationer man kan nå från en situation genom bara en hällning. Detta är inte trivialt utan kräver att man systematiskt tänker igenom även detta delproblem ordentligt.

Vi kan för det första konstatera att man alltid häller mellan två hinkar eller mellan sjön och en hink. En förenkling man kan göra är att betrakta sjön som en jättestor hink med massor av vatten i men också med massor av plats kvar. På detta sätt slipper vi att specialbehandla hällningarna till och från sjön utan kan betrakta alla steg som hällningar mellan två hinkar.

Alla möjliga hällningar får vi genom att gå igenom alla par av hinkar och undersöka vad som händer om vi häller från den ena till den andra. Lägg märke till att man alltid häller så mycket som det går mellan två givna hinkar. Mängden vatten som hälls är alltså det minsta av mängden vatten som finns i "från-hinken" och det tomma utrymmet som finns i "till-hinken". Om denna mängd är noll kan man inte hälla alls och det aktuella paret genererar följaktligen inte någon ny situation.

Implementation

Programmet skrivs lämpligen som en "application" som får den önskade volymen samt hinkarnas volymer som parametrar på kommandoraden. Använd metoden Integer.parseInt(String) för att göra om strängarna till tal. Lösningen skriver du enklast ut genom System.out.println som vanligt.

Algoritmen som ska implementeras blir förhållandevis rättfram: börja med att lägga in startsituationen i kön, tag sedan iterativt ut första situationen ur kön, kontrollera om det är en situation vi redan har behandlat, om inte så kontrollerar vi om det är en målsituation (då är vi klara), annars genererar vi alla följdsituationer och stoppar in dessa i kön. Detta upprepas iterativt tills vi hittar en målsituation eller kön blivit tom.

När vi funnit en målsituation räcker det inte med att bara tala om vilken situation detta är. Det intressanta är ju hur man kom fram till den. Därför måste man också hålla reda på hur man kommit till varje situation. Detta gör man enklast genom att för varje situation både lagra innehållet i hinkarna och vilken situation som denna situation kom ifrån. Det är därför lämpligt att representera situationerna som instanser med två instansvariabler: en vektor med tal (innehållet i hinkarna) och en referens till fadersituationen. Du kan naturligtvis införa ytterligare instansvariabler också ifall det behövs.

En central del i algoritmen är lagringen av situationerna i en kö. Denna kö måste representeras på något sätt. Det finns ingen färdig implementation av köer i java.util men det är mycket enkelt att bygga en sådan genom att utnyttja t.ex. LinkedList för själva lagringen.

En knepig bit i algoritmen är att man måste hålla reda på vilka situationer man redan har behandlat så att man kan undvika att behandla dem igen. Vi måste alltså åstadkomma någon form av minne. En enkel metod skulle kunna vara att spara alla situationerna i en lång lista och söka igenom den varje gång. Detta kan dock bli alltför långsamt, det är en hel del situationer som ska behandlas. Vi ska istället utnyttja oss av en hashtabell för att snabbt kunna avgöra ifall vi har sett en viss situation förut eller ej. I Javas paket java.util finns både det abstrakta gränssnittet Set och den konkreta (instansierbara) klassen HashSet som passar mycket bra för denna uppgift.

Genomförande

Arbetet kan förslagsvis delas upp i tre delar:

  1. Implementera klassen Queue.
  2. Implementera klassen som representerar situationer.
  3. Implementera själva breddenförst-genomgången.

Vi ska här ge lite råd om vad man bör tänka på.

Implementation av Queue

Detta bör inte vara svårt. Utnyttja den färdiga LinkedList och implementera bara de metoder du verkligen behöver (t.ex. enqueue, dequeue och isEmpty).

Representation av Situationer

Situationerna representeras naturligtvis som objekt. Klassen bör också innehålla de metoder som har direkt med situationerna att göra. Detta gäller t.ex. beräkningen av "barnnoderna", d.v.s. alla de nya situationer som man kan komma till genom en hällning. Denna metod kan lämpligen returnera alla barnnoderna i en Collection.

Du måste också se till att implementera metoderna hashCode och equals för att HashSet ska fungera som du vill. Anledningen till detta är att du vill att två olika situationsobjekt ska betraktas som lika ifall innehållet i hinkvektorn är lika. Hashalgoritmen använder dessa två metoder för att känna igen objekt. Om man definierar en metod hashCode som räknar ut ett hashvärde (stort heltal) baserat bara på hinkinnehållet, samt en equals som bara jämför hinkinnehållen, så får man automatiskt detta att fungera.

Breddenförst-genomgången

Slutligen är det dags att implementera själva breddenförst-sökningen. Först måste man skapa kön och hashtabellen samt tillverka en startsituation som man lägger in i kön från början.

Den iterativa delen av algoritmen plockar ut situationer ur kön och behandlar dem. Om det är en målsituation är man klar. Om det är en situation som finns i hashtabellen så ignoreras den bara. Annars genererar man nya situationer och stoppar in dem i kön. Om kön blir tom så saknas lösning.

När man hittat en målsituation räcker det inte med att returnera den. Istället vill man skriva ut alla situationerna startsituationen till målsituationen. Detta kan man åstadkomma genom att följa "pappa"-fältet i situationsobjekten. För att få situationerna utskrivna i rätt ordning kan man göra rekursion till listans slut och skriva ut på vägen tillbaka.

Testkörning

När ni skriver programmet är det vettigt att provköra de olika delarna separat. Det gäller speciellt de delar som har att göra med att räkna ut nya situationer.

Det är extra viktigt att kontrollera att igenkänningen av situationer med hjälp av hashtabellen fungerar. Det räcker inte att bara provköra hela det färdiga programmet eftersom man får rätt svar även om igenkänningen inte fungerar! Resultatet blir "bara" att sökningen tar mycket längre tid. Stoppa in lite testutskrifter så att ni ser att den verkligen känner igen någonting och plocka bort dem när ni är övertygade om att detta fungerar.

Som lämpliga tester kan ni prova att med hinkarna på 15, 21 och 35 liter mäta upp 1 liter (det kan göras med fyra hällningar) och 3 liter (det kräver 8 hällningar). En lite annorlunda lösning får man om man försöker mäta upp en liter vatten med bara två hinkar, en på 101 liter och en på 103. Hur många hällningar krävs för detta?

Försök också att mäta upp 17 liter med hinkar på 15, 20 och 35 liter. Denna uppgift saknar lösning och ert program ska tala om det på lämpligt sätt.

Glöm inte att lösa ursprungsproblemet: att mäta upp 17 liter med 15, 21 och 35-litershinkarna.

Lycka till!