Tävlingsprogrammering/Uppgifter/Tivoli

Tivoli

Lisa har kommit till tivolit och har bestämt vilka N attraktioner hon vill åka, hon vill åka varje attraktion en gång. För varje attraktion finns det två stycken anläggningar som är likvärdiga, det finns alltså totalt 2N anläggningar. Givet positionerna för samtliga anläggninar, hjälp Lisa att planera vilka N anläggningar hon ska välja och i vilken ordning för att minimera den sträcka hon måste gå för att ha åkt alla N attraktioner. Hon börjar dessutom vid entrén och ska också sluta där. Entrén är vid origo.

Tivolit i exemplet med origo som ett blått kors och Lisas väg utritad. Den första anläggningen av varje attraktion är färgad rosa och den andra gul.

Indata

Första raden består av heltalet N, antalet attraktioner Lisa vill åka (1 ≤ N ≤ 15). Därefter följer N rader, där den första raden beskriver attraktion nummer 1, den andra raden attraktion nummer 2 o.s.v. Varje rad innehåller fyra heltal: x- och y-koordinat för den första anläggningen av denna attraktion, samt x- och y-koordinat för den andra anläggningen av denna attraktion. Koordinaternas absolutbelopp understiger en miljon.

Utdata

Utdatan ska först bestå av flyttalet hur långt Lisa måste gå, och därefter N rader med två heltal som, varav det första inom 1..N som säger vilken attraktion hon ska gå till och det andra inom 1..2 vilken av anläggningarna. Det första av dessa N rader säger alltså vilken anläggning som hon först går till och den sista raden vilken anläggning hon sist går till. Om det finns flera vägar som ger lika kort sträcka (det finns ju åtminstone alltid två håll att gå) kan du ange vilken som helst av dem. Notera även att det första flyttalet som skrivs ut ska ta till hänsyn även att Lisa måste börja och sluta vid entrén. Det relativa felet ska understiga 10^-5.

Exempel: Indata

3
3 5 1 -1
-2 0 0 4
4 4 0 6

Exempel: Utdata

14.233345
2 2
1 1
3 1

Lösning

En brute force-lösning blir för långsam, för det finns 30!! = 30*28*26*...*4*2 = ~4E16 möjligheter för Lisa att gå sin runda. Faktum är att detta är en variant av det så kallade handelsresandeproblemet, ett klassiskt NP-komplett problem, så det finns ingen polynomisk lösning. Däremot finns det ett trick som kan användas såväl i det klassiska problemet som i denna variant och som gör att man kan klara sådana här hyfsat små indata trots att lösningen är exponentiell.

Det gäller att inse att när Lisa gått runt en stund så behöver hon egentligen bara veta attraktioner hon har varit vid (inte ens vilken anläggning av varje) för att kunna räkna ut kortaste vägen hem som passerar de återstående attraktionerna. Hon skulle då kunna spara resultatet i en tabell, och om hon någon gång råkar vara i en situationen där hon befinner sig på samma plats och har besökt precis samma attraktioner, så är det bara att plocka fram värdet ur tabellen. Fördelen är att antalet värden hon behöver spara (antalet "states" i den dynamiska programmeringen) endast är 30*2¹⁵ = 983040, alltså bara en bråkdel av antalet möjliga rundor. Nackdelen är förstås att med ett större tivoli blir metoden snabbt ohållbar eftersom den också är exponentiell i minnesåtgång.

Det enda återstående problemet är att man även ska skriva ut en optimal väg, men det kan göras genom att man sparar nästa attraktion man ska gå till samtidigt som man sparar det minimala avståndet hem. När algoritmen gått färdigt kan man i lugn och ro följa dessa instruktioner och på så sätt återskapa den optimala vägen.

#include <stdio.h>
#include <math.h>
#define MAXN 15

double dst(double dx, double dy) {return sqrt(dx*dx+dy*dy);}

int N; 
double x[2*MAXN],y[2*MAXN];
double T[2*MAXN][1<<MAXN];
int P[2*MAXN][1<<MAXN];

double MLX(int now, int vis) {    //Vad är kortaste vägen hem om hon är vid now och har besökt attraktionerna enligt bitmasken vis?
  double best=1E9,d,xx,yy;
  int i,j,k,next;
  if (T[now][vis]>=0) return T[now][vis];
  xx=(vis>0)?x[now]:0;
  yy=(vis>0)?y[now]:0;
  if(vis==(1<<N)-1) best=dst(xx,yy);
  else for(i=0;i<N;i++) if(!((vis>>i)&1)) {
      for(j=0;j<2;j++) { 
        k=i*2+j;
        d=dst(xx-x[k],yy-y[k])+MLX(k,vis|(1<<i));
        if(d<best) {
           best=d;
           next=i*2+j;
        }
      }
    }
  T[now][vis]=best;
  P[now][vis]=next;
  return best;
}

int main() {
  int i,j,now,vis;
  scanf("%d", &N);
  for(i=0;i<N;i++) for(j=0;j<2;j++) scanf("%lf %lf", &x[i*2+j],&y[i*2+j]);
  for(i=0;i<2*N;i++) for(j=0;j<(1<<N);j++) T[i][j]=-1;
  printf("%f\n", MLX(0,0));
  now=0; vis=0;
  for(i=0;i<N;i++) {
    j=P[now][vis];
    printf("%d %d\n", j/2+1, j%2+1);
    now=j;
    vis|=(1<<(j/2));
  }
  return 0;
}