Логическая задача: предвыборная дискуссия

В этой теме 3 ответа, 2 участника, последнее обновление  Васильев Владимир Сергеевич 1 год, 5 мес. назад.

  • Автор
    Сообщения
  • #2782

    questioner
    Участник

    Нужно решить логическую задачу на языке Prolog:

    Перед выборами в законодательное собрание три брата вели долгую дискуссию, которую закончили следующими довольно запутанными высказываниями.
    Пьер. Если Жан проголосует за Дюбуа, я буду голосовать за Дюпона, Но если он проголосует за Дюрана, я буду голосовать за Дюбуа. С другой стороны, если Жак проголосует за Дюпона, я буду голосовать за Дюрана.
    Жан. Если Пьер проголосует за Дюрана, я не буду голосовать за Дюпона. Но если Жак проголосует за Дюбуа, то я проголосую за Дюпона.
    Жак. Если Пьер проголосует за Дюпона, я не буду голосовать за Дюрана.
    Подошел день выборов. Все три брата проголосовали за разных кандидатов. За кого именно?

    Я смотрел тему про решение логических задач и поиск в пространстве состояний, но это не помогло. Проблема в том, что в этой задаче у каждого персонажа есть набор высказываний, каждое из которых содержит определенное условие и следствие (ограничения, которые должны наложиться на ответ), однако если условие не выполняется – то и ограничения не должны накладываться.
    Решить нужно на Visual Prolog 5.2.

  • #2783

    Для начала надо описать типы данных – имена кандидатов, избирателей, составной тип для фиксации результатов голосования и тип списка результатов:

    DOMAINS
    	voter_d = per;zan;zak
    	candidate_d = dubua;dupon;duran
    	vote_d = vote(voter_d, candidate_d)
    	
    	votes_d = vote_d*

    Затем нужно описать возможных кандидатов во внутренней базе данных для их последующего перебора:
    PREDICATES
    	nondeterm candidate(candidate_d)
    CLAUSES
    	candidate(dubua).
    	candidate(dupon).
    	candidate(duran).

    Если вы уже сейчас запустите генерацию вариантов (для каждого избирателя запросите кандидата) – то получите 27 ответов:
    GOAL 
    	candidate(PerCandidate),
    	candidate(ZanCandidate),
    	candidate(ZakCandidate).

    prolog_logical_task_votes_discussion

  • #2785

    Далее нужно наложить на решения ограничения. В задаче сказано, что каждый братья проголосовали за разных кандидатов. Чтобы осуществить такую проверку можно поместить кандидатов в список и применить к нему функцию unique, но можно решить следующим образом:

    NOT(PerCandidate = ZanCandidate), 
    NOT(PerCandidate = ZakCandidate), 
    NOT(ZanCandidate = ZakCandidate).

    Т.е. мы требуем, чтобы кандидат Пьера отличался от кандидатов Жана и Жака, которые тоже должны быть различны. Теперь интерпретатор вернет нам всего 6 решений.

  • #2787

    Утверждения братьев типа “если Жан проголосует на Дюбуа, то Пьер – за Дюпона” могут быть записаны следующим образом:

    statement(per, 1, Votes):-
    	member(vote(zan, dubua), Votes), !,
    	member(vote(per, dupon), Votes).
    statement(per, 1, Votes).

    В данном случае единица – номер высказывания Пьера. Тут используется функция member для поиска элемента списка. Мы сначала ищем в списке утверждение о том, что Жан проголосовал за Дюбуа – если находим, то выполняем отсечение и требуем наличие в списке записи, что Пьер голосовал за Дюпона. Отсечение в данном случае является красным, т.к. изменяет ход вычислений – мы поставили его для того, чтобы исключить варианты когда в списке будет найдена запись vote(zan, dubua), но будет отсутствовать vote(per, dupon). Если же первая запись не будет найдена в списке, то данное утверждение не должно накладывать ограничений, поэтому второе правило предиката завершается истиной при любом наборе голосов.

    Аналогичным образом могут быть записаны все остальные записи о голосовании:

    	statement(per, 1, Votes):-
    		member(vote(zan, dubua), Votes), !,
    		member(vote(per, dupon), Votes).
    	statement(per, 1, Votes).
    	
    	statement(per, 2, Votes):-
    		member(vote(zan, duran), Votes), !,
    		member(vote(per, dubua), Votes).
    	statement(per, 2, Votes).
    	
    	statement(per, 3, Votes):-
    		member(vote(zak, dupon), Votes), !,
    		member(vote(per, duran), Votes).
    	statement(per, 3, Votes).
    	
    	statement(zan, 1, Votes):-
    		member(vote(per, duran), Votes), !,
    		NOT(member(vote(zan, dupon), Votes)).
    	statement(zan, 1, Votes).
    	
    	statement(zan, 2, Votes):-
    		member(vote(zak, dubua), Votes), !,
    		member(vote(zan, dupon), Votes).
    	statement(zan, 2, Votes).
    
    	statement(zak, Votes):-
    		member(vote(per, dupon), Votes), !,
    		NOT(member(vote(zak, duran), Votes)).
    	statement(zak, _Votes).

    У Жака всего одно высказывание, поэтому можно обойтись без нумерации. Для остальных избирателей необходимо написать вспомогательное правило, которое применит к сгенерированному решению все ограничения:

    	statement(per, Votes):-
    		statement(per, 1, Votes),
    		statement(per, 2, Votes),
    		statement(per, 3, Votes).		
    	
    	statement(zan, Votes):-
    		statement(zan, 1, Votes),
    		statement(zan, 2, Votes).

    Остается поместить результаты голосования в список и передать на вход функциям, описывающим ограничения:

    	Votes = [
    		vote(per, PerCandidate),
    		vote(zan, ZanCandidate),
    		vote(zak, ZakCandidate)
    	],
    	
    	statement(per, Votes),
    	statement(zan, Votes),
    	statement(zak, Votes).

    Теперь программа вернет лишь одно решение.

Для ответа в этой теме необходимо авторизоваться.