Brute Force

Brute force

Er nyttig når man ikke kommer på bedre løsninger. Som regel består det i å prøve alle mulige løsninger (rekkefølger, subset osv.).

Alle permutasjoner

Dersom løsningen man leter etter er en rekkefølge (permutasjon), vil det å prøve alle ta O(N!) tid. 10! er allerede 3.6 millioner, så dette blir fort upraktisk rundt N = 13 selv på raske datamaskiner.

Det mest berømte problemet som går ut på å finne en rekkefølge er “The Travelling Salesman Problem” (TSP). Her skal en besøke en gitt liste med steder, og målet er å finne den rekkefølgen som minimerer den totale reiselengden.

void tspBruteForce(int currNode, double currLen, int currStep) {
  // Continue only if this route is promising:
  if (currLen + dist[currNode][0] < bestTrip) {
    // If this is the last node:
    if (currStep == numSteps) {
      currLen += dur[currNode][0];
      currPath[currStep] = 0;
      bestTrip = currLen;
      for (int i = 0; i <= numSteps; ++i) {
        bestPath[i] = currPath[i];
      }
    } else {
      // Try all possible routes:
      for (int i = 1; i < numSteps; ++i) { 
        if (!visited[i]) {
          visited[i] = true;
          currPath[currStep] = i; 
          tspBruteForce(i, currLen+dist[currNode][i], currStep+1);
          visited[i] = false; 
        } 
      } 
    } 
  } 
}

Fordelen med en rekursiv funksjon fremfor STL next_permutation er at man har mulighet til å avbryte søket tidlig om rekkefølgen man holder på med er håpløs (og det er de ofte i TSP). Sett at man allerede har funnet en løsning med lengde 1000. Om man holder på å evaluere enda en rekkefølge men kun har besøkt 50% av stedene og allerede har brukt en lengde som er >= 1000, kan man trygt unnlate å teste alle permutasjoner som starter med denne rekkefølgen. (tspBruteForce gjør en lignende avgrensing, som antar at trekantulikheten dist[A][C] <= dist[A][B] + dist[B][C] holder – raskeste vei hjem er direkte hjem, ikke via andre steder).

Rekursiv testing av alle rekkefølger er temmelig vanlig som en løsning som gir noen poeng på mange oppgaver, så om man ikke føler seg trygg på det er det verdt det å sette seg ned og mestre dette.

Alle subset

En enkel metode for å teste alle subset av N elementer er å telle opp til 2^N. Etthvert subset av N elementer kan representeres ved hvilke bits som er satt i et tall mellom 0 og 2^N. F.eks tallet 5 = 101 (base 2) og det kan man tolke som at element nummer 0 er i settet, element 1 er det ikke, og element 2 er i settet.

Hvordan finne ut om bit nummer i er satt i et heltall x i C++:

if (x & (1 << i))

Hvordan sette bit nummer i til 1 (strengt tatt ikke nødvendig for å teste alle subset, men ofte brukt om man skal bruke bitmasks til andre ting, f.eks bygge opp en løsning nedenfra og opp):

x = x | (1 << i)

Hvordan sette bit nummer i til 0 (som over, ikke så nødvendig for BF, men kjekt i andre tilfeller):

x = x & ~(1 << i)

Ta f.eks en oppgave der man har kasser med forskjellig vekt, og vil laste en lastebil med en bestemt maksgrense for vekt slik at man har lastet mest mulig vekt på lastebilen. Da kan man prøve alle subset av kassene med denne metoden:

int best = 0;
for (int bitmask = 0; bitmask < (1 << n); ++bitmask) {
  int tot = 0;
  for (int i = 0; i < n; ++i) {
    if (bitmask & (1 << i)) {
      tot += weight[i];
    }
  }
  if (tot < limit && tot < best) best = tot;
}

Selv om dette ikke er like ille som å prøve alle rekkefølger, tar det fort tid. Kompleksiteten er O(2^N), og det begynner å bli problematisk når N er mellom 20 og 30 avhengig av hvor tungt det er å teste hvert subset.

Pruning

Når grenene blir for lange i hekken eller i treet, klipper vi dem. Dette kalles “pruning”. I algoritmeverdenen brukes pruning også til å unngå å gå for dypt inn i løsninger som er håpløse. Som i eksempelet med Travelling Salesman-problemet, der man kan slutte å evaluere en sti (og alle løsninger som starter med denne stien, når lengden av stien er større enn en løsning vi allerede har funnet). Slik pruning kan i mange tilfeller være forskjellen på en løsning som fungerer helt greit på de tilfellene man er interessert i, og en løsning som bruker år og dag.

Oppgaver

Rush Hour, se siste side i IOI 2005 Newsletter 8.

Vi jobber alltid med 6×6 grid. Første linje i input er antallet biler N. Deretter N linjer med tre heltall, X Y Z L, der X er X-koordinaten (regnet fra øverste venstre hjørne) og Y er Y-koordinaten til bilens øverste venstre hjørne. Z er 0 om bilen er horisontalt plassert, og 1 om bilen er vertikalt plassert. L er bilens lengde og er enten 2 eller 3.

Output er ett heltall, det minste antall trekk som trengs for å flytte bilen ut utgangen (ett skritt ut).

F.eks for tegningen som er i newsletter:

12
2 0 1 2
3 0 0 3
3 1 1 2
0 2 0 2
2 2 1 2
0 3 0 2
3 3 0 2
5 3 1 3
0 4 1 2
1 4 1 2
2 4 0 2
3 5 0 2

Output

50