어떤 종류의 알고리즘을 사용해야합니까?

Question

그래서 아래에 설명 된 문제를 해결하기 위해 노력하고 있습니다. 문제를 간단하게 설명 할 수 없으므로 실제로 문제를 찾고 있습니다. 누군가가 올바른 알고리즘이나 경로를 해결할 수 있기를 바라고 있습니다.

문제 (간체) :

그래서 나는 여러 사람 개체가 말할 수 있습니다.

Person1 
Person2 
Person3 

는 지금은 6 개 슬롯

각 사람이 규칙은 그들과 관련된있다

Slot1 
Slot2 
Slot3 
Slot4 
Slot5 
Slot6 

이 말할 수와 같은

• PERSON1가 홀수와 슬롯을 사용할 수 있어야합니다 3 다른 슬롯.
• Person2 슬롯 2 개만 들어갈 수 있고 슬롯 2 개가 있어야합니다.
• Person3은 소수의 소수 슬롯 1 개만 사용할 수 있습니다.

그래서 우리는 내가이 AI/기계 학습의 사용을 필요로 알고

Slot1 - Person3 
Slot2 - Person1 
Slot3 - Person2 
Slot4 - Person1 
Slot5 - Person2 
Slot6 - Person1 

와 끝까지 난이 지역에 몇 가지 조사를했을하지만 난이에 사용되어야 하는지를 알고리즘을 찾을 수 없습니다 문제 또는 어떻게 검색 할 것인가. 내가 이것을 어떤 식 으로든 해낸 유일한 방법은 회귀 나무를 통과하는 것이지만 그것은 나에게 잘못된 길을 택한 것처럼 보입니다.

참고 :이 문제를 해결하기 위해 C#을 사용하고 Encog와 같은 일부 프레임 워크를 사용합니다.

Answer 1

실제로이 문제는 표준 이산 최적화 문제입니다. coursera discrete optimization course을보고 싶을 수 있습니다. 첫 주에는 간단한 퍼즐이라는 워크샵이 있습니다. 그것은 당신에게 비슷한 문제를주고 자신의 플랫폼 미니 아연에서 그것을 해결하는 방법을 보여줍니다.

이러한 유형의 문제가 해결 된 방법을 이해 한 후에 List of optimization software에서 C# 솔루션을 찾고 싶을 수 있습니다.

Answer 2

사실 나는이 문제를 간단한 수정으로 Maximum Matching으로 해결할 수 있다고 생각합니다. 표준 최대 일치에서 각 노드는 하나의 다른 노드와 만 일치하지만 여기에서는 사람이 여러 개의 일치를 가질 수 있습니다. Person의 인스턴스를 여러 개 작성하면이 문제점을 최대 일치로 줄일 수 있습니다. 예를 들어

PERSON1는 홀수 슬롯을 사용할 수없는 3 개 다른 슬롯에 있어야한다.

Person1에 대해 3 개의 노드를 만들고 짝수 번호 슬롯에 연결하십시오.

사람이 단지 최대 2에서 슬롯에 갈 수 및하여 Person2의 2 개 노드 만들기 2 개 슬롯

해야하며 2보다 큰 수의 슬롯에 연결해야합니다.

사람 3은 소수의 소수로만 갈 수 있습니다.

Person3의 노드를 하나 만들고 슬롯 1, 슬롯 2, 슬롯 3 및 슬롯 5에 연결하십시오.

결과 그래프에서 최대 일치를 수행하면 대답을 찾을 수 있습니다.

Answer 3

사람과 슬롯 간의 쌍이 문제를 해결하기 위해 지식이 필요한 일정 문제입니다. 지식은 "Person1은 홀수의 슬롯을 사용할 수없고 3 개의 다른 슬롯에 있어야합니다."와 같은 규칙으로 설명됩니다. 문제를 해결하는 알고리즘은 모든 가능한 솔루션을 생성하기 위해 규칙과 주어진 자원 (3 인 및 6 슬롯)을 사용합니다. Computerscience는 지식을 기계 판독 가능 코드로 형식화하는 작업을 수행합니다. 많은 프로그래밍 언어가 있습니다. PDDL, Prolog 또는 객체 지향 언어. ICAPS 컨퍼런스에서 논의 된 고전적인 "인공 지능 계획 및 스케줄링"에서 PDDL 언어는 지식 모델링을위한 선호되는 선택 일 것입니다. 주어진 도메인을 해결하는 알고리즘 자체는 대부분 역 추적, 몬테카를로 트리 검색 또는 단순한 무차별 대항력입니다. 이를 "검색 문제 해결"이라고합니다.