OptAtlas

감소 우선 적합 (First-Fit Decreasing)

항목을 큰 순으로 정렬해 첫 번째로 맞는 빈에 넣는 휴리스틱.

다른 이름: First-Fit Decreasing · FFD · 퍼스트핏 감소

항목을 크기 내림차순으로 정렬한 다음, 각 항목을 현재 열린 빈 중 들어가는 첫 번째 빈에 넣는(없으면 새 빈을 여는) 빈 패킹 휴리스틱. 고전적인 근사비 분석으로 잘 알려져 있으며, 2D/직교 변형의 출발점으로도 쓰인다.

주장 & 증거

모든 관계는 증거 등급을 가진 하나의 주장이고, 문제 간 관계에는 해당되는 경우 등가 수준도 표시합니다. 증거 정책을 참고하세요.

A–X는 근거의 신뢰도, E0–E4는 문제 사이의 수학적 유사도입니다. 두 축은 서로 독립적입니다.

이 항목에서 나가는 관계 1

  • 방법 공유
    감소 우선 적합 (First-Fit Decreasing)에서 바텀-레프트-필 (Bottom-Left Fill)로

    감소 우선 적합과 바텀-레프트-필은 모두 항목을 정해진 규칙으로 하나씩 놓는 구성적 배치 휴리스틱이다.

    증거B · 서베이 / 튜토리얼 / 커뮤니티
    등가E3 · 구조적 유추

    출처

    • 출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems
      서지정보

      Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.

이 항목으로 들어오는 관계 2

  • 사용 방법
    2D 빈 패킹에서 감소 우선 적합 (First-Fit Decreasing)로

    감소 우선 적합(FFD) 계열의 구성적 휴리스틱이 빈 패킹의 빠른 근사해에 널리 쓰인다.

    증거B · 서베이 / 튜토리얼 / 커뮤니티

    출처

    • 출처 등급: A — 동료심사 논문 / 공식 문서Two-dimensional packing problems: A survey
      서지정보

      Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.

  • 사용 방법
    2D 스트립 패킹에서 감소 우선 적합 (First-Fit Decreasing)로

    레벨 기반 감소-우선 적합(FFDH 등)은 스트립 패킹의 고전적 구성적 휴리스틱이다.

    증거B · 서베이 / 튜토리얼 / 커뮤니티

    출처

    • 출처 등급: A — 동료심사 논문 / 공식 문서Two-dimensional packing problems: A survey
      서지정보

      Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.