Существует 2 основных подхода к решению логических задач: метод порождения и проверок и метод ветвей и границ. Они оба перебирают некоторый набор решений. Суть первого метода состоит в том, что некоторый предикат генерирует множество исходных данных, которые затем проверяются другими предикатами на предмет соответствия условию задачи. В случае неуспеха происходит возврат и рассмотрение следующего решения, в случае успеха полученное решение возвращается пользователю или используется дальше. Второй метод можно противопоставить первому. В методе ветвей и границ значительные части возможных решений отсекаются на раннем этапе выполнения или вообще не генерируются. Например, можно использовать предикат member одновременно для генерации и для проверки, таким образом генерируются не все варианты решений, а какое-то их подмножество. Очевидно, что программа, написанная с помощью второго метода, будет работать быстрее.
Пролог удобен для решения логических задач, потому что он дает возможность рассмотрения большого количества вариантов решения задачи и выбора из них подходящих. Механизм бэктрекинга при обнаружении неуспеха автоматически пересматривает решение и вытается продолжить выполнение программы при других значениях переменных.
- На одном международном конгрессе встретились 4 делегата из разных стран. Каждый из них владел двумя языками из 4 (английский, французский, немецкий, итальянский). Однако, оказалось, что не было такого языка, на котором они могли бы говорить вчетвером. И был только один язык, на котором могли вести беседу трое из них. Никто из делегатов не владеет французским и немецким языками одновременно. Хотя физик не говорит по-английски, он может служить переводчиком, если математик и биолог захотят поговорить друг с другом. Биолог говорит по-немецки и может говорить с химиком, хотя тот не знает ни одного немецкого слова. Физик, математик и химик не могут беседовать втроем на одном языке. Какими двумя языками владеет каждый из них?
Главный предикат main. Есть список делегатов -- физик (Phys), математик (Math), биолог (Bio), химик (Chem). Каждому делегату ставим в соответствие предикат del, который проверяет, являются ли аргументы языками. Каждый делегат характеризуется 2 языками, которые он знает. Генерируем список Dels, который содержит всех делегатов. Языки перебираем по очереди, причем если это один и тот же язык, то такой вариант не проверяем (в коде это Lan11 @< Lan12 и проч). Используем оператор @<, a не == (перед == стоит обратный слеш, но он почему-то не отображается в md), чтобы не генерировались варианты del(french,german), а потом del(german,french) из-за чего единственное решение будет выдаваться 2^4 раз. Когда список сформирован, проверяем условия задачи для данного списка.
Условие "не было такого языка, на котором они могли бы говорить вчетвером" отражено в предикате common_lan.
common_lan([Del1, Del2, Del3, Del4]):-
speak(Del1, L), speak(Del2, L), speak(Del3, L), speak(Del4, L).С помощью предиката speak проверяем, говорят ли на языке L все 4 делегата. Если этот язык входит в предикат del, поставленный в соответствие делегату, то возвращается успех, иначе неуспех.
speak(del(L, _), L).
speak(del(_, L), L).В главном предикате main проверяем отрицание получившегося ответа.
not(common_lan(Dels)),Условие "и был только один язык, на котором могли вести беседу трое из них" отражено в предикатах lan_for_3 и lan_for_3_optional. В первом предикате проверяем, что существует язык, который общих для 3 делегатов. Для всех троек делегатов проверяем, есть ли у них общий язык. Во втором предикате проверяем, что такой язык только один.
lan_for_3([Del1, Del2, Del3,_], L):-
speak(Del1, L), speak(Del2, L), speak(Del3, L).
lan_for_3([Del1, Del2,_, Del4], L):-
speak(Del1, L), speak(Del2, L), speak(Del4, L).
lan_for_3([Del1,_, Del3, Del4], L):-
speak(Del1, L), speak(Del3, L), speak(Del4, L).
lan_for_3([_, Del2, Del3, Del4], L):-
speak(Del2, L), speak(Del3, L), speak(Del4, L).
lan_for_3_optional([Del1, Del2, Del3, Del4], L):-
lan_for_3([Del1, Del2, Del3, Del4], L1), L1 \== L.Условие "никто из делегатов не владеет французским и немецким языками одновременно" отражено в main. Не нужно проверять условие, содержащее del(german, french), потому что мы не генерируем списки, в которых терм french идет после терма german.
not(member(del(french, german), Dels)),Условие "физик не говорит по-английски" отражено в main.
not(speak(Phys,english)),Условие "он [физик] может служить переводчиком, если математик и биолог захотят поговорить друг с другом" отражено в предикате math_and_bio_speaks и в main. Т.е. математик и биолог не имеют общего языка.
math_and_bio_speaks(Math, Bio):-
speak(Math, L), speak(Bio, L).В main вносим информацию о том, что физик и математик имеют общий язык, физик и биолог имеют общий язык, математик и биолог не имеют общего языка:
speak(Phys, LFM), speak(Math, LFM),
speak(Phys, LFB), speak(Bio, LFB),
not(math_and_bio_speaks(Math, Bio)),Условие "биолог говорит по-немецки" отражено в main.
speak(Bio,german),Условие "[биолог] может говорить с химиком, хотя тот не знает ни одного немецкого слова" отражено в main. Биолог и химик имеют общий язык и это не немецкий.
speak(Bio, LBH), speak(Chem, LBH),
not(speak(Chem, german)),Условие "физик, математик и химик не могут беседовать втроем на одном языке" отражено в предикате phys_math_chem_speaks(Phys, Math, Chem).
phys_math_chem_speaks(Phys, Math, Chem):-
speak(Phys, L), speak(Math, L), speak(Chem, L).Результат работы:
?- main([del(PhysLan1,PhysLan2),del(MathLan1,MathLan2),del(BioLan1,BioLan2),del(ChemLan1,ChemLan2)]).
PhysLan1 = MathLan2, MathLan2 = french,
PhysLan2 = BioLan2, BioLan2 = ChemLan2, ChemLan2 = italian,
MathLan1 = ChemLan1, ChemLan1 = english,
BioLan1 = german.Результатом работы моей программы является единственно верное непротиворечивое решение. Все условия задачи соблюдены. Моя программа эффективна, потому что я не проверяю дублирующиеся варианты решений, когда языки, которыми владеют делегаты, переставлены местами. Получается, что из 20 736 возможных решений (для каждого делегата можно выбрать 2 языка из 4 12-ю различными способами, если считать повторяющиеся комбинации, например английский-франзузский, французский-английский, делегатов 4), моя программа проверяет лишь 1 296 (по 6 возможных комбинаций языков для каждого делегата).
Пролог, безусловно, удобен для решения подобных задач. Описав ряд условий, мы отсекаем неподходящие варианты и находим нужное решение. Это намного проще, чем решать вручную, если бы мы, подобно программе, проверяли все возможные решения. Насколько эффективнее написание программы по сравнению с "ручным" решением вопрос спорный. Если такая задача одна и там немного входных данных, то проще решить ее на бумаге. На больших данных я все-таки предпочла бы написать программу. Сложно представить себе ситуацию, при которой пришлось бы решать большое количество таких задач. Также стоит отметить, что похожие по смыслу задачи решаются на Прологе механически -- мы просто меняем предикаты с условиями и генерацию. Думаю, если бы мы формализовали условие и написали все возможные проверки вообще (написание которых наверняка тоже можно как-то автоматизировать), то смогли бы решать целые классы таких задач.