Логическая задача. Составление расписания на Prolog

      Комментарии к записи Логическая задача. Составление расписания на Prolog отключены

Главная Форумы Программирование Помощь с решением задач на Prolog Решение головоломок на Prolog Логическая задача. Составление расписания на Prolog

В этой теме 2 ответа, 3 участника, последнее обновление  Tavasilyok 7 мес., 3 нед. назад.

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

    questioner
    Участник

    Решение логической задачи на Visual Prolog 5.2:

    В девятом классе в понедельник шесть уроков: иностранный язык (И), физика (Ф), химия (X), биология (Б), литература (Л), математика (М). Каждый из шести преподавателей — A, B, C, D, E, F — должен провести один урок. Известно следующее:
    Если C не преподает химию, то уж точно биологию; он же занят на третьем уроке в восьмом классе. F не литератор, на втором уроке присутствовать не может. A и B преподают иностранный язык или физику. На четвертом уроке — химия, физика или иностранный язык, но преподаватели не A и не B. Пятый урок проводит если не B, то D. На шестом уроке иностранный язык, химия или литература: преподаватели — B или C. Математик, считая (согласно учению Пифагора!) четные числа «счастливыми», просил дать ему «четный» урок. Биологический кабинет освобождается не ранее второго урока.
    Составить расписание на понедельник для 9-го класса, удовлетворяющее всем требованиям, и узнать, какой предмет преподает каждый учитель.

    В своих попытках решения использовала функции member и unique (для поиска элемента в списке и проверки списка на уникальность элементов).

    domains
      list = string*
      name = string
      subject = string
      number = string
      raspisanie = raspisanie(number,subject,name)
      desk = raspisanie*
    
    predicates
    
      prepodavatel(name)
      urok(subject)
      nomer(number)
      member(string,list)
      member(raspisanie,desk)
      unique(list)
      solve(desk)
      start(desk)
    
    clauses
    
      nomer("1").
      nomer("2").
      nomer("3").
      nomer("4").
      nomer("5").
      nomer("6").
    
      urok("In").
      urok("Fi").
      urok("Ch").
      urok("Bi").
      urok("Li").
      urok("Ma").
    
      prepodavatel("A").
      prepodavatel("B").
      prepodavatel("C").
      prepodavatel("D").
      prepodavatel("E").
      prepodavatel("F").
    
      solve(Solve):-
        Solve = [raspisanie(A,Aurok,Auchitel),raspisanie(B,Burok,Buchitel),raspisanie(C,Curok,Cuchitel),
                 raspisanie(D,Durok,Duchitel),raspisanie(E,Eurok,Euchitel),raspisanie(F,Furok,Fuchitel)],
                 nomer(A),nomer(B),nomer(C),nomer(D),nomer(E),nomer(F),unique([A,B,C,D,E,F]),
                 urok(Aurok),urok(Burok),urok(Curok),urok(Durok),urok(Eurok),urok(Furok),unique([Aurok,Burok,Curok,Durok,Eurok,Furok]),
                 prepodavatel(Auchitel),prepodavatel(Buchitel),prepodavatel(Cuchitel),prepodavatel(Duchitel),
                 prepodavatel(Euchitel),prepodavatel(Fuchitel),unique([Auchitel,Buchitel,Cuchitel,Duchitel,Euchitel,Fuchitel]),
                 member(raspisanie("3",_,P1),Solve),NOT (P1="C"),
                 member(raspisanie(_,U1,"C"),Solve),member(U1,["Ch","Bi"]),
                 member(raspisanie(N1,U2,"F"),Solve),NOT (U2="Li"),NOT (N1="2"),
                 member(raspisanie(N2,U3,P2),Solve),member(U3,["In","Fi"]),member(P2,["A","B"]),NOT (N2="4"),
                 member(raspisanie("4",U4,_),Solve),member(U4,["Ch","Fi","In"]),
                 member(raspisanie("5",_,P3),Solve),member(P3,["B","D"]),
                 member(raspisanie("6",_,P4),Solve),member(P4,["B","C"]),  
                 member(raspisanie("6",U5,_),Solve),member(U5,["Ch","Li","In"]), 
                 member(raspisanie(N3,"Ma",_),Solve),member(N3,["2","4","6"]),
                 member(raspisanie("1",U6,_),Solve),NOT (U6="Bi").             
    
      start(Solve):-solve(Solve),Solve = [raspisanie("1",_,_),raspisanie("2",_,_),raspisanie("3",_,_),
                 raspisanie("4",_,_),raspisanie("5",_,_),raspisanie("6",_,_)].
    
    goal
    
      start(X).

    В этом случае выдает кучу неправильных вариантов и зависает. Попробовала изменить код на:

    domains
      list = string*
      name = string
      subject = string
      number = string
      raspisanie = raspisanie(number,subject,name)
      desk = raspisanie*
    
    predicates
    
      prepodavatel(name)
      urok(subject)
      nomer(number)
      member(string,list)
      member(raspisanie,desk)
      unique(list)
      solve(desk)
      start(desk)
    
    clauses
    
      nomer("1").
      nomer("2").
      nomer("3").
      nomer("4").
      nomer("5").
      nomer("6").
    
      urok("In").
      urok("Fi").
      urok("Ch").
      urok("Bi").
      urok("Li").
      urok("Ma").
    
      prepodavatel("A").
      prepodavatel("B").
      prepodavatel("C").
      prepodavatel("D").
      prepodavatel("E").
      prepodavatel("F").
    
      solve(Solve):-
        Solve = [raspisanie(A,Aurok,Auchitel),raspisanie(B,Burok,Buchitel),raspisanie(C,Curok,Cuchitel),
                 raspisanie(D,Durok,Duchitel),raspisanie(E,Eurok,Euchitel),raspisanie(F,Furok,Fuchitel)],
                 nomer(A),nomer(B),nomer(C),nomer(D),nomer(E),nomer(F),unique([A,B,C,D,E,F]),
                 urok(Aurok),urok(Burok),urok(Curok),urok(Durok),urok(Eurok),urok(Furok),unique([Aurok,Burok,Curok,Durok,Eurok,Furok]),
                 prepodavatel(Auchitel),prepodavatel(Buchitel),prepodavatel(Cuchitel),prepodavatel(Duchitel),
                 prepodavatel(Euchitel),prepodavatel(Fuchitel),unique([Auchitel,Buchitel,Cuchitel,Duchitel,Euchitel,Fuchitel]),
                 member(raspisanie("3",_,P1),Solve),NOT (P1="C"),
                 %member(raspisanie(N1,U1,"C"),Solve),NOT (U1="In"),NOT (U1="Fi"),NOT (U1="Li"),NOT (U1="Ma"),NOT (N1="3"),
                 member(raspisanie(_,"Ma",P11),Solve),NOT (P11="C"),
                 member(raspisanie(_,"Fi",P11),Solve),NOT (P11="C"),
                 member(raspisanie(_,"Li",P11),Solve),NOT (P11="C"),
    
                 %member(raspisanie(N2,U2,"F"),Solve),NOT (U2="Li"),NOT (N2="2"),
                 member(raspisanie(_,"Li",P2),Solve),NOT (P2="F"),
                 member(raspisanie("2",_,P21),Solve),NOT (P21="F"),
    
                 %member(raspisanie(N3,U3,"A"),Solve),NOT (N3="4"),NOT (U3="Ch"),NOT (U3="Bi"),NOT (U3="Li"),NOT (U3="Ma"),
                 member(raspisanie(_,"Ch",P3),Solve),NOT (P3="A"),
                 member(raspisanie(_,"Bi",P31),Solve),NOT (P31="A"),
                 member(raspisanie(_,"Li",P32),Solve),NOT (P32="A"),
                 member(raspisanie(_,"Ma",P33),Solve),NOT (P33="A"),
                 member(raspisanie(N31,_,"A"),Solve),NOT (N31="4"),
                 %member(raspisanie(N32,U31,"B"),Solve),NOT (N32="4"),NOT (U31="Ch"),NOT (U31="Bi"),NOT (U31="Li"),NOT (U31="Ma"),
                 member(raspisanie(_,"Ch",P34),Solve),NOT (P34="B"),
                 member(raspisanie(_,"Bi",P35),Solve),NOT (P35="B"),
                 member(raspisanie(_,"Li",P36),Solve),NOT (P36="B"),
                 member(raspisanie(_,"Ma",P37),Solve),NOT (P37="B"),
                 member(raspisanie(N33,_,"B"),Solve),NOT (N33="4"),
                 member(raspisanie("4",_,P38),Solve),NOT (P38="A"),
                 member(raspisanie("4",_,P39),Solve),NOT (P39="B"),
    
                 %member(raspisanie("4",U4,_),Solve),NOT (U4="Bi"),NOT (U4="Li"),NOT (U4="Ma"),
                 member(raspisanie(N41,"Bi",_),Solve),NOT (N41="4"),
                 member(raspisanie(N42,"Li",_),Solve),NOT (N42="4"),
                 member(raspisanie(N43,"Ma",_),Solve),NOT (N43="4"),
    
                 %member(raspisanie("5",_,P5),Solve),NOT (P5="A"),NOT (P5="C"),NOT (P5="E"),NOT (P5="F"),
                 member(raspisanie(N5,_,"A"),Solve),NOT (N5="5"),
                 member(raspisanie(N51,_,"C"),Solve),NOT (N51="5"),
                 member(raspisanie(N52,_,"E"),Solve),NOT (N52="5"),
                 member(raspisanie(N53,_,"F"),Solve),NOT (N53="5"),
    
                 %member(raspisanie("6",_,P6),Solve),NOT (P6="A"),NOT (P6="D"),NOT (P6="E"),NOT (P6="F"),
                 member(raspisanie(N6,_,"A"),Solve),NOT (N6="6"),
                 member(raspisanie(N61,_,"D"),Solve),NOT (N61="6"),
                 member(raspisanie(N62,_,"E"),Solve),NOT (N62="6"),
                 member(raspisanie(N63,_,"F"),Solve),NOT (N63="6"),
    
                 %member(raspisanie("6",U7,_),Solve),NOT (U7="Fi"),NOT (U7="Bi"),NOT (U7="Ma"),
                 member(raspisanie(N7,"Bi",_),Solve),NOT (N7="6"),
                 member(raspisanie(N71,"Fi",_),Solve),NOT (N71="6"),
                 member(raspisanie(N72,"Ma",_),Solve),NOT (N72="6"),
    
                 %member(raspisanie(N8,"Ma",_),Solve),NOT (N8="1"),NOT (N8="3"),NOT (N8="5"),
                 member(raspisanie("1",U8,_),Solve),NOT (U8="Ma"),
                 member(raspisanie("3",U81,_),Solve),NOT (U81="Ma"),
                 member(raspisanie("5",U82,_),Solve),NOT (U82="Ma"),
    
                 member(raspisanie("1",U9,_),Solve),NOT (U9="Bi").
    
      start(Solve):-solve(Solve),Solve = [raspisanie("1",_,_),raspisanie("2",_,_),raspisanie("3",_,_),
                 raspisanie("4",_,_),raspisanie("5",_,_),raspisanie("6",_,_)].
    
    goal
    
      start(X).

    Тогда просто зависает. Подскажите, пожалуйста, в чем проблема моего кода.

  • #2887

    Генерацию гипотезы вы сделали вроде бы верно, но я не смог разобраться что вы пытались сделать дальше.
    Чтобы проверить гипотезу нужно проверить все утверждения из условия, например:

    Если C не преподает химию, то уж точно биологию; он же занят на третьем уроке в восьмом классе.

    Формализовать это на Prolog можно так:

    Solve = [
      raspisanie(A, Aurok, Auchitel),
      raspisanie(B, Burok, Buchitel),
      raspisanie(C, Curok, Cuchitel),
      raspisanie(D, Durok, Duchitel),
      raspisanie(E, Eurok, Euchitel),
      raspisanie(F, Furok, Fuchitel)
    ],
    /*
      генерация гипотезы
    */
    C = "3",
    member(Curok, [химия, биология]),
    /*
      остальные проверки
    */
    .

    Все остальные условия записываются точно также, например:

    F не литератор, на втором уроке присутствовать не может

    На Prolog запишется так:
    NOT(F="2"), NOT(Furok = литература).

    Это очень простая задача, я не понимаю зачем вы написали в ней столько вызово предиката member. Вы можете написать часть условий (даже те два, что я тут привел) и уже запустить поиск решений. По мере дописывания условий количество найденных решений будет сокращаться и если что-то останется – вы всегда сможете посмотреть какое именно условие нарушается.

  • #2889

    Tavasilyok
    Участник

    Спасибо за помощь, извините, что не в правильное место выложила вопрос

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