"자주 사용하지 않는"알고리즘 -

Question

나는 유한 임무 풀에서 사용자의 임무를 추출하기로되어있는 응용 프로그램을 구축 중입니다. 문제는 내가 원하는 것입니다 : 사용자가 두 번 같은 임무를 얻을하지 않습니다

1. ,
2. 약간의 시간이 될 때까지 사용자는 (응용 프로그램)에 자신의 친구와 같은 임무를 얻을하지 않습니다 통과했다.

내 문제를 요약하면 가장 일반적인 임무는 풀에서 입니다.

누군가 가장 일반적인 것을 찾아내는 알려진 알고리즘 (LFU)을 참조 할 수 있습니까? 이론적 측면도 필요합니다. 누군가 Scientific American과 같은 유명 잡지의 기사 나 연구 논문을 잘 알고 있으면 좋을 것입니다.

Answer 1

자주 사용하지 않는 미션을 얻으려면 모든 미션에 사용 된 횟수를 세는 카운터를 부여하기 만하면됩니다. 그런 다음 가장 낮은 카운터 값으로 임무를 검색하십시오.

친구 그룹이 자주 사용하지 않는 임무를 수행하려면 모든 사용자에게 자신이 수행 한 임무 (횟수)를 저장할 수 있습니다. 이 정보는 어쨌든 유용 할 것입니다. 그런 다음 사용자를 위해 새로운 임무를 선택해야 할 때 사용자 및 모든 친구들이 사용한 임무 및 빈도를 (임시로) 결합한 목록을 빈도별로 쉽게 만들고 정렬 할 수 있습니다. 이것은별로 비싸지 않다.

Answer 2

좋은 시작은 일반적인 그래프에서 완벽한 최소 매칭을위한 Edmond Blossom V 알고리즘입니다. 만약 당신이 이분 그래프를 가지고 있다면 Floyd-Warshall 알고리즘을 찾아서 최단 경로를 찾을 수 있습니다. 어쩌면 토폴로지 검색도 사용할 수 있지만이 알고리즘은 실제로 배우기가 어렵 기 때문에 모르겠습니다.

Answer 3

귀하의 2 가지 요구 사항을 바탕으로, 나는 "최소한"사용 된 임무가이 작업과 관련이 없음을 알 수 없습니다. 반복하지 않는 임무를 원한다고하셨습니까?

옵션 1 :
모든 임무를 수행하기 위해 어떤 용기를 사용합니까? 귀하 또는 귀하의 친구가 선교사를 선택하면 그 선교사를 목록의 끝에 옮기십시오 (선교부와 교환하십시오). 이제 초기 목록을 2 개의 하위 목록으로 나눕니다. 첫 번째 부분은 사용하지 않은 임무를 보유하고 두 번째 부분은 사용 된 임무를 수행합니다. 2 목록을 구분하는 피벗/색인을 추적하십시오.
귀하 또는 귀하의 친구들이 새로운 임무를 선택할 때마다 첫 번째 하위 목록에서 그것을 선택합니다. 그런 다음 두 번째 하위 목록으로 이동하고 피벗을 업데이트합니다. 옵션 2

: 는 결국 임무를 반복하되 최소한의 시간을 선택 한 첫 번째 사람을 선택하면, 당신은 컨테이너 A 최소 힙 할 수 있습니다. 각 임무에 사용 카운터를 추가하고이를 기반으로 힙에 카운터를 추가하십시오. 임무를 추출하고 사용 카운터를 증가시킨 다음 다시 힙에 넣습니다. 이것은 좋은 해결책이지만 프로그램이 얼마나 간단한 지에 따라 원형 버퍼를 사용할 수도 있습니다.

당신이 당신이 필요로하는 구조가 min-heap 생각

Answer 4

:)을 구축하는지에 대한 자세한 내용을 알고하는 것이 좋을 것이다. 그것은 O (Log (n))의 최소값을 추출 할 수 있고 O (Log (n))의 항목 값을 증가시킬 수 있습니다.