performance - resueltos - Reduciendo la complejidad del tiempo de este algoritmo.

ejemplos de complejidad computacional

Question

Estoy jugando un juego que tiene un componente de forja de armas, en el que combinas dos armas para obtener una nueva. El gran número de combinaciones de armas (consulte "6.1. Tablas de combinación de cuchillas" en http://www.gamefaqs.com/ps/914326-vagrant-story/faqs/8485 ) hace que sea difícil descubrir qué es lo que finalmente puede crear de sus armas actuales a través de repetidas falsificaciones, así que intenté escribir un programa que hiciera esto por mí. Le doy una lista de las armas que tengo actualmente, tales como:

• francisca
• tabarzin
• kris

y me da la lista de todas las armas que puedo forjar:

• maza de pelota
• chamkaq
• puñal
• francisca
• media luna grande
• cuchillo de lanzar

El problema es que estoy usando un algoritmo de fuerza bruta que se escala extremadamente mal; se tarda aproximadamente 15 segundos en calcular todas las armas posibles para siete armas iniciales y unos minutos para calcular ocho armas iniciales. Me gustaría poder calcular hasta 64 armas (el máximo que puedes tener de una vez), pero no creo que viva lo suficiente como para ver los resultados.

function find_possible_weapons(source_weapons)
{
    for (i in source_weapons)
    {
        for (j in source_weapons)
        {
            if (i != j)
            {
                result_weapon = combine_weapons(source_weapons[i], source_weapons[j]);

                new_weapons = array();
                new_weapons.add(result_weapon);
                for (k in source_weapons)
                {
                    if (k != i && k != j)
                        new_weapons.add(source_weapons[k]);
                }
                find_possible_weapons(new_weapons);
            }
        }
    }
}

En inglés: intento cada combinación de dos armas de mi lista de armas de origen. Para cada una de esas combinaciones, creo una nueva lista de todas las armas que tendría después de esa combinación (es decir, el arma recién combinada más todas las armas de origen excepto las dos que combiné), y luego repito estas Pasos para la nueva lista.

¿Hay una mejor manera de hacer esto?

Tenga en cuenta que combinar armas en el orden inverso puede cambiar el resultado (Rapier + Firangi = Espada corta, pero Firangi + Rapier = Spatha), por lo que no puedo omitir esas inversiones en el bucle j .

Edición: aquí hay un desglose del ejemplo de prueba que di anteriormente, para mostrar lo que está haciendo el algoritmo. Una línea entre paréntesis muestra el resultado de una combinación, y la siguiente línea es la nueva lista de armas que se crea como resultado:

francisca,tabarzin,kris
[francisca + tabarzin = chamkaq]
    chamkaq,kris
    [chamkaq + kris = large crescent]
        large crescent
    [kris + chamkaq = large crescent]
        large crescent
[francisca + kris = dirk]
    dirk,tabarzin
    [dirk + tabarzin = francisca]
        francisca
    [tabarzin + dirk = francisca]
        francisca
[tabarzin + francisca = chamkaq]
    chamkaq,kris
    [chamkaq + kris = large crescent]
        large crescent
    [kris + chamkaq = large crescent]
        large crescent
[tabarzin + kris = throwing knife]
    throwing knife,francisca
    [throwing knife + francisca = ball mace]
        ball mace
    [francisca + throwing knife = ball mace]
        ball mace
[kris + francisca = dirk]
    dirk,tabarzin
    [dirk + tabarzin = francisca]
        francisca
    [tabarzin + dirk = francisca]
        francisca
[kris + tabarzin = throwing knife]
    throwing knife,francisca
    [throwing knife + francisca = ball mace]
        ball mace
    [francisca + throwing knife = ball mace]
        ball mace

Además, tenga en cuenta que los elementos duplicados en una lista de armas son importantes y no se pueden eliminar. Por ejemplo, si agrego un segundo kris a mi lista de armas iniciales para tener la siguiente lista:

• francisca
• tabarzin
• kris
• kris

Entonces puedo forjar los siguientes artículos:

• maza de pelota
• hacha de batalla
• cuchillo de batalla
• chamkaq
• puñal
• francisca
• kris
• kudi
• media luna grande
• Scramasax
• cuchillo de lanzar

La adición de un kris duplicado me permitió forjar cuatro nuevos elementos que antes no podía. También aumentó el número total de pruebas de forja a 252 para una lista de cuatro elementos, en comparación con 27 para la lista de tres elementos.

Edit: Tengo la sensación de que resolver esto requeriría más conocimientos de matemática e informática que los que tengo, por lo que voy a renunciar a ello. Parecía un problema bastante simple al principio, pero luego, también lo hace el Vendedor Viajero. Estoy aceptando la respuesta de David Eisenstat ya que la sugerencia de recordar y omitir listas de elementos duplicados hizo una gran diferencia en el tiempo de ejecución y parece que sería aplicable a muchos problemas similares.

Answer 1

Comience por memoizing la solución de fuerza bruta, es decir, ordenar las source_weapons , hacer que se pueda cambiar (por ejemplo, convertir a una cadena uniendo con comas), y buscarla en un mapa de pares de entrada / salida. Si no está allí, realice el cálculo normalmente y agregue el resultado al mapa. Esto a menudo resulta en grandes victorias por poco esfuerzo.

Alternativamente, podrías hacer una búsqueda hacia atrás. Dado un conjunto múltiple de armas, forme predecesores reemplazando una de las armas con dos armas que la forjan, de todas las formas posibles. Comenzando con la lista de singleton que consiste en el multiset de singleton que consiste en el arma de la meta, expanda repetidamente la lista con los predecesores de los elementos de la lista y luego elimine los multisets que son superconjuntos de otros. Deténgase cuando llegue a un punto fijo.

Si la programación lineal es una opción, entonces hay formas sistemáticas de eliminar los árboles de búsqueda. En particular, simplifiquemos el problema (i) permitiendo un suministro infinito de "catalizadores" (¿quizás no sea necesario aquí?) (Ii) permitiendo el forjado "fraccional", por ejemplo, si X + Y => Z, entonces 0.5 X + 0.5 Y => 0.5 Z. Luego hay una formulación LP de la siguiente manera. Para todos i + j => k (i y j forge k), la variable x_{ijk} es el número de veces que se realiza este forge.

minimize sum_{i, j => k} x_{ijk} (to prevent wasteful cycles)
for all i:   sum_{j, k: j + k => i} x_{jki}
           - sum_{j, k: j + i => k} x_{jik}
           - sum_{j, k: i + j => k} x_{ijk} >= q_i,
for all i + j => k: x_{ijk} >= 0,

donde q_i es 1 si i es el ítem del objetivo, de lo contrario, menos el número de i inicialmente disponible. Hay solucionadores eficientes para esta versión fácil. Dado que las reacciones son siempre 2 => 1, siempre puede recuperar un programa de falsificación viable para una solución entera. En consecuencia, recomendaría la programación entera para este problema. El siguiente párrafo puede ser de interés.

Sé que enviar un solucionador de LP puede ser inconveniente, por lo que aquí hay una idea que le permitirá prescindir. Este LP es factible si y solo si su dual está acotado. Intuitivamente, el problema dual es asignar un "valor" a cada elemento de forma tal que, sin embargo, la falsificación del valor total de su inventario no aumente. Si el ítem del objetivo se valora más que el inventario disponible, entonces no puede falsificarlo. Puede utilizar cualquier método que se le ocurra para asignar estos valores.

Answer 2

Creo que es poco probable que obtenga una buena respuesta general a esta pregunta porque si existiera un algoritmo eficiente para resolver su problema, entonces también podría resolver los problemas de NP-completo.

Por ejemplo, considere el problema de encontrar el número máximo de filas independientes en una matriz binaria.
Este es un problema conocido de NP-completo (por ejemplo, al mostrar la equivalencia con el problema del conjunto máximo independiente ).

Podemos reducir este problema a su pregunta de la siguiente manera:

Podemos comenzar a sostener un arma para cada columna en la matriz binaria, y luego imaginamos que cada fila describe una forma alternativa de hacer una nueva arma (por ejemplo, un hacha de batalla). Construimos la tabla de traducción de armas de tal manera que para hacer el hacha de batalla usando el método i, necesitamos todas las armas j de modo que M [i, j] sea igual a 1 (esto puede implicar inventar algunas armas adicionales).

Luego construimos una serie de súper armas que se pueden hacer combinando diferentes números de nuestros ejes de batalla.

Por ejemplo, el mega hacha de batalla final puede requerir que se combinen 4 ejes de batalla.

Si somos capaces de encontrar la mejor arma que se puede construir a partir de tus armas iniciales, entonces hemos resuelto el problema de encontrar el número máximo de filas independientes en la matriz binaria original.

Answer 3

Es posible que desee comenzar por crear una matriz de Armas [] [], para mostrar los resultados de forjar cada par. Podría asignar el nombre del arma al índice del eje de la matriz, y la búsqueda de los resultados de una combinación de armas ocurriría en un tiempo constante.

Answer 4

No es un gran ahorro, sin embargo, mirando el documento de origen, hay ocasiones en que la combinación de armas produce la misma arma que la que se combinó. Supongo que no querrás hacer esto ya que terminarás con menos armas.

Por lo tanto, si agregó una verificación para ver si el resultado_weapon era del mismo tipo que una de las entradas, y no siguió adelante y recursivamente llamó a find_possible_weapons (new_weapons), recortaría un poco la búsqueda.

La otra cosa en la que puedo pensar es que no está haciendo un seguimiento del trabajo realizado, por lo que si el retorno de find_possible_weapons (new_weapons) devuelve la misma arma que ya tiene al combinar otras armas, es posible que esté realizando la misma búsqueda. Rama varias veces.

por ejemplo, si tiene a, b, c, d, e, f, g, y si a + b = x, yc + d = x, entonces el algoritmo realizará dos lotes de comparación de x con e, f, y sol. Así que si mantienes un registro de lo que ya has calculado, estarás en un ganador ...

Básicamente, hay que recortar el árbol de búsqueda. Hay muchas técnicas diferentes para hacer esto: se llama búsqueda . Si quieres más consejos, te recomiendo ir al intercambio de pila de informática.

Si aún tiene dificultades, siempre puede comenzar a ponderar elementos / elementos resultantes, y solo concentrarse en hacer el cálculo en objetos de ''alta ganancia'' ...