무게 선별작업 자동화 프로그램

최근에 농사일을 하시는 분에게서 알고리즘 제작 의뢰를 요청받았습니다. 의뢰자분은 과일 농장을 운영하고 계셨고, 매 포장 때마다 수작업으로 과일의 무게를 재고 중량을 맞추는 선별 과정 때문에 어려움을 겪고 계셨는데요. 중량에 맞는 조합들의 과일만 자동으로 찾아주기만 해도 업무 개선에 큰 도움이 될 것입니다! 오늘 작성해볼 코드는 무게 선별작업 자동화 프로그램입니다.

 

참고할 만한 사이트

https://youtu.be/VbV5f23xmhM

자동 선별 기계는 과일의 무게를 재는 센서들이 (1 - 10) 번까지 있고, 작동 전 어떻게 동작할지에 대한 옵션을 선택할 수 있습니다.

1) 옵션에 따라 조합의 수를 조정할 수 있는 스위치 변수가 있습니다.

    1번 스위치: 가능한 조합의 수 2개

    2번 스위치: 가능한 조합의 수 3개

    3번 스위치: 가능한 조합의수 4개

    4번 스위치: 가능한 조합의수 5개

    5번 스위치: 가능한 조합의수 6개

    6번 스위치: 가능한 조합의수 7개

 

2) 중량 정보는 하나만 선택할 수 있습니다. 1kg, 2kg, 1kg or 2kg

3) 과일의 무게를 정확히 중량 정보에 맞게 정확히 측정할 수 없으니 어느 정도 허용 가능한 오차범위를 선택할 수 있습니다.

 

예시를 보겠습니다.

 

예시 1)

중량 정보 1kg

1번 스위치만 on

센서 1: 500g

센서 2: 400g

센서 3: 500g

센서 4: 300g

센서 5: 900g

센서 6: 300g

 

가능한 조합

센서 1, 센서 3 

센서 5, 센서 6

 

예시 2)

중량 정보 1kg

2번 스위치만 on

센서 1: 500g

센서 2: 400g

센서 3: 500g

센서 4: 300g

센서 5: 900g

센서 6: 300g

 

가능한 조합

센서 2, 센서 4, 센서 6

 

켜진 스위치 버튼에 대응되는 조합의 수에 대해선 반드시 탐색이 이뤄줘야 합니다

문제 해결을 위해 다음의 아이디어를 적용하였습니다.

1) 중량 정보와 스위치 정보를 확인해 가능한 모든 조합을 만들어낸다.

2) 만들어진 조합에서 조건에 맞는 조합만 따로 저장을 시킵니다.

3) 조건에 맞는 조합을 찾았다면, 더 이상 탐색을 하지 않습니다.

#include <stdio.h>
#include <stdint.h>

//#define PRINT_ALL_COMBINATION

const int SENSOR_MAX = 10;
int16_t sensors[SENSOR_MAX] = {500, 1000, 600, 400, 1000, 800, 800, 570, 692, 706};
int16_t answer[SENSOR_MAX]  = {0};
int32_t totalHeight = 0;

const int SWITCH_NUM = 6;
int8_t switchFlag[SWITCH_NUM] = {0};
int8_t switchNum[SWITCH_NUM]  = {2, 3, 4, 5, 6, 7};

int8_t height = -1; // -1: 2kg 
                    //  0: 4kg 
                    //  1: 2kg or 4Kg
const uint32_t t_2000G = 2000;
const uint32_t t_4000G = 4000;
int16_t error = 500;

int16_t temp[SENSOR_MAX] = { 0 };
int8_t findFlag = 0;

void Init_Option()
{
    for (int8_t k = 0; k < SWITCH_NUM; k++)
        switchFlag[k] = 1;
    height = -1;
}

void Show_Option()
{
    printf("###############[Option]###############\n");
    if (height == -1 || height == 0) {
        int16_t val = t_2000G;
        if (height == 0) {
            val = t_4000G;
        }
        printf("Height: %dg\n", val);
        printf("Error: %d ", error);
        printf("(%dg <= Height <= %dg)\n", val, val + error);
    }
    else if (height == 1) {
        printf("Height: %dg or %dg\n", t_2000G, t_4000G);
        printf("Error: %d ", error);
        printf("(%dg <= Height <= %dg) or (%dg <= Height <= %dg)\n", t_2000G, t_2000G + error, t_4000G, t_4000G + error);
    }
    else {
        printf("Height option is invalid\n");
    }

    printf("\n[Switch]\n");
    for (int k = 0; k < SWITCH_NUM; k++) {
        printf("switch [%d]: %d\n", k + 1, switchFlag[k]);
    }
}

int8_t isPossible(uint32_t sum)
{
    int8_t flag = 0;

    if (height == -1) {
        flag |= (t_2000G <= sum && sum <= t_2000G + error) ? 1 : 0;
        return flag;
    }

    if (height == 0) {
        flag |= (t_4000G <= sum && sum <= t_4000G + error) ? 1 : 0;
        return flag;
    }

    if (height == 1) {
        flag |= (t_2000G <= sum && sum <= t_2000G + error) ? 1 : 0;
        flag |= (t_4000G <= sum && sum <= t_4000G + error) ? 1 : 0;
        return flag;
    }

    return 0;
}

void Combination(uint8_t r, uint8_t index, uint8_t depth, uint32_t sum)
{
#if not defined PRINT_ALL_COMBINATION
    if (findFlag)
        return;
#endif

    if (r == 0)
    {
        if (isPossible(sum))
        {
#if not defined  PRINT_ALL_COMBINATION
            findFlag = 1;
#endif
            totalHeight = sum;
            for (uint8_t k = 0; k < SENSOR_MAX; k++)
                answer[k] = temp[k];

            printf("Sensor Number: ");
            for (uint8_t k = 0; k < SENSOR_MAX; k++)
                printf("%2d ", answer[k]);
            printf("Total Height: %d\n", sum);
        }
        return;
    }

    if (depth >= SENSOR_MAX)
        return;

    temp[index] = (depth + 1);
    Combination(r - 1, index + 1, depth + 1, sum + sensors[depth]);
    Combination(r, index, depth + 1, sum);
}

int main()
{
    Init_Option();
    Show_Option();
    printf("###############[Result]###############\n");

    for (int8_t k = 0; k < SWITCH_NUM; k++)
    {
        if (switchFlag[k]) {
            Combination(switchNum[k], 0, 0, 0);
        }
    }

#if not defined PRINT_ALL_COMBINATION
    if (!findFlag)
    {
        printf("not found\n");
    }
#endif

    return 0;
}

1) 중량 정보와 스위치 정보를 확인해 가능한 모든 조합을 만들기 위해서 Combination 알고리즘을 적용시켰습니다. (Combination 알고리즘은 나올 수 있는 모든 조합 셋을 찾아줍니다.)

 

2) 조합 셋 중, isPossible이란 함수를 통해 조건에 부합하는 조합 셋 인지 검사합니다.

 

3) 조건에 만족한다면 조합 셋을 다른 메모리에 따로 저장합니다, 그리고 findFlag를 활성화시켜 더 이상 탐색을 시키지 않습니다.

 

이 알고리즘은 무게를 감지하는 센서의 수가 많아질수록 시간 복잡도가 늘어나는 특징이 있는데요. 하드웨어의 연산 허용범위를 고려해 센서의 수를 선정할 필요가 있습니다.

 

자 오늘은 여기까지!