c# - ejemplo - Mochila-algoritmo de fuerza bruta

algoritmo de fuerza bruta c++

Question

He encontrado este código para resolver el problema de la mochila utilizando un mecanismo de fuerza bruta (esto es principalmente para el aprendizaje, por lo que no es necesario señalar la dinámica es más eficiente). Tengo el código para trabajar, y entiendo la mayor parte. MÁS. Aquí está la pregunta:

He notado esos dos condicionales, que no tengo idea de cómo funcionan y por qué están en el código. Sé que son vitales, ya que cualquier cambio que hice causó que el algoritmo produjera resultados incorrectos:

// if bit not included then skip
if (((i >> j) & 1) != 1) continue;

// if bit match then add
if (((bestPosition >> j) & 1) == 1)
{
    include.Add(Items[j]);
}

Aquí está toda la clase, y la forma en que lo estoy llamando desde main:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace KnapSack2
{
    class BruteForce
    {
        public double Capacity { get; set; }
        public Item[] Items { get; set; }

        public Data Run()
        {
            int bestValue = 0;
            int bestPosition = 0;
            int size = Items.Length;

            var permutations = (long)Math.Pow(2,size);

            for (int i = 0; i<permutations; i++)
            {
                int total = 0;
                int weight = 0;
                for (int j = 0; j<size; j++)
                {
                    //jeżeli bit "not included" to omin"
                    if(((i>>j)&1)!=1)
                        continue;
                    total += Items[j].v;
                    weight += Items[j].w;
                }
                if (weight <= Capacity && total>bestValue)
                {
                    bestPosition = i;
                    bestValue = total;
                }
            }
            var include = new List<Item>();
            for (int j = 0; j<size; j++)
            {
                // jeżeli bit pasuje, wtedy dodaj
                if (((bestPosition>>j) & 1)==1)
                    include.Add(Items[j]);
            }
            return new Data { BestValue = bestValue, Include = include };

        }//End of Run


    }
}

Llamando a la voz principal

var ks = new BruteForce
{
    Capacity = MaxWeight,
    Items = items.ToArray()
};

Data result = ks.Run();

La clase de artículo es solo un objeto simple que contiene valor, peso e ID

Answer 1

Al parecer, las partes del código en cuestión son comprobaciones para un determinado bit que se establece, como lo indican los comentarios. La condición

((i >> j) & 1) != 1

es verdadero si y solo si el bit j de i es cero; la condición

((bestPosition >> j) & 1) == 1

es cierto si y solo si el bit j de la mejor bestPosition es uno. Con respecto a la imagen más grande, al parecer, la implementación usa int para modelar un conjunto de elementos, donde el bit j se establece si, y solo si, el elemento j -th se incluye en el conjunto; En consecuencia, las pruebas de membresía se pueden realizar mediante comprobaciones de bits. La implementación enumera todos los subconjuntos de los elementos (usando int para representarlos) para realizar una búsqueda exhaustiva.

Tenga en cuenta que la implementación de Delphi para conjuntos utiliza el mismo enfoque, pero oculta la indexación de bits del código del cliente.

Answer 2

Este & es el bitwise-AND

El operador bit a bit Y compara cada bit de su primer operando con el bit correspondiente de su segundo operando. Si ambos bits son 1, el bit de resultado correspondiente se establece en 1. De lo contrario, el bit de resultado correspondiente se establece en 0.

Si bien este >> es el operador de cambio a la derecha

El operador de desplazamiento a la derecha (>>) desplaza su primer operando a la derecha por el número de bits especificado por su segundo operando.

Dicho esto, tomemos la siguiente expresión

if (((i >> j) & 1) != 1) continue;

y tratar de entenderlo.

Inicialmente, este i >> j desplazará a la derecha los bits de las posiciones i by j .

Por ejemplo, vamos a tener la siguiente asignación:

int number = 5;

La representación binaria de number es:

0000 0000 0000 0000 0000 0000 0000 0101

Si definimos un nuevo entero como:

int shiftNumbersBitByOne = a >> 1;

Entonces la representación binaria de shiftNumbersBitByOne sería:

0000 0000 0000 0000 0000 0000 0000 0010

Luego, en el resultado de esta operación y 1, aplicamos el operador AND a nivel de bits.

¿Qué hace exactamente este operador?

A pesar de que la definición es clara, un ejemplo lo hará más claro.

Dejemos que tengamos los números binarios a y b , entonces el resultado de a&b es el siguiente:

a =     0001 0100 1010 0001 1000 1010 1101 0011
b =     0010 1100 1111 0111 0011 1010 1011 0111
a & b = 0000 0100 1010 0001 0000 1010 1001 0011

Dicho esto, en esta operación (i >> j) & 1 aplicamos el operador AND a nivel de bit entre el resultado de i >> j y la representación binaria de 1

0000 0000 0000 0000 0000 0000 0000 0001

Cuando el resultado de (i >> j) & 1 sería 1?

Esto sucederá si y solo si el último dígito de i >> j es 1.

Actualizar

Anteriormente abordamos la parte cómo : no tengo idea de cómo funcionan . Ahora abordaremos la parte de por qué , por qué están en el código .

Vamos a definir nuestro problema, el problema de la mochila. Segun wikipedia

El problema de mochila o de mochila es un problema en la optimización combinatoria: dado un conjunto de artículos, cada uno con una masa y un valor, determina el número de cada artículo para incluir en una colección de modo que el peso total sea menor o igual a un Límite dado y el valor total es lo más grande posible.

De acuerdo con lo anterior, es sencillo que

// This is the total weight limit.
public double Capacity { get; set; }

y

// This is an array with all the given items.
public Item[] Items { get; set; }

Además, según su código, podemos deducir que cada elemento tiene un valor y una ponderación a los que se puede acceder como item.v y item.w respectivamente. Le sugiero que cambie el nombre a valor y peso respectivamente, para que su código sea más significativo.

Al parecer, este int size = Items.Length; Es el número de los artículos disponibles.

El punto de por qué parte comienza aquí :

var permutations = (long)Math.Pow(2,size);

¿Qué son las permutations ? ¿Qué representan las permutations ?

Antes de responder a esta pregunta, pensemos en cómo podemos representar qué elementos de la colección de artículos se utilizarán en la solución final. Sostengo que podemos representarlo con un número de n bits siempre que tengamos n elementos. ¿Cómo es eso posible? Si cada bit en el número de n bits se refiere a uno de los n-elementos, es bastante evidente que podemos hacerlo. El valor del n- ésimo bit sería 0, si el n- ésimo elemento no se incluye en la solución final. Si bien su valor sería 1, si se incluye.

Dicho esto es bastante claro lo que representan las permutaciones. Representa todas las combinaciones posibles de los elementos en la solución final . Esto está claro, porque cada bit puede tener 2 valores, ya sea 0 o 1. Dado que tenemos n bits, el número de combinaciones posibles es 2 ^ n.

En realidad, por esta razón, este algoritmo es un algoritmo de fuerza bruta (hacemos una búsqueda exhaustiva). Visitamos todas las combinaciones posibles para encontrar la mejor. En el siguiente bucle:

for (int i = 0; i<permutations; i++)
{ 
    // ...
}

Recorres todas las combinaciones posibles.

Luego, para cada combinación, recorres la colección de elementos:

for (int j = 0; j < size; j++)
{
    // Here you check if the item in position j
    // is included in the current combination.
    // If it is not, you go to the next value of the loop''s variable
    // and you make the same check.
    if(((i>>j)&1)!=1)
        continue;

    // The j-th item is included in the current combination. 
    // Hence we add it''s
    // value to the total value accumulator and it''s weight to 
    // the total weight accumulator.
    total += Items[j].v;
    weight += Items[j].w;
}

Ahora, si el weight es menor que el valor límite y el valor total es mayor que el mejor valor total actual, escogemos esta combinación como la mejor actual:

bestPosition = i;
bestValue = total;

Al final, habiendo recorrido todas las combinaciones disponibles, tendremos la mejor.

Habiendo encontrado la mejor combinación, tenemos que recorrer los elementos para ver cuáles de ellos están incluidos en esta combinación.

// The include is a list that will hold the items of the best combination.
var include = new List<Item>();

// We loop through all the available items
for (int j = 0; j<size; j++)
{
    // If the items is included in the best combination,
    // add this item to the include list.
    if (((bestPosition>>j) & 1)==1)
        include.Add(Items[j]);
}