Vänner till Alien

Designen metod algoritm Branch och band (även känd som Branch och bundna) är en variant av backtracking avsevärt förbättrats och är oftast tillämpas för att lösa frågor eller problem av optimering.

Tekniken att Branch och bundna brukar tolkas som en lösning träd, där varje gren leder till en möjlig lösning på den aktuella tjänsten. Det karakteristiska för denna teknik över tidigare (och har fått sitt namn) är att algoritmen är ansvarig för att upptäcka vad som förgrenar den givna lösningar inte längre bäst, att "beskära" denna gren av trädet och inte fortsätta slösa resurser och processer

Problem

Från följande algoritm för att lösa Ryggsäck 0 / 1 genom förgrening och beskärning, har jag genomfört ett program i C # som löser detta problem med följande strategier:

• FIFO - (First In First Out) först in - först ut
• LIFO - (sist in först ut) sist in först ut. (Pila)
• LC - LIFO - senast i Array First Out. (Utbud av batterier)
• LC - FIFO - Array Först in först ut. (Utbud av lim)

Listan över levande noder (LNV) kommer att bestå av objekt av klass Node, som definieras enligt följande:

Resolution Process

1. Vektorer rangordnas efter vinsten och viktförhållandet B / s.
2. När detta rotnoden genereras och läggas till listan av noder levande.
3. Vid denna punkt kommer in i en slinga som upprepas tills LNV är tom följande:
4. Om noden extraheras löften de största vinsterna som vi hittills studerat (första beskärning) genre sina barn i noden y.
5. För varje barn om vikten i det är> att den högsta vikt som inte behandling (göra ingenting) att för noden klass konstruktorn jag initierade värdet på gränserna på mycket små tal.
6. Annars behandling och kön nod uppskattningar därefter.
7. Kontrollera sedan om den nuvarande situationen är en lösning och i så fall uppdatera nod lösningen.
8. Om ingen lösning se om den övre gränsen för den nod som vi arbetar med är större än eller lika med C att vi (beskärning 2) läggs till LNV annars inte.

Syfte:

Målet är att uppnå den optimala lösningen på ränseln problem med olika strategier och jämför antalet noder som genereras i varje för att se vilket är effektivare när det gäller band.

Förslag till lösning

Detta projekt innehåller koden som löser problemet genom att de fyra tidigare nämnda strategier. Jag har också en rapport med detaljerad beskrivning och en jämförelse med spår av var och en av de strategier, där vi kommer att se på antalet noder beskuren och antalet noder som genereras, vilket möjliggör jämförelser.