Éste de hoy es el quinto y último artículo de esta serie sobre el algoritmo de Quine-McClusky.
En el anterior artículo de esta serie sobre minimización de funciones lógicas, el cuarto, dedicado a definir el Paso 7 del algoritmo, describí cómo son las alternativas que se citan habitualmente en la literatura sobre Quine-McClusky, sobre todo el método de Petrik, que procuré definir con la máxima precisión debido a que, aunque es sencillo de implementar, no es tarea tan sencilla comprender en qué se basa y cómo funciona.
En este quinto y definitivo artículo describiré una alternativa viable y muy interesante a dicho método de Petrik, una alternativa que proviene de un área distinta de la informática, pero perfectamente aplicable a nuestro problema de minimizar expresiones lógicas.
Aquí podéis encontrar el PDF del quinto y último artículo.
Y con él acaba la serie. Yo no alcanzo para llegar más allá.
Espero que toda la información que he vertido en estos artículos os haya sido de utilidad y que, quizás, os haya picado el gusanillo de mirar con otros ojos a algoritmos que están establecidos en nuestra profesión como si fueran el Santo Grial, pero que, quién sabe, quizás sean susceptibles de mejorarse, como hemos visto que le ocurre al venerable algoritmo de Quine-McClusky.
Disfrutad de la vida mientras podáis.
The Minimización de Funciones Lógicas. El algoritmo de Quine–McClusky explicado y mejorado-V by , unless otherwise expressly stated, is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 2.5 Spain License.
{ 2 } Comentarios
Hola Macluskey,
En el artículo dices: “La constatación de que ambos problemas son exactamente el mismo problema y que, por tanto, cualquier técnica utilizada en uno de ellos es aplicable directamente a la resolución del otro no la he visto reflejada en ningún sitio en la Red, donde ambos problemas, la minimización de expresiones lógicas y la cobertura de conjuntos, viven plácidas vidas separadas. No digo que sea yo el primero en darse cuenta de la igualdad de ambos problemas, mucho me extrañaría tal cosa; lo que digo es que no he encontrado nada en la Red acerca de esta igualdad.?”
Solo como apunte. Como indica el artículo sobre el método de Quine–McCluskey en la Wikipedia en inglés, la correspondencia se conoce desde que W. Masek desmotró en 1978 en su máster tesis, “Some NP-complete set covering problems”, que el problema de encontrar un expresión mínima en suma de productos partiendo de la tabla de verdad totalmente especificada es NP-completo. Puede que incluso antes, pero seguro que al menos desde entonces.
Un saludo.
Gracias, Masek, por tu comentario.
Como digo en el documento, estoy prácticamente seguro de que algo tan evidente como que el “Prime Implicant Chart” cargado en el Paso 4 del algoritmo QM es exactamente el mismo que se cargaría en el Problema de cobertura debe haber sido “descubierto” hace muchos años.
Lo que en realidad no he encontrado es, por ejemplo, que el Set Cover Problem se puede resolver con el método de Petrick, ni tampoco que la tabla de cobertura de implicantes primos se puede resolver con el Voraz.
Y hablando del método de Petrick, he encontrado diferentes artículos, incluso algún video, explicando el artificio booleano en que se basa, pero ningú algoritmo en sí. Nuevamente no digo yo que no exista, debe de hacerlo, sólo que yo no lo he encontrado, así que lo he tenido que parir ex novo. Seguro que estoy repitiendo el trabajo que alguien ha hecho hace años, pero al menos creo que he conseguido un algoritmo para el método de Petrick que es bastante eficaz.
Y lo mismo puedo decir del Greedy; conseguir una modificación que obtiene la función mínima en más del 99% de casos para tamaños de forma canónica de hasta 256 bits en tiempo polinómico puede resultar muy útil.
Seguro, seguro que todas las mejoras que yo he encontrado han sido ya descubiertas hace mucho tiempo. Mi principal objetivo al publicar estos artículos es poner todos estos “hallazgos” juntos en un solo documento, que compendia estos cinco y que publicaré uno de estos días. Por si a alguien le sirve en el futuro.
Escribe un comentario