3
주어진 진리표 (일부 텍스트 형식)에서 ROBDD (Reduced Ordered Binary Decision Diagrams)를 작성하는 소프트웨어 패키지 (라이브러리가 아닌 응용 프로그램이 좋음)가 있습니까?진리표에서 ROBDD (reduced Ordered Binary Decision Diagram)를 작성하십시오.
A
답변
1
모든 BDD 라이브러리로 원하는 것을 할 수 있습니다. 물론 코드 조각을 직접 작성해야합니다.
5
당신이 시도 할 수 있습니다 : http://formal.cs.utah.edu:8080/pbl/BDD.php
당신이 가벼운 도구를 찾고 있다면, 나는 종종 함수의 BDD 얼핏하려면이 같은 애플릿을 사용
지금까지 사용한 BDD에 가장 적합한 도구입니다.
1
BDD는 중복 하위 진리를 탐지하는 데 크게 의존하기 때문에 메모리 제약적인 데이터 구조입니다. 찾을 수있는 대부분의 BDD 패키지는 대용량 일반 진리 테이블에 적합하지 않으며 매우 희박하거나 매우 반복적 인 표현에 최적화되어 있습니다.
표준 BDD 패키지를 사용하면 변수에서 작동하는 식을 사용하여 작업 할 수 있습니다. 따라서 진실 표를 반복해야하며 표의 1에 대한 곱의 표현식과 같은 것을 구성해야합니다. 길을가는 동안 대부분의 라이브러리는 메모리 제약 조건에 맞게 변수를 동적으로 재정렬하므로 또 다른 속도가 느려집니다. 약 24 개의 변수를 사용하면 매우 희소 한 진리표가 있더라도이 라이브러리는 현대 시스템에서 쓰레기가되기 시작합니다.
가변 순서가 이미 암시 적으로 정의 된 진리표가 제공된 최종 BDD 노드 만 찾는 경우 외부 라이브러리와 끔찍한 런타임으로 많은 복잡성을 피할 수 있습니다. 일부 유닉스 텍스트 처리 도구를 사용하면됩니다.
BDD에 대한 훌륭한 자료 인 Knuth의 TAOCP v4.1b는 BDD 노드와 그 비 구형 문자열 인 "비들"의 동등성을 보여줍니다. 더 단순한 버전 인 ZDD는 "zeads"와 비슷한 구조를 가지고 있습니다 : 긍정적 인 부분 부분적으로 완전히 진실하지 않은 부분을 말합니다. BDD로 다시 일반화하려면 파이프 라인의 sed + grep를 양수 부분이 0이 아닌 문자열로 유지하는 대신 정사각형 문자열을 필터링하는 프로그램으로 바꿉니다.
는 (한 줄 아스키의 파일 '1과 0의, 마지막에 개행 문자로 제공)를 truthtable의 모든 zeads를 인쇄 변수와 파일 이름의 수를 설정 한 후 다음 명령을 실행하십시오MAX=8; FILENAME="8_vars_truthtable.txt"; for ((ITER=0; ITER<=${MAX}; ITER++)) ; do INTERVAL=$((2 ** ${ITER})); fold -w ${INTERVAL} ${FILENAME} | sed -n '1~2!p' | grep -v "^0*$" | sort -u ; done
- 간단한 :
이 BDD 패키지에 비해 많은 장점을 가지고있다.
- 외부 정렬은 메모리 내 해시 테이블과 달리 스 래싱이 없음을 의미합니다.
- for 루프에서 분기 할 때 라인 버퍼링과 디스크 캐싱을 이해하면 쉽게 병렬화 가능 &을 확장 할 수 있습니다.
- 중간 파일 정렬 작업도 병렬 처리됩니다.
사실 최대 32 개의 변수가있는 truthtables에는 BDD 라이브러리를 사용하는 것이 현실적으로 불가능합니다. 간신히 몇 MB를 사용하여 메모리 시스템에 전혀 과세하지 않습니다. 그러나 사용 가능한 RAM이 많다면 Linux와 같은 적절한 OS가 디스크를 캐싱하여 기꺼이 더 빨리 사용할 수 있습니다.
제공된 페이지가 원하는 페이지가 아닙니다. 진리표를 제공하고 주어진 함수의 가장 작은 BDD 기반 표현 인 ROBDD (즉, 감소 된 OBDD)를 계산하려고합니다. 페이지에서 아무 것도 허용하지 않습니다. – tomash
글쎄, 표현으로 주어진 함수에서 ROBDD를 그린다. (실제로 진리표가 아니다.) 제목에는 BDD 만 나와 있지만 출력은 ROBDD입니다. 아니면 최고의 변수 순서를 찾고 있습니까? – Lorenzo