Duda resolucion CSP

[Renato Williner]

Buenas noches,
Fisa, queria que me dejes por escrito lo que charlamos esta noche sobre la resolucion que te mostre del ejercicio, porque por lo que entendi lo que estaba ineficiente era la parte que agregaba las restrcciones y lo demas del codigo estaba ok.

Te dejo el codigo porque no me deja mandar archivos, aguardo tu respuesta.

Saludos

from simpleai.search import CspProblem, backtrack

variables = ["mastil", "i1", "i2", "fr"]

valoresFrente = [

    "Nuevo taladro de muestras",

    "Láser para experimentos",

    "Microscopio remoto",

    "Espacio extra para muestras",

]

valoresMastil = [

    "Nuevo taladro de muestras",

    "Nueva cámara panorámica",

    "Láser para experimentos",

    "Antena con mejor alcance"

]

valoresI = [

    "Batería nuclear extra",

    "Nuevo sistema de navegación",

    "Espacio extra para muestras",

    "Antena con mejor alcance"

]

pesos = {

    "Nuevo taladro de muestras": [15],

    "Nueva cámara panorámica": [3],

    "Batería nuclear extra": [10],

    "Láser para experimentos": [5],

    "Microscopio remoto": [3],

    "Nuevo sistema de navegación": [8],

    "Espacio extra para muestras": [5],

    "Antena con mejor alcance": [7],

}

dominios = {

    "mastil": valoresMastil,

    "i1": valoresI,

    "i2": valoresI,

    "fr": valoresFrente,

}

# Tus restricciones corregidas

def todos_distintos(vars, vals):

    if len(set(vals)) < 4:

        return False

    return True

def no_250(vars, vals):

    pesoT = 0

    for val in vals:

        pesoT += pesos[val][0]

    if pesoT > 25:

        return False

    return True

def antena_vs_bateria(vars, vals):

    bateria = False

    antena = False

    for val in vals:

        if val == "Batería nuclear extra":

            bateria = True

        if val == "Antena con mejor alcance":

            antena = True

    if bateria and antena:

        return False

    return True

def laser_y_bateria(vars, vals):

    laser = False

    bateria = False

    for val in vals:

        if val == "Láser para experimentos":

            laser = True

        if val == "Batería nuclear extra":

            bateria = True

    if laser and not bateria:

        return False

    return True

def ciencia(vars, vals):

    for val in vals:

        if val in ["Nuevo taladro de muestras", "Láser para experimentos", "Espacio extra para muestras", "Microscopio remoto"]:

            return True

    return False

def taladro_vs_microscopio(vars, vals):

    tiene_taladro = False

    tiene_microscopio = False

    for val in vals:

        if val == "Nuevo taladro de muestras":

            tiene_taladro = True

        if val == "Microscopio remoto":

            tiene_microscopio = True

    if tiene_taladro and tiene_microscopio:

        return False

    return True

restricciones = [

    (variables, todos_distintos),

    (variables, no_250),

    (variables, antena_vs_bateria),

    (variables, laser_y_bateria),

    (variables, ciencia),

    (variables, taladro_vs_microscopio),

]

problema = CspProblem(variables, dominios, restricciones)

solucion = backtrack(problema)

print("\n=== SOLUCIÓN ENCONTRADA ===")

if solucion:

    for slot, mejora in solucion.items():

        print(f"{slot}: {mejora}")

else:

    print("No se encontró una solución válida.")

[fisa]

Buenas! En clases lo más importante que charlamos es que tenés varias restricciones hechas como restricciones únicas que abarcan a todas las variables, cuando eso es extremadamente ineficiente (fuerza a probar millones de combinaciones inválidas). En vez tenés que hacerlas como muchas restricciones que involucran a menos variables.

Por ejemplo: 

- el "all diff" que estás haciendo no está bien que sea una sola restricción involucrando a todas las variables. En vez hay que hacerla como un conjunto de restricciones binarias para todos los pares posibles de variables.

- lo mismo pasa con las restricciones de antena_vs_bateria y taladro_vs_microscopio. Como una sola restricción con todas las variables, no está bien. En vez hay que armarlas como restricciones binarias para pares de variables (y no hace falta que sean todos los pares, sino los pares donde podrían llegar a estar esos aparatos).

No está 100% mal, pero te resta bastante hacerlas de esa forma porque en la práctica intentar correr un problema planteado así en vez de con restricciones de menos variables, hace que demore miles o millones de veces más tiempo. Esto solo puede hacer la diferencia entre encontrar solución en 1 segundo, vs 1 mes.

Similar a eso, hay mejoras que se pueden hacer. Por ejemplo, la restriccón de peso total se puede pensar para todos los conjuntos de 2, 3, y 4 variables posibles, ya que si ya hay 3 variables asignadas y se pasan del peso total, no hay que esperar a asignar la cuarta para saber que ya no puede tener solución por esa rama de posibilidades.

Un detalle menor: no hace falta que los pesos sean listas.

Finalmente, un detalle que puede hacer que no funcione: estás usando la misma lista en el dominio de más de una variable. Por un detalle de implementación de SimpleAI, eso no hay que hacerlo. A futuro voy a sacar un release que haga que no importe, pero mientras tanto, cambiate esto:

dominios = {
    ...
    "i1": valoresI,
    "i2": valoresI,
    ...

Por esto:

dominios = {
    ...
    "i1": valoresI.copy(),
    "i2": valoresI.copy(),
    ...

Saludos!

--
You received this message because you are subscribed to the Google Groups "UCSE IA" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ucse-ia+u...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/ucse-ia/3ca81778-21bc-465c-ad18-492d5c94f2can%40googlegroups.com.

--

fisa  -  Juan Pedro Fisanotti