프롤로그를 사용하여 소프트 제약 조건을 지정하는 방법은 무엇입니까? (부드러운 제약이있는 퍼즐)

debugcn 에 게시 Dev

브루스

프롤로그를 사용하여 퍼즐을 풀라는 임무를 받았습니다.

지난 몇 시간 동안 프롤로그에 대한 몇 가지 온라인 자습서를 읽은 프롤로그 초보자이기 때문에 어떻게 시작해야할지 모르겠습니다 ..

퍼즐은 훨씬 더 큰 규모이고 더 많은 제약이 있지만, 나중에 크기를 조정할 수 있도록 아이디어를 얻고 싶기 때문에 여기서 단순화하겠습니다.

퍼즐은 다음과 같이 진행됩니다 : A와 B의 2 명의 직원이 한 주에 근무해야합니다. (주말 포함) 규칙 :

하루에 A 또는 B (둘다는 아님)가 작동해야합니다.
화요일에 일해야합니다.
아무도 2 일 이상 지속적으로 일할 수 없습니다.

소프트 제약 :

A는 목요일에 일하는 것을 선호합니다 (A가 목요일에 일하는 경우 2 점 추가).
B는 수요일에 일하는 것을 싫어합니다 (B가 수요일에 일하지 않으면 5 점 추가).

도표:

|--------|--------|--------|---------|-----------|----------|--------|----------| 
|        | Sunday | Monday | Tuesday | Wednesday | Thursday | Friday | Saturday |
|--------|--------|--------|---------|-----------|----------|--------|----------| 
|    A   |        |        |         |           |          |        |          |
|--------|--------|--------|---------|-----------|----------|--------|----------|
|    B   |        |        |         |           |          |        |          |
|--------|--------|--------|---------|-----------|----------|--------|----------|

가능한 가장 높은 점수를 얻을 수 있도록이를 예약하는 방법은 무엇입니까?

가능한 한 가지 해결책 (여러 가지가 있음)은 다음과 같습니다.

|--------|--------|--------|---------|-----------|----------|--------|----------| 
|        | Sunday | Monday | Tuesday | Wednesday | Thursday | Friday | Saturday |
|--------|--------|--------|---------|-----------|----------|--------|----------| 
|    A   |        |        |    X    |     X     |          |        |     X    |
|--------|--------|--------|---------|-----------|----------|--------|----------|
|    B   |    X   |    X   |         |           |     X    |    X   |          |
|--------|--------|--------|---------|-----------|----------|--------|----------|

얻을 수있는 최대 점수는 5 점입니다. 모든 규칙을 만족하면서 7 점 만점을 얻을 수있는 솔루션이 없기 때문입니다.

내가 가지고있는 질문 :

소프트 제약으로 규칙을 어떻게 설정합니까? 위의 소프트 제약 조건 하에서 모든 규칙을 준수하는 것은 불가능하므로 가장 높은 점수를 기반으로 할 규칙을 결정해야합니다.
프롤로그에서 위와 같은 2D 배열을 표현하는 방법은 무엇입니까? List에 대해 읽었지만 2d List를 나타내는 방법을 잘 모르겠습니다.

미리 감사드립니다!

머리카락 C.

Prolog에서는 간단한 문제 에 대해 단순함으로 흥미로운 단순한 '패턴', 평범한 오래된 생성 및 테스트 를 적용 할 수 있습니다 . 우리는 적절한 도메인 생성기와 테스트를 '그냥'제공합니다.

generate(D0, D) :-
    length(D0, DL),
    length(D, DL),
    maplist(dom_element, D).
dom_element(a).
dom_element(b).

test(D, Score, D) :-
    D = [_Sunday, _Monday, Tuesday, Wednesday, Thursday, _Friday, _Saturday],

    % 1. In a single day, either A or B (but not both) must be working
    %    Here True by construction

    % 2. A must work on Tuesday
    Tuesday = a,

    % 3. no one can work continuously for more than 2 days
    no_more_than_2(D),

    % soft 1. A prefers to work on Thursday (add 2 points if A works on Thursday )
    ( Thursday = a -> S1 is 2 ; S1 is 0 ),

    % soft 2. B dislike to work on Wednesday (add 5 points if B doesn't work on Wednesday)
    ( Wednesday \= b -> S2 is 5 ; S2 is 0 ),

    Score is S1 + S2.

% edit: jshimpfs suggestion, beside being much better, highlights a bug
no_more_than_2(D) :-
    nth0(I, D, E),
    length(D, L),
    J is (I+1) mod L,
    nth0(J, D, E),
    K is (J+1) mod L,
    nth0(K, D, E),
    !, fail.
no_more_than_2(_).

solve(D0, Best) :-
    D0 = [sun,mon,tue,wed,thu,fri,sat],
    setof(Score/Sol, D^(generate(D0, D), test(D, Score, Sol)), All),
    last(All, Best).

테스트:

?- solve(_,L).
L = 5/[b, b, a, a, b, b, a].

이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.

침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제

에서 수정2021-06-1

몇 마디 만하겠습니다

0리뷰

로그인참여 후 검토

Related 관련 기사

기사