En primer lugar, no es posible encontrar todas las rutas posibles rápidamente, simplemente porque hay demasiadas. Si le doy una cuadrícula de todos los ceros y también suma = 0, cada una de las [matemáticas] {2n-2 \ elegir n-1} [/ matemáticas] las posibles rutas serán válidas, y ese número es exponencial en [matemáticas] n [/ matemáticas]. Entonces, cambiemos la pregunta: a partir de ahora, solo intentaremos contar todas las rutas válidas.
Si los números en su cuadrícula son enteros pequeños no negativos (por ejemplo, de 0 a [matemática] x [/ matemática]), el problema tiene una solución de tiempo pseudopolinomial: podemos usar la programación dinámica para responder todas las preguntas de la forma “¿Qué es la cantidad de rutas válidas que van de (1,1) a (a, b) y tienen la suma c? ”Esta solución se ejecutará en [matemática] O (n ^ 3x) [/ matemática], ya que hay [matemática ] n ^ 2 [/ math] celdas y cada suma parcial es como máximo [math] (2n-1) x [/ math].
En general, este problema es NP-hard. Por ejemplo, podemos reducir la PARTICIÓN a este problema. Dada una instancia [math] (a_1, \ dots, a_n) [/ math] de PARTITION, tome una cuadrícula [math] (n + 2) \ times (n + 2) [/ math], complétela con ceros, luego escriba los números [matemática] a_1, \ puntos, a_n [/ matemática] en la diagonal principal (excepto las esquinas). Ahora, puede resolver la instancia original de PARTITION preguntando si hay al menos una ruta válida con una suma igual a [math] (\ sum a_i) / 2 [/ math].
- ¿Qué debo hacer en mis vacaciones de verano, dado que soy estudiante de informática (1er año)?
- ¿Hay algún proyecto de aprendizaje automático de finanzas que pueda ejercer con Python?
- ¿Qué es un algoritmo numérico simpléctico?
- Una computadora pequeña tiene 4 marcos de página. Un proceso hace la siguiente lista de referencias de página; 1,2,3,4,1,5,2,3,1,2. ¿Cuántas fallas de página ocurren usando los siguientes algoritmos de reemplazo de página?
- ¿Cuál es un buen algoritmo para priorizar mensajes DENTRO de su bandeja de entrada?
