Tävlingsprogrammering/Uppgifter/Nätvärk
Nätvärk
Fil:Kommer-snart.png
FIGUR 3. Ett nätverk med 10 datorer. Om fiberkabeln dras via dator 1, 2, 3, 5, 8 och 9 (markerat med tjocka linjer) kommer alla datorer utom nummer 7 att ligga högst en länk ifrån fiberkabeln, vilket är optimalt.
Bandbredden på företaget Caterpillar AB's intranät ska utökas. Deras datornätverk består av n datorer som är sammankopplade med n − 1 länkar, så att alla datorer kan kommunicera med varandra. ITavdelningen har fått i uppdrag av styrelsen att ersätta en del av dessa länkar med en ny tjock fiberkabel. Kabeln får inte förgrena sig, men kan vara hur lång som helst.
Alla datorer som ligger längs kabeln eller högst en länk ifrån denna kan utnyttja den extra bandbredden. Eftersom Caterpillar AB är ett stort företag med många datorer är det inte helt enkelt att bestämma var den ny fiberkabeln ska dras, så att flest antal datorer kan utnyttja den högre bandbredden. Detta har orsakat stor huvudvärk hos IT-avdelningen, så de har därför outsourcat problemet åt dig.
Programmet ska läsa datornätverkets struktur från filen network.dat. Första raden i filen innehåller talet n (mellan 1 och 2500). Därefter följer n − 1 rader som beskriver länkarna mellan datorerna. Varje sådan rad består av två heltal mellan 1 och n, numren på datorerna som länken förbinder. Programmet ska skriva ut maximalt antal datorer som kan utnyttja den utökade bandbredden om fiberkabeln dras optimalt.
Körningsexempel:
Filen network.dat med innehållet: 10 1 2 2 3 3 4 3 5 5 6 6 7 5 8 8 9 8 10 ska ge svaret: Maximalt antal datorer: 9
Lösning
[redigera]När man löser den här uppgiften, så hoppar ens hjärna mellan hopp och förtvivlan. Först tycker man den är lätt, sedan svår, sedan lätt och slutligen lagom. Först och främst kan man ju fråga sig var man ska börja dra kabeln? Att testa att börja dra kabeln vid varje dator är inte särskilt effektivt, nej de datorer som torde vara kandidaterna för där man ska börja dra kabeln (och även avsluta den) är änddatorerna i nätverket, dvs de datorer som bara har en anslutning med en annan dator. Givetvis kan man inte bara börja vid vilken änddator som helst, eftersom änddatorn själv kanske inte ingår i den optimala lösningen, varför vi måste testa att börja dra vid varje änddator.
Med den idén klar sätter man ingång och läser in alla datorer från filen, samt sparar undan referenser till de datorer som är änddatorer (de vi senare ska testa att börja dra kabel vid). Men plötsligt slås man av ett skräckscenario, tänk om det kan förekomma cykler i nätverket? Svaret på den frågan är emellertid Nej, eftersom alla datorer är kopplade till nätverket och det finns endast n-1 stycken länkar. (Om man ska koppla samman n stycken datorer med n-1 stycken länkar, så är det faktiskt omöjligt att konstruera cykler. Tack och lov.) Hur går man vidare nu? En idé kan vara att man börjar dra kabeln vid en änddator (och tänker nätverket som ett träd) och sedan fortsätter man i den riktning man tidigare inte kom ifrån (man får inte gå uppåt i trädet), so far so good. Men om vi kommer till en dator från vilken vi kan välja att gå vidare till fler än en dator? Vilken dator ska vi välja att dra kabeln vidare igenom? Ja med det är ju enkelt, vi väljer bara den dator som har flest datorer sammankopplade med sig (även indirekt, dvs alla barn till datorn om vi betraktar det hela som ett träd) bortsett från datorn vi kom ifrån och datorerna som binds samman via den. Men vänta nu stämmer verkligen det? Det bistra sanningen är NEJ, för även om det finns fler datorer i en riktning än en annan, så finns det ju inga garantier för att vi kommer att kunna gynna alla datorer med kabeln i den ena riktningen. I riktningen med färre datorer kan kanske alla ligga snyggt på rad, medan datorerna i riktningen med fler kanske förgrenar sig något fruktansvärt.
Det är nu vi bör ha nått insikten "lagom" om uppgiften. Att vi ska börja vid en änddator och betrakta den som en rot i ett träd verkar fortfarande som en bra idé, men hur ska vi sedan gå tillväga. Lösningen är faktiskt tämligen elegant, då man kan betrakta subträd till träd som egna träd. Den går till på så sätt att vi börjar att dra kabeln vid vår änddator och sedan räknar vi hur många angränsande datorer som gynnas av att kabeln finns vid datorn. Och det eleganta är att vi nu bara behöver returnera hur många datorer som gynnades av att vi drog kabeln genom denna dator + hur många datorer som gynnas av att vi drar kabeln genom datorn i anslutning till denna. Finns det fler än en dator i anslutning, så väljer vi givetvis den vidare-dragning av kabeln som gynnar flest datorer. (Observera att detta är en rekursiv definition som gäller för varje dator i nätverket.) Dock får man inte glömma när man räknar hur många datorer som gynnas av att kabeln finns vid en dator att utelämna datorn man kom ifrån (eftersom den redan har räknats). Observera också att vi inte räknar att en dator gynnas av kabeln när den dras igenom den, eftersom vi redan då har räknat datorn när kabeln fanns vid föregående dator. (Detta gör att vi inte får glömma att räkna med änddatorn vid vilken vi började dra kabeln.)
(Givetvis kan man göra lite optimeringar genom att spara undan redan kända resultat, men det är onödigt och ger bara marginell förbättring. Jag här ändå med en sådan optimering, som jag dock kommenterat bort, bara för att visa hur.)
import java.util.*;
import java.io.*;
public class Network
{
//Orka fånga exceptions. Vi är lata och säkra på vår sak.
public static void main(String [] klein) throws FileNotFoundException
{
//Vi ska läsa av filen network.dat i mappen/katalogen data.
Scanner scan = new Scanner(new File("data\\network.dat"));
//Antalet datorer.
int nr = scan.nextInt();
//Sparar vilka änddatorer som finns i nätverket.
HashSet <Computer> ends = new HashSet <Computer> ();
//Referenser till alla datorer i nätverket.
Computer [] computers = new Computer [nr+1];
//Läser in alla datorer och dess förbindelser.
for(int i = 0; i<nr-1; i++)
{
//Läser in numret för de två datorerna.
int c1 = scan.nextInt();
int c2 = scan.nextInt();
//Om datorn inte fanns så skapar vi den och lägger
//till den som en änddator.
if(computers[c1]==null)
{
computers[c1] = new Computer(c1);
ends.add(computers[c1]);
}
else //Fanns den redan, så var den ingen änddator.
{
ends.remove(computers[c1]);
}
//Samma sak fast för andra datorn.
if(computers[c2]==null)
{
computers[c2] = new Computer(c2);
ends.add(computers[c2]);
}
else
{
ends.remove(computers[c2]);
}
//Kopplar samman datorerna.
computers[c1].add(computers[c2]);
computers[c2].add(computers[c1]);
}
//Maximalt antal datorer som kan utnyttja fiberkabeln.
int max = 0;
//Går igenom ändpunkterna.
for(Computer com : ends)
{
//Kollar hur många datorer man max kan gynna med fiberkabeln
//om man börjar dra den från denna änddator. +1 för att
//änddatorn själv ska räknas in i antalet. (Sedan kommer vi ju
//ifrån en dator som inte finns, vilken jag valt att kalla 0.)
int tmp = 1 + com.possible(0);
//Kollar om detta bör vara vårt nya största resultat.
if(tmp>max) max = tmp;
}
//Skriver ut svaret.
System.out.println("Maximalt antal datorer: " + max);
}
//En klass som beskriver en dator i nätverket.
private static class Computer
{
//Datorns id.
int id;
//Datorerna datorn är sammankopplad med.
List <Computer> connected;
/* Optimering: HashMap <Integer, Integer> calculated; */
//Skapar en dator med det givna id-nummer.
public Computer(int id)
{
this.id = id;
connected = new LinkedList <Computer> ();
/* calculated = new HashMap <Integer, Integer> (); */
}
//Kopplar samman den här datorn med den givna datorn.
public void add(Computer comp)
{
connected.add(comp);
}
//Returnerar hur många datorer man kan gynna med fiberkabeln
//om man drar den genom denna dator givet att man tidigare kom
//från datorn med id 'from'.
public int possible(int from)
{
/*Integer calc = calculated.get(from);
if(calc!=null) return calc;*/
//Största antalet datorer som kan gynnas genom att fortsätta
//dra kabeln via någon av datorerna kopplad till denna.
int max = 0;
//Hur många datorer som står i direkt anslutning till denna.
//Dvs datorer som gynnas av kabeln, men nödvändigtvis inte står
//i direkt sammanslutning med den.
int nextTo = 0;
//Går igenom datorerna i anslutning till denna.
for(Computer com : connected)
{
//Datorn vi kom från ska inte behandlas.
if(com.id!=from)
{
//Ytterliggare en dator står i anslutning.
nextTo++;
//Hur många datorer som skulle kunna gynnas av att vi
//fortsätter att dra kabeln till denna dator i anslutning.
//Då givetvis exkluderat datorn själv eftersom den redan
//gynnas av att kabeln finns vid denna dator.
int tmp = com.possible(id);
//Kollar om detta var det bästa valet.
if(tmp>max) max = tmp;
}
}
/* calculated.put(from, max+nextTo); */
//Returnerar bästa valet där kabeln kan fortsättas att dra + antalet
//datorer som gynnats av att kabeln dragits genom denna dator.
return max+nextTo;
}
//Följande två nedanstående metoder är bara överlagrade för
//att vi ska kunna stoppa klassen i en hashtabell.
public int hashCode()
{
return id;
}
public boolean equals(Object ob)
{
Computer comp = (Computer)ob;
return (id==comp.id);
}
}
}
Lösning i Haskell. För att programmet ska klara av tidsgränsen för testfall 4 och 5, måste det kompileras ned till en binärfil. (Testar man bara programmet i GHCI, så tar det ca 13 sek för testfall 4, medan motsvarande testfall går på 2-3 sek om man kompilerat med GHC.)
-- Nätvärk
module Main where
import IO
import Data.List
import Data.Ord (comparing)
import Data.Map (Map, lookup, fromList)
type ComID = Int
type Network = Map ComID [ComID]
main = do {
ih <- openFile "network.dat" ReadMode;
content <- hGetContents ih;
edges <- return $ concat $ map ((\[a,b] -> [(a,b),(b,a)]).(map read).words) $ tail $ lines content;
coms <- return $ map (foldr (\(b,a) (_,c) -> (b,a:c)) (0, [])) $
groupBy (\a b -> (fst a)==(fst b)) $ sortBy (comparing fst) edges;
network <- return $ fromList coms;
ends <- return [a | (a,b) <- coms, length b == 1];
putStrLn $ "Maximalt antal datorer: " ++ (show $ maximum (map (isPossible network 0) ends) + 2);
hClose(ih)
}
isPossible :: Network -> ComID -> ComID -> Int
isPossible set from a = if (length b == 1 && from/=0) then 0 else best + (length b - 1)
where
Just b = Data.Map.lookup a set
best = maximum (map (isPossible set a) $ delete from b)