태그 보관물: data-structure

data-structure

논리 게임 / 공제 규칙 / 충분한 단서에 대한 데이터 구조? Puzzle 과

나는 Einstein ‘s Puzzle 과 유사한 논리 게임을 개발하는 것에 대해 흥겨워 왔는데 , 새로운 게임 재생마다 다른 단서가 있습니다.

제공하는 단서가 고유 한 솔루션을 가리 키도록 보장하기 위해 다양한 엔티티 (애완 동물, 주택의 색상, 국적 등), 공제 규칙 등을 처리하기 위해 어떤 데이터 구조를 사용 하시겠습니까?

가능한 단서와 함께 공제 규칙을 적용하는 방법에 대해 고민하고 있습니다. 모든 통찰력은 감사하겠습니다.

답변

와. 이것은 실제로 인공 지능과 컴퓨터 게임 을 쓸 때 Richard Bartle과 같은 구식 AI 시맨틱 웹이 미래의 게임에 중요 할 것이라고 생각되는 상황처럼 보입니다 . 기본적으로 두 개의 데이터 목록 (데이터베이스 테이블 등)이 있으며, 첫 번째 목록은 다음과 같이 서로 관련이있는 방법에 대한 규칙을 지정합니다.

a PERSON must LIVE IN a DOMICILE
a PERSON must OWN an ANIMAL
a PERSON must DRINK a BEVERAGE
a PERSON must SMOKE a CIGARETTE BRAND
a PERSON must BE OF a NATIONALITY
a DOMICILE must BE IN a POSITION
a DOMICILE must BE OF a COLOR

그런 다음 카테고리의 인스턴스가 있습니다.

ANIMAL: dog snail zebra fox horse
BEVERAGE: milk tea OJ coffee water
CIGARETTE BRAND: Kools Parliaments Luckies OldGold Chesterfields
NATIONALITY: Englishman Spaniard Ukrainian Japanese Norwegian
POSITION: first second third fourth fifth
COLOR: red green yellow ivory blue

이러한 데이터 구조는 상황을 완전히 캡슐화하지는 않습니다. 고유성 제약 조건이 필요하고 일부 범주 POSITION에는 “오른쪽”, “왼쪽”및 “다음”의 처리 와 같은 메타 규칙이 필요합니다. 예를 들어 “개념에 대한 것입니다. 그러나 문제의 구조는이를 강력하게 제안하는 것 같습니다.

Dunno 이것이 당신을 멀리 데려다 줄 것이지만, 그것이 도움이되기를 바랍니다.

답변

AIMA 프로젝트 와 함께 제공되는 제약 만족 문제 (CSP) 에 대한 Python 코드를 살펴 보는 것이 좋습니다 . 유효한 제약 조건을 추적하기 위해 Dictionary (연관 배열 / 해시 테이블)를 사용합니다. 또한 최소 충돌 및 AC3과 같이 CSP를 해결하는 데 사용되는 여러 알고리즘이 구현되어 있습니다.

이 코드에는 링크 된 것과 같은 샘플 Zebra 문제가 예제로 포함되어 있습니다.

답변

이것은 실제로 매우 깊습니다. Wikipedia가 언급하지 않은 것이 이상합니다.

당신이 찾고있는 것은 아마도 Fitch proofs 와 같은 것들에 도달 할 수있는 매우 단단한 증거입니다 . 그래서 우리는 주어진 데이터에서 물건을 빼려고합니다. 많은있다 피치 증거 빌더 당신을 위해 많은 일을한다. 그러나 일부 운동은 교정하지 않습니다.

사용자가 계산을 수행 해야하는지 모르겠습니다. 그렇다면 3SAT 와 같이 다항식 시간에 취소 할 수없는 문제에주의하십시오.

사용하려는 데이터 구조는 일종의 Rule클래스 를 원한다고 생각합니다 . 규칙은 유형에 따라 무엇이든 될 수 있습니다. 술어 논리 에는 규칙이 많지 않으므로 상속하면 (if, iff 및 / 또는 …이 아닌)이를 극복 할 수 있습니다. 이 규칙 만 평가하면됩니다. 그리고 규칙이 할 수있는 유일한 일은 true 또는 false를 반환하는 것입니다. 그것이 술어 논리로하는 일이기 때문입니다. 대학에서 나는 John Kelly 가이 책을 읽는 것이 좋습니다 .

수업으로 돌아 가기 : 수학을 사용하여 일반 계산을 구현하는 것처럼 이러한 문제가 나타납니다. +운영자 란 무엇입니까 ? 여기에는 두 개의 매개 변수가 포함되는데,이 매개 변수는 자체적으로 새로운 방정식 일 수도 있고 숫자 일 수도 있습니다. 나는 당신이 규칙과 동일하다고 생각합니다. 매개 변수로 새 규칙을 갖거나 부울 (소위 술어) 만 가질 수 있습니다.

나는 이것이 당신에게 특히 도움이되기를 바랍니다. 더 알고 싶거나 잘못된 방향으로 가고 있다면 알려주세요.

답변

나는 좋은 대답이 없지만 같은 종류의 문제에 대한 힌트를 찾고 github 에서이 저장소를 찾았습니다.

https://github.com/nateinaction/Zebra-Puzzle

단서를 선택하고 퍼즐을 해결하기 위해 필요한 단서를 몇 가지 결정하는 논리가 포함되어 있습니다.

답변

이 문제를 해결하는 데 있습니다.

물론, 나는 거꾸로 일하는 것이 그리 어렵지 않을 것이라고 생각합니다. 다음과 같은 목록이 있습니다.

  • 프레드 레드 독

  • 스티브 블루 고양이

  • 빌 퍼플 고래

  • 에릭 시안 돌핀

어느 것이 쉽게 생성 될 수 있고, 그로부터 일련의 규칙을 구성하십시오.

저장에 관해서는, [Fred, Steve, Bill, Eric]와 일련의 답변 [Fred, Red, Dog]이 각각 별도의 세트가 아닌 이유. 그런 다음 ‘NAME 님이 액션 오브젝트를 수행하지 않습니다’.

당신이 그것에 도달하면, 독특한 솔루션이 정말로 중요합니까? 게임이 그것들을 목록으로 나누고 ‘세트 1에 고래가 포함되어 있지 않습니다’를 체크하십시오.

답변