Tävlingsprogrammering/Uppgifter/Budbilen

Budbilen

Veronica kör budbil mellan N städer, numrerade från 1 till N . Varje morgon får hon en lista över leveranser hon ska göra under dagen. Varje leverans innebär att ett paket ska hämtas i en stad och lämnas i en annan stad. Skriv ett program som, givet denna lista samt en avståndstabell för städerna, räknar ut den minimala sträckan Veronica behöver köra under dagen.

Den första raden i filen budbil.dat innehåller två heltal separerade med blanksteg: antalet städer (2 ≤ N ≤ 8) och antalet leveranser (1 ≤ M ≤ 100). Därefter följer N rader med N heltal på varje rad, separerade med blanksteg. Talen utgör en “avståndstabell” där det i:te talet på den j :te raden, D(i, j ), anger hur långt det är (i kilometer) mellan städerna i och j . Talen i tabellen uppfyller D(i, i) = 0, D(i, j ) = D(j, i) samt D(i, j ) + D(j, k) ≥ D(i, k) (triangelolikheten) och alla avstånd mellan städer ligger i intervallet 1..100. Slutligen följer M rader som vardera beskriver en leverans. Varje rad innehåller två heltal separerade med blanksteg. Det första talet anger staden där paketet ska hämtas och det andra staden där paketet ska lämnas. Veronica måste starta och sluta i stad 1 (även om hon inte ska hämta eller lämna paket där) och har obegränsat med plats i sin bil. Programmet ska skriva ut den minimala sträckan (i kilometer) som hon måste köra för att kunna leverera alla paketen.

Exempel: Filen budbil.dat med innehållet

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

ska ge svaret

Minsta körsträcka: 16 

Kommentar: Det bästa körschemat är 1 → 5 → 2 → 3 → 5 → 1

Lösning

Här finns ingen särskilt smart lösning. Faktum är att specialfallet när det ska levereras paket från stad 1 till var och en av de övriga städerna är det s.k. handelsresandeproblemet, som är ett klassiskt NP-komplett problem, till vilket det bara finns exponentiella lösningar.

Därför gäller det att testa alla möjliga sätt att färdas och detta kan göras på många sätt. Det finns dock några saker man bör tänka på för att inte programmet ska gå för långsamt:

• Man behöver aldrig besöka en stad mer än två gånger.
• Första gången hämtar man alla paket som ska från staden. Sista gången lämnar man alla paket som ska till staden. Man kan förstås lyckas få till det så att första och sista gången är samma gång, d.v.s. att man bara besöker staden en gång.
• Om det inte finns paket att hämta i en stad och man ännu inte har alla paket som ska till staden är det ingen idé att besöka den.
• Stad nummer 1 behöver man aldrig besöka utom vid ruttens start och slut.

Lösningsexempel i C:

#include <stdio.h>

int N,d[20][20],nbrev[20],left[20],brev[20][100],mini;

void MLX(int now, int dist, int nleft) {
  int i,nbrevsav,leftsav;
  if(dist+d[now][0]>=mini) return;    //Kan aldrig bli en bästa lösning
  //Spara tillståndet:
  nbrevsav=nbrev[now];     
  leftsav=left[now];
  //Hämta paketen som ska skickas från now:
  for(i=0;i<nbrev[now];i++) left[brev[now][i]]--;
  nbrev[now]=0;
  //Lämna paketen som ska till now:
  if(left[now]==0) {
    left[now]=-1;
    nleft--;
  }
  if(nleft==0) {   //Om det var sista lämningen så är vi färdiga och har hittat den hittills bästa lösningen...
    mini=dist+d[now][0];     // ... men vi måste tillbaka till 0 också.
  }
  else {    //Annars fortsätter vi
    for(i=1;i<N;i++) if(nbrev[i]>0 || left[i]==0) {   //Välj en stad som vi antingen ska lämna eller hämta paket i
	MLX(i,dist+d[now][i],nleft);  //Rekursera!
      }
  }
  //Vi backtrackar. Återställ tillståndet:
  nbrev[now]=nbrevsav;
  for(i=0;i<nbrev[now];i++) left[brev[now][i]]++;
  left[now]=leftsav;
}

int main(){
  int i,j,nb,from,to,tot;
  scanf("%d %d", &N, &nb);
  for(i=0;i<N;i++) {
    for(j=0;j<N;j++) scanf("%d", &d[i][j]);
    nbrev[i]=0;     //Antal paket som ska hämtas i staden
    left[i]=-1;     //Antal paket som ska till staden och ännu inte är upphämtade (eller -1 om redan levererat)
  }
  tot=0;    //Antal städer dit det ska levereras paket
  for(i=0;i<nb;i++) {
    scanf("%d %d", &from, &to); from--; to--;
    brev[from][nbrev[from]++]=to;
    if(left[to]==-1) {
      left[to]=1;
      if(to!=0) tot++;
    }
    else left[to]++;
  }
  mini=1000000000;
  MLX(0,0,tot);
  printf("Minsta körsträcka: %d\n",mini);
  return 0;
}

Här nedan följer ett lösningsexempel i Java.

import java.util.*;
import java.io.*;

public class Budbil
{
	//Tabell med avståndet mellan vardera stad.
	static int [][] tabell;

	//Alla de olika leveranserna.
	static int [][] paket;

	//Hur många städer vi har.
	static int cities;

	//Hur många leveranser vi har.
	static int deliveries;

	//Kortaste sträckan vi behöver köra.
	static int min = Integer.MAX_VALUE;

	//Vår rekursiva metod som löser problemet.
	/*
	city: Staden vi är i.
	distance: Hur lång sträcka vi kört.
	isPickedUp: Vilka paket vi har hämtat.
	isDelivered: Vilka paket vi har lämnat.
	*/
	public static void rek(int city, int distance, boolean [] isPickedUp, boolean [] isDelivered)
	{
		//Plockar upp alla paket i staden om det finns några.
		pickUp(city, isPickedUp);

		//Lämnar paket till staden om vi har några.
		deliver(city, isPickedUp, isDelivered);

		//Dumt att fortsätta.
		if(distance+tabell[city][1]>=min)
		{
			return;
		}
		else if( isFinished(isDelivered) )
		{ //Om vi är klara så har vi hittat en ny kortaste sträcka.
			//Vi får inte glömma att gå tillbaka till stad 1. Om vi redan är där så är avståndet 0.
			min = distance + tabell[city][1];
			return;
		}

		//Testar att gå till varje stad (om det är smart).
		for(int i = 1; i<=cities; i++)
		{
			/*
			Det kan vara smart att gå till en stad om det finns paket att hämta där,
			eller om vi har paket att lämna och det inte finns några andra paket
			i någon annan stad att hämta till denna stad.
			*/
			if(hasPackages(i, isPickedUp) || (!hasMoreDeliveries(i, isPickedUp) && hasDeliveries(i, isDelivered)))
			{
				//Kopierar vilka paket vi plockat upp.
				boolean [] copy1 = Arrays.copyOfRange(isPickedUp, 0, deliveries);

				//Kopierar vilka paket vi lämnat.
				boolean [] copy2 = Arrays.copyOfRange(isDelivered, 0, deliveries);

				//Går till nämnda stad och gör alla "smarta" drag därifrån.
				rek(i, distance+tabell[city][i], copy1, copy2);
			}
		}
	}

	//Talar om huruvida det finns paket att hämta i staden.
	public static boolean hasPackages(int city, boolean [] isPickedUp)
	{
		for(int i = 0; i<deliveries; i++)
		{
			if(paket[i][0]==city && !isPickedUp[i]) return true;
		}

		return false;
	}

	//Talar om huruvida det finns leveranser som inte blivit levererade till en viss stad.
	public static boolean hasDeliveries(int city, boolean [] isDelivered)
	{
		for(int i = 0; i<deliveries; i++)
		{
			if(paket[i][1]==city && !isDelivered[i]) return true;
		}

		return false;
	}

	//Talar om huruvida det finns leveranser till en viss stad vi inte plockat upp.
	public static boolean hasMoreDeliveries(int city, boolean [] isPickedUp)
	{
		for(int i = 0; i<deliveries; i++)
		{
			if(paket[i][1]==city && !isPickedUp[i]) return true;
		}

		return false;
	}

	//Plockar upp alla leveranser i en viss stad.
	public static void pickUp(int city, boolean [] isPickedUp)
	{
		for(int i = 0; i<deliveries; i++)
		{
			if(paket[i][0]==city) isPickedUp[i] = true;
		}
	}

	//Levererar alla leveranser vi plockat upp till en viss stad.
	public static void deliver(int city, boolean [] isPickedUp, boolean [] isDelivered)
	{
		for(int i = 0; i<deliveries; i++)
		{
			if(paket[i][1]==city && isPickedUp[i]) isDelivered[i] = true;
		}
	}

	//Talar om huruvida alla leveranser är slutförda.
	public static boolean isFinished(boolean [] isDelivered)
	{
		for(int i = 0; i<deliveries; i++)
		{
			if(!isDelivered[i]) return false;
		}

		return true;
	}

	//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 budbil.dat i mappen/katalogen data.
		Scanner scan = new Scanner(new File("data\\budbil.dat"));

		cities = scan.nextInt();
		deliveries = scan.nextInt();

		//Skapar avståndstabell.
		tabell = new int [cities+1][cities+1];

		//Läser in alla värden.
		for(int i = 1; i<=cities; i++)
		{
			for(int j = 1; j<=cities; j++)
			{
				tabell[i][j] = scan.nextInt();
			}
		}

		//Skapar lista över alla leveranser.
		paket = new int [deliveries][2];

		//Läser in alla leveranser.
		for(int i = 0; i<deliveries; i++)
		{
			paket[i][0] = scan.nextInt(); //Var paketet ska hämtas.
			paket[i][1] = scan.nextInt(); //Var paketet ska lämnas.
		}

		//Vilka leveranser vi har lämnat.
		boolean [] isDelivered = new boolean [deliveries];

		//Vilka leverenaser vi har plockat upp.
		boolean [] isPickedUp = new boolean [deliveries];

		//Vi börjar i stad 1, kört 0 km, och varken plockat upp eller lämnat något.
		rek(1, 0, isPickedUp, isDelivered);

		//Skriver ut svaret.
		System.out.println("Minsta körsträcka: " + min);
	}

}