최소 절단 배치 알고리즘의 클래스

본 논문에서는 전기 회로의 물리적 구현과 관련된 몇 가지 배치 문제를 해결하기 위한 최소 절단 배치 알고리즘의 클래스를 제시합니다. 우리는 거리 기반의 고전적인 목적 함수를 포기할 필요성에 대해 논의하고, 절단에 기반한 새로운 목적 함수를 도입합니다. 선 c에 의해 절단된 신호의 수는 회로를 라우팅할 때 c를 교차해야 하는 라우팅 트랙의 수에 대한 하한입니다. 세 가지 특정 목적 함수가 도입되며, 이 중 하나와 반둘레에 기반한 고전적인 거리 측정 간의 관계가 제시됩니다. 두 개의 최소 절단 배치 알고리즘이 제시되며, 각각 Ouadrature 및 Slice/Bisection으로 언급됩니다. 블록 및 절단 선의 개념이 도입됩니다. 이 두 개체는 새로운 최소 절단 배치 알고리즘을 개발하는 데 주요 구성 요소입니다. 제시된 대부분의 개념은 구현되었으며, 일부 실험 결과도 제시됩니다.