Лекция
Привет, мой друг, тебе интересно узнать все про задачи логического вывода, тогда с вдохновением прочти до конца. Для того чтобы лучше понимать что такое задачи логического вывода, logic puzzle , настоятельно рекомендую прочитать все из категории Представление и использование знаний.
Есть головоломка, которую придумал А. Эйнштейн. Он утверждал, что эту задачу способны решить лишь 2% людей. Там же сказано, что 2% людей решают эту задачу примерно за это же время подобию своих мыслей создал алгоритм, а затем и саму программу на ПРОЛОГе, решающую такую задачу. Создание программы заняло целый день. Зато решение она выдавала за 0,5 секунд!
Этот тип задач называется задачей логического вывода (logic puzzle) или задачей на логику (logic problem), и обычно решается с помощью логического программирования или ручного логического вывода. В таких задачах требуется найти решение, основываясь на наборе правил и ограничений, которые обычно представлены в форме логических утверждений.
Условия задачи.
1. Есть 5 домов каждый разного цвета.
2. В каждом доме живет один человек, отличающийся от соседнего по национальности: немец, англичанин, швед, датчанин, норвежец.
3. Каждый пьет только один определенный напиток, курит определенную марку сигарет и держит определенное животное.
4. Никто из 5 человек не пьет одинаковые с другими напитки, не курит одинаковые сигареты и не держит одинаковое животное.
Вопрос: кому принадлежит рыба?
Подсказки:
1. Англичанин живет в красном доме.
2. Швед держит собаку.
3. Датчанин пьет чай.
4. Зеленый дом стоит слева от белого.
5. Жилец зеленого дома пьет кофе.
6. Человек, который курит Pall Mall, держит птицу.
7. Жилец из среднего дома пьет молоко.
8. Жилец из желтого дома курит Dunhill.
9. Норвежец живет в первом доме.
10. Курильщик Marlboro живет около того, кто держит кошку.
11. Человек, который держит лошадь, живет около того, кто курит Dunhill.
12. Курильщик сигарет Winfield пьет пиво.
13. Норвежец живет около голубого дома.
14. Немец курит Rothmans.
15. Курильщик Marlboro живет по соседству с человеком, который пьет воду.
Ниже приводится программа для решения головоломки.
альтернативы
Для решения головоломки "Who has a fish?" необходимо учитывать следующие факты:
Исходя из этих фактов, можно прийти к следующим выводам:
Итак, чтобы ответить на головоломку "Who has a fish?", можно сделать вывод, что рыбку имеет Мэри.
Решение головоломок подобного типа может быть выполнено путем логического вывода, основанного на фактах, предоставленных в условии задачи. Для этого используются правила и ограничения, которые определяют возможные варианты ответов и исключают неверные варианты.
Обычно решение головоломок такого типа начинается с анализа фактов, предоставленных в условии задачи, и выявления связей между ними. Затем на основе этих связей формулируются правила и ограничения, которые определяют возможные варианты ответов.
Для решения головоломки "Who has a fish?" можно использовать метод логического вывода с применением правил и ограничений. Как правило, такие головоломки решаются методом исключения. То есть из всех возможных вариантов ответов, постепенно исключаются те, которые противоречат фактам, которые даны в условии.
В данном конкретном примере, мы начали с анализа фактов и выяснили, что у каждого из четырех человек может быть только одно животное. Затем мы использовали эти факты, чтобы сформулировать правила и ограничения, которые позволили нам исключить неверные варианты ответов и прийти к правильному ответу.
пример решения головоломки кто имеет рыбу? (Who has a fish?) есть пять разноцветных домов, в которых живут разные люди, которые пьют разные напитки и которые имеют разных животных и которые курят разные сигареты. нужно ответить на вопрос имея 15 подсказок Кто имеет рыбу? Здесь приведен способ ускоренного поиска решения.
domains
Цвет = желтый; голубой; красный; зеленый; белый
НомерДома = первый; второй; третий; четвертый; пятый
% reference - здесь указывает на возможность работы с неопределенными значениями
ПризнакДома= reference признак(Цвет, НомерДома)
Национальность = норвежец; датчанин; англичанин; немец; швед
Напиток = вода; чай; молоко; кофе; пиво
Сигареты = dunhill; marlboro; pall_mall; rothmans; winfield
Животное = кот; лошадь; птица; рыба; собака
Дом = reference дом(ПризнакДома, Национальность, Напиток, Сигареты, Животное)
Дома = reference Дом*
Значение = ц(Цвет); нд(НомерДома); нц(Национальность);
нп(Напиток); сг(Сигареты); жв(Животное)
Значения = Значение*
predicates
nondeterm цвет(Цвет)
nondeterm национальность(Национальность)
nondeterm напиток(Напиток)
nondeterm сигареты(Сигареты)
nondeterm животное(Животное)
nondeterm дом(Номер, ПризнакДома, Национальность, Напиток, Сигареты, Животное)
nondeterm дом_наобум(ПризнакДома, Национальность, Напиток, Сигареты, Животное)
nondeterm условие(Номер, Дом,Дома)
условия_не_нарушены(Номер, Дом,Дома)
% без учета "слева"-"справа"
nondeterm дома_рядом(Дома,Дом, Дом Рядом)
% с учетом "слева"-"справа"
nondeterm дома_прилегают(Дома,Дом, Дом Рядом)
nondeterm рядом(НомерДома, НомерДома)
nondeterm прилегает(НомерДома Слева, НомерДома Справа)
дом_неуникален1(Дом, Дом)
дом_неуникален(Дом, Дома)
сверить_значения(Дом, Значения, Дом, Значения)
значение_связано(Значение)
clauses
% определение возможных значений
% явное определение помогает на этапе отладки
% отловить ошибки в значениях
цвет(желтый). цвет(голубой). цвет(красный). цвет(зеленый). цвет(белый).
национальность(норвежец). национальность(датчанин).
национальность(англичанин). национальность(немец). национальность(швед).
напиток(вода). напиток(чай). напиток(молоко). напиток(кофе). напиток(пиво).
сигареты(dunhill). сигареты(marlboro). сигареты(pall_mall).
сигареты(rothmans). сигареты(winfield).
животное(кот). животное(лошадь). животное(птица).
животное(рыба). животное(собака).
%
% основные условия задачи
%
%1. в красном доме живет англичанин.
дом(1,признак(красный,_),англичанин,_,_,_).
%2. швед содержит собаку.
дом(2,_,швед,_,_,собака).
%3. датчанин пьет чай.
дом(3,_,датчанин,чай,_,_).
%5. жилец зеленого дома пьет кофе.
дом(5,признак(зеленый,_),_,кофе,_,_).
%6. тот кто курит Pall Mall содержит птицу.
дом(6,_,_,_,pall_mall,птица).
%7. кто живет в среднем (третьем) доме пьет молоко.
дом(7,признак(_,третий),_,молоко,_,_).
%8. Об этом говорит сайт https://intellect.icu . тот кто живет в желтом доме курит Dunhill.
дом(8,признак(желтый,_),_,_,dunhill,_).
%9. в первом доме живет норвежец.
дом(9,признак(_,первый),норвежец,_,_,_).
%12 курильщик сигарет Winfield пьет пиво.
дом(12,_,_,пиво,winfield,_).
%14 германец курит Rothmans.
дом(14,_,немец,_,rothmans,_).
% это условие - что можно взять любое значение - если оно еще не связано
дом_наобум(признак(Цвет,_),Нац,Нап,Сиг,Жив):-
цвет(Цвет),национальность(Нац),
напиток(Нап),сигареты(Сиг),животное(Жив).
% условия-зависимости, здесь проверка делается сразу для обоих домов
%4. зеленый дом находится слева от белого
условие(4,ДомЗеленый,Дома):-
ДомЗеленый=дом(признак(зеленый,_),_,_,_,_),
not(дом_неуникален(ДомЗеленый,Дома)),
дома_прилегают(Дома,ДомЗеленый,ДомБелый),
ДомБелый=дом(признак(белый,_),_,_,_,_),
not(дом_неуникален(ДомБелый,Дома)).
%10. тот, кто курит Marlboro живет рядом с тем, кто содержит кота.
условие(10,Дом,Дома):-Дом=дом(_,_,_,marlboro,_),
not(дом_неуникален(Дом,Дома)),
дома_рядом(Дома,Дом,ДомРядом),
ДомРядом=дом(_,_,_,_,кот),
not(дом_неуникален(ДомРядом,Дома)).
%11. тот кто имеет лошадь живет рядом с тем кто курит Dunhill.
условие(11,Дом,Дома):-Дом=дом(_,_,_,_,лошадь),
not(дом_неуникален(Дом,Дома)),
дома_рядом(Дома,Дом,ДомРядом),
ДомРядом=дом(_,_,_,dunhill,_),
not(дом_неуникален(ДомРядом,Дома)).
%13 норвежец живет рядом с голубым домом.
условие(13,Дом,Дома):-Дом=дом(_,норвежец,_,_,_),
not(дом_неуникален(Дом,Дома)),
дома_рядом(Дома,Дом,ДомРядом),
ДомРядом=дом(признак(голубой,_),_,_,_,_),
not(дом_неуникален(ДомРядом,Дома)).
%15 Курильщик Marlboro живет по соседству с человеком, который пьет воду.
условие(15,Дом,Дома):-Дом=дом(_,_,_,marlboro,_),
not(дом_неуникален(Дом,Дома)),
дома_рядом(Дома,Дом,ДомРядом),
ДомРядом=дом(_,_,вода,_,_),
not(дом_неуникален(ДомРядом,Дома)).
% условие для доступа к простым фактам
условие(Ном,Дом,Дома):-
дом(Ном,П,Нац,Нап,Сиг,Жив),
Дом=дом(П,Нац,Нап,Сиг,Жив),
not(дом_неуникален(Дом,Дома)).
%
% теперь условия для проверки правильности
%
% условия-зависимости, здесь проверка делается сразу для обоих домов
% здесь находится именно не выполненное условие
% так чтобы все условия проверялись
% 4. зеленый дом находится слева от белого
условия_не_нарушены(4,ДомЗеленый,Дома):-
ДомЗеленый=дом(признак(Цвет,_),_,_,_,_),
bound(Цвет),
Цвет=зеленый,
ДомБелый=дом(признак(белый,_),_,_,_,_),
not(дома_прилегают(Дома,ДомЗеленый,ДомБелый)),
!,fail.
%10. тот, кто курит Marlboro живет рядом с тем, кто содержит кота.
условия_не_нарушены(10,Дом,Дома):-Дом=дом(_,_,_,Сиг,_),
bound(Сиг),
Сиг=marlboro,
ДомРядом=дом(_,_,_,_,кот),
not(дома_рядом(Дома,Дом,ДомРядом)),
!,fail.
%11. тот кто имеет лошадь живет рядом с теем кто курит Dunhill.
условия_не_нарушены(11,Дом,Дома):-Дом=дом(_,_,_,_,Жив),
bound(Жив),
Жив=лошадь,
ДомРядом=дом(_,_,_,dunhill,_),
not(дома_рядом(Дома,Дом,ДомРядом)),
!,fail.
%13 норвежец живет рядом с голубым домом.
условия_не_нарушены(13,Дом,Дома):-Дом=дом(_,Нац,_,_,_),
bound(Нац),
Нац=норвежец,
ДомРядом=дом(признак(голубой,_),_,_,_,_),
not(дома_рядом(Дома,Дом,ДомРядом)),
!,fail.
%15 Курильщик Marlboro живет по соседству с человеком, который пьет воду.
условия_не_нарушены(15,Дом,Дома):-Дом=дом(_,_,_,Сиг,_),
bound(Сиг),
Сиг=marlboro,
ДомРядом=дом(_,_,вода,_,_),
not(дома_рядом(Дома,Дом,ДомРядом)),
!,fail.
% проверка для простых условий-фактов
условия_не_нарушены(0,Дом,_):-
% взять значения проверяемого Дома
Дом=дом(признак(Цвет,Номер),Нац,Нап,Сиг,Жив),
% взять значения условия-факта
дом(_,признак(Цвет1,Номер1),Нац1,Нап1,Сиг1,Жив1),
% если значения из одного списка связаны и
% из другого тоже - то они должны быть равны
% иначе условие на соблюдается
not(сверить_значения(
Дом,
[ц(Цвет),нд(Номер),нц(Нац),нп(Нап),сг(Сиг),жв(Жив)],
дом(признак(Цвет1,Номер1),Нац1,Нап1,Сиг1,Жив1),
[ц(Цвет1),нд(Номер1),нц(Нац1),нп(Нап1),сг(Сиг1),жв(Жив1)])
),
!,fail.
% если пришло сюда, значит
% все условия выполнены
условия_не_нарушены(0,_,_):-!.
значение_связано(ц(Знач)):-bound(Знач),!.
значение_связано(нд(Знач)):-bound(Знач),!.
значение_связано(нц(Знач)):-bound(Знач),!.
значение_связано(нп(Знач)):-bound(Знач),!.
значение_связано(сг(Знач)):-bound(Знач),!.
значение_связано(жв(Знач)):-bound(Знач),!.
% проверка связей в простых условиях-фактах
сверить_значения(Дом,[Что|_],Дом1,[Что1|_]):-
значение_связано(Что),
значение_Связано(Что1),
Что=Что1,
% если что-то совпало, то и все остальное должно совпасть
!, % поэтому здесь запрет отката стоит
Дом=Дом1,
!.
сверить_значения(Дом,[_|Ост],Дом1,[_|Ост1]):-
% взять следующую пару значений
сверить_значения(Дом,Ост,Дом1,Ост1),
!.
сверить_значения(_,[],_,[]):-
% сравнение успешно
!.
% не сравнивать с самим собой
дом_неуникален1(дом(признак(_,Номер1),_,_,_,_),
дом(признак(_,Номер2),_,_,_,_)):-Номер1=Номер2,
!,fail.
% если оба значения связаны и равны
дом_неуникален1(дом(признак(Что,_),_,_,_,_),дом(признак(Что1,_),_,_,_,_)):-
bound(Что),bound(Что1),Что=Что1,
!.
дом_неуникален1(дом(_,Что,_,_,_),дом(_,Что1,_,_,_)):-
bound(Что),bound(Что1),Что=Что1,
!.
дом_неуникален1(дом(_,_,Что,_,_),дом(_,_,Что1,_,_)):-
bound(Что),bound(Что1),Что=Что1,
!.
дом_неуникален1(дом(_,_,_,Что,_),дом(_,_,_,Что1,_)):-
bound(Что),bound(Что1),Что=Что1,
!.
дом_неуникален1(дом(_,_,_,_,Что),дом(_,_,_,_,Что1)):-
bound(Что),bound(Что1),Что=Что1,
!.
%
% проверка на условие уникальности: всех значения дома
% должны быть уникальны
%
дом_неуникален(Дом,[ДомДругой|_]):-
дом_неуникален1(Дом,ДомДругой),
!.
дом_неуникален(Дом,[_|Дома]):-
дом_неуникален(Дом,Дома),
!.
% определение общих правил расположения домов
рядом(Место,Рядом):-прилегает(Место,Рядом).
рядом(Место,Рядом):-прилегает(Рядом,Место).
прилегает(первый, второй).
прилегает(второй, третий).
прилегает(третий,четвертый).
прилегает(четвертый,пятый).
% определение дома рядом с данным без учета лево-право
дома_рядом([ДомРядом|_],дом(признак(_,Место),_,_,_,_),ДомРядом):-
ДомРядом=дом(признак(_,Рядом),_,_,_,_),
рядом(Место,Рядом).
дома_рядом([_|Дома],Дом,ДомРядом):-
дома_рядом(Дома,Дом,ДомРядом),
!.
% определение дома рядом с данным с учетом лево-право
дома_прилегают([ДомРядом|_],дом(признак(_,Место),_,_,_,_),ДомРядом):-
ДомРядом=дом(признак(_,Рядом),_,_,_,_),
прилегает(Место,Рядом).
дома_прилегают([_|Дома],Дом,ДомРядом):-
дома_прилегают(Дома,Дом,ДомРядом),
!.
predicates
все_связано1(Дом)
все_связано(Дома)
не_связано1(Дом)
nondeterm не_связано(Дома,Дом)
clauses
все_связано1(дом(П,Н,Нап,Сиг,Ж)):-bound(П),bound(Н),bound(Нап),
bound(Сиг),bound(Ж),!.
% все ли решено?
все_связано([Дом|Дома]):-
!,
все_связано1(Дом),
все_связано(Дома),
!.
все_связано([]):-!.
не_связано1(дом(признак(Что,_),_,_,_,_)):-free(Что),!.
не_связано1(дом(_,Что,_,_,_)):-free(Что),!.
не_связано1(дом(_,_,Что,_,_)):-free(Что),!.
не_связано1(дом(_,_,_,Что,_)):-free(Что),!.
не_связано1(дом(_,_,_,_,Что)):-free(Что),!.
% найти Дом у которого есть несвязанные значения
не_связано([Дом|_],Дом):-
не_связано1(Дом).
не_связано([_|Дома],Дом):-
не_связано(Дома,Дом).
predicates
nondeterm выбрать_явную_связь(Номер)
nondeterm решить2(Дом,Дома, Номер)
все_условия_использованы(Номера, Дома)
nondeterm запомнить_выбор(Дом,Дома)
условие_обработано(Номер,Номера)
nondeterm решить1(Дома, Номера)
nondeterm дорешить(Дома)
решить(Дома)
clauses
% выбрать такие условия и связи - которые явно
% следуют из текущих данных и условий
% это ускоряет решение
выбрать_явную_связь(Ном):-
условие(Ном,Дом,[]),
Дом=дом(признак(_,Номер),_,_,_,_),
% если произошло связывание номера, значит явная!
bound(Номер).
% если некое условие сработало,
% то нужно его результат запомнить в общем списке
запомнить_выбор(Дом,[Дом|_]).
запомнить_выбор(Дом,[_|Дома]):-
запомнить_выбор(Дом,Дома).
% проверяет, было ли уже такое условие обработано
условие_обработано(Ном,[Ном|_]):-!.
условие_обработано(Ном,[_|Обработаны]):-
условие_обработано(Ном,Обработаны),
!.
% выбор условий
решить2(Дом,ВсеДома,Ном):-
% для ускорения решения - выбор наиболее лучшего условия.
% с использованием этого предиката выполнение идет менее 0,5 секунды,
% без этого предиката - время выполнения на ПОРЯДКИ больше!
выбрать_явную_связь(Ном),
условие(Ном,Дом,ВсеДома).
решить2(Дом,ВсеДома,Ном):-
% перебор всех условий
условие(Ном,Дом,ВсеДома).
% проверка - все ли условия использованы
все_условия_использованы(Обработано,Дома):-
условие(Номер,_,Дома),
not(условие_обработано(Номер,Обработано)),
!,fail.
все_условия_использованы(_,_):- !.
% применяет все условия задачи и выдает полученный
% результат для дальнейшего связывания
решить1(ВсеДома,Обработано):-
% если все правила использованы, то выход и выдать результат
% для дальнейшего подбора наобум
все_условия_использованы(Обработано,ВсеДома),
!.
решить1(ВсеДома,Обработаны):-
% использовать условие задачи
решить2(Дом,ВсеДома,Ном),
% это условие еще не обрабатывалось
not(условие_обработано(Ном,Обработаны)),
% запомним результат применения условия
% здесь если ниже будет откат, то присвоение
% может быть сделано для других домов
запомнить_выбор(Дом,ВсеДома),
% если дом уникальный
not(дом_неуникален(Дом,ВсеДома)),
% и не другие нарушены условия задачи
условия_не_нарушены(_,Дом,ВсеДома),
% то идем дальше
решить1(ВсеДома,[Ном|Обработаны]).
% оставшиеся несвязанные значения свяжем на основании
% условия, что значения не должны повторяться
% то есть можно взять любое возможное значение
% и вставить его, если не нарушены условия задачи
дорешить(ВсеДома):-
% взять дом, у которого есть несвязанное значение
не_связано(ВсеДома,Дом),
Дом=дом(П,Н,Нап,Сиг,Жив),
% выбрать это значение наобум
дом_наобум(П,Н,Нап,Сиг,Жив),
% проверим условие уникальности
not(дом_неуникален(Дом,ВсеДома)),
% и при этом все условия задачи верны
условия_не_нарушены(_,Дом,ВсеДома),
% искать другое несвязанное значение
дорешить(ВсеДома).
дорешить(Дома):-
% если все уже решено (связано), то выход
все_связано(Дома),
!.
решить(Дома):-
Дома=[дом(признак(_,первый),_,_,_,_),
дом(признак(_,второй),_,_,_,_),
дом(признак(_,третий),_,_,_,_),
дом(признак(_,четвертый),_,_,_,_),
дом(признак(_,пятый),_,_,_,_)],
% обработка условий
% здесь все условия должны быть выполнены (применены)
решить1(Дома,[]),
% оставшиеся несвязанные значения нужно
% связать наобум с проверкой на условия
дорешить(Дома),
!.
Goal:-
marktime(0,T1),
решить(Дома),
marktime(0,T2),
difftime(T2,T1,Тост),
nl,write(Дома,":",Тост).
Возможно, программа покажется Вам довольно навороченной, но именно такие действия совершает человек при решении этой головоломки.
К сожалению, для решения головоломки "Who has a fish?" необходимы некоторые особенности, которые не могут быть выполнены с помощью обычного программирования, например, логическое программирование. Однако, для решения подобных задач на языке логического программирования Prolog, можно написать следующий код:
% Определяем возможные животные и людей
animal(dog).
animal(cat).
animal(bird).
animal(fish).
person(john).
person(mary).
person(peter).
person(susan).
% Определяем факты о том, кто какое животное имеет
has(john, dog).
has(mary, cat).
has(peter, bird).
has(susan, fish).
% Определяем правило для решения головоломки
solve(X) :-
person(X), % X - это человек
has(X, Y), % X имеет животное Y
animal(Y), % Y - это животное
not((has(Z, Y), Z \= X)). % нет других людей, имеющих животное Y
После запуска этого кода и вызова предиката solve(X), система Prolog вернет ответ, указывающий, кто из четырех людей имеет рыбу. В данном случае ответом будет susan, так как она единственная имеет рыбу.
Если я не полностью рассказал про задачи логического вывода? Напиши в комментариях Надеюсь, что теперь ты понял что такое задачи логического вывода, logic puzzle и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Представление и использование знаний
Комментарии
Оставить комментарий
Представление и использование знаний
Термины: Представление и использование знаний