23650

Поиск списка реакций химического синтеза

Лабораторная работа

Информатика, кибернетика и программирование

Список элементарных химических реакций типа a b  i можно выразить в виде фактовпредикатов: rxn i[ab]. В целях упрощения представим в виде исходных фактов только эти необходимые реакции: rxn w [j r]. rxn j [c d]. rxn r [k l].

Русский

2013-08-05

145.5 KB

1 чел.

Лабораторная работа № 2

«Поиск списка реакций химического синтеза»

Задание №2.1. Поиск списка содействующих  реакций и используемых при этом веществ.

При химическом синтезе желаемый конечный продукт создается из более простых соединений, те в свою очередь  из еще более простых, и т. д., до тех пор, пока мы не дойдем до исходных элементов или материалов.  Программа должна по указанной формуле конечного вещества сообщить пользователю список содействующих реакций, т. е. найти нужный путь в дереве реакций от исходных материалов до конечного продукта.

Список элементарных химических реакций  типа  a + b i  можно выразить в виде фактов-предикатов:

        rxn (i,[a,b]).

 Смысл факта: «Синтез i происходит из веществ a и  b». Кроме того, эту реакцию можно представить в виде фрагмента дерева с конъюнкцией вершин, поддерживающих  i:

                            

   

                               

                                                                                         b       

 С помощью таких фрагментов можно представить все дерево синтеза. Рассмотрим схему синтеза вещества  w  из более простых:

   

     

       

          

Здесь w создаётся из j и r,  j из c и d,  r из k и l, и т.д. Исходными являются широко распространенные простые вещества  c, d, e, f, b, которые не являются продуктами синтеза. Внутренние узлы дерева - продукты химических реакций. Полная БД может содержать сотни реакций. Из них надо выделить необходимые для синтеза  w. В целях упрощения представим в виде исходных фактов только эти необходимые реакции:

rxn (w, [j, r]).

rxn (j, [c, d]).

rxn (r, [k, l]).

rxn (k, [e, f]).

rxn (l, [e, b]).

Для разработки программы поиска всех содействующих реакций введем вначале понятие о прямых предшественниках.

        dpre(X, Y): -  rxn(X, R),  member(Y, R).

Правило означает, что вещество Y можно считать прямым предшественником X, если X получают из компонентов списка R, и Y является элементом списка R. Рекурсивное определение любого, в том числе непрямого предшественника:

pre(X, Y): -  dpre(X, Y).

pre(X, Y): -  dpre(X, Z),  pre(Z, Y).

Логический смысл первого предложения: Y - предшественник X, если Y является прямым предшественником X. Второе предложение определяет непрямых предшественников Х рекурсивно: Y -предшественник X, если у X существует прямой предшественник Z, и Y является предшественником Z.   

Теперь введём с помощью правила contrxn еще одно понятие - о содействующей реакции как реакции, в результате которой получается конечный продукт, или один из его предшественников:

        contrxn(Y, rxn (Y, X)):  -  rxn(Y, X).

        contrxn(Y, rxn (Z, X)): -  rxn(Z, X),  pre(Y, Z).

 По первому предложению реакция rxn(Y, X) является содействующей получению Y, если существует реакция прямого получения Y из веществ списка X.

Второе предложение правила утверждает, что реакция  rxn(Z, X) является содействующей получению Y, если существует реакция получения Z из списка веществ X, и Z является предшественником Y. Теперь синтез можно определить как список всех содействующих реакций, имеющих отношение к конечному продукту.

        synthes(Y, Z): -  findall(X,  contrxn(Y, X), Z).

Здесь Z- список всех содействующих получению Y реакций. Стандартный предикат findall многократно вызывает правило contrxn, пока не соберет в список Z все содействующие реакции X.

Ниже приведёны основные правила программы для определения списка содействующих реакций (полный текст содержится в файле lab2_1.pro).

clauses

  dpre(X, Y): -  rxn(X, R), member(Y, R).

  pre(X, Y): -  dpre(X, Y).

  pre(X, Y): -  dpre(X, Z),  pre(Z, Y).

  contrxn(Y, rxn(Y, X)): -  rxn(Y, X).

  contrxn(Y, rxn(Z, X)): -  rxn(Z, X),  pre(Y, Z).

  synthes(Y, Z): -  findall(X, contrxn(Y, X), Z).

           

            member(X, [X|Xs]).

            member(X, [Y|Ys]): - member(X, Ys).

Цель поиска: synthes(w, Z). Она должна привести к выводу списка Z всех содействующих получению w реакций , т. е. в данном случае всей исходной БД.

Самостоятельная часть работы

Объясните работу правил pre, dpre и member  с помощью трассировки программы, поставив цель типа pre(w, k). Напишите протокол.

Обратите внимание на то, как в  разделе domains описаны вложенные структуры (дальше они будут усложняться).

Напишите правило для вывода списка всех веществ (не реакций!), используемых при получении данного конечного продукта (т.е. всех предшественников).

Изучите работу программы synthes в режиме трассировки, чтобы суметь объяснить, как она работает.

Обратите внимание на работу правила member, которое может не только проверять наличие заданного элемента в списке, но и присваивать свободной переменной значение элемента списка.  

Задание №2.2. Поиск способа получения конечного продукта (списка последовательных реакций)

Список L последовательных реакций получения продукта Y можно найти,  используя правило,  цель которого syn(Y, L):

syn(Y, [ ]): -  rawmaterial(Y).

syn(Y, L): -  rxn(Y, [X1, X2]),  syn(X1, L1),  syn(X2, L2),

append(L1, L2, Q),  append([rxn(Y, [X1, X2])], Q, L).   

Первая строка означает, что если Y исходное вещество (сырой материал rawmaterial), то список реакций его синтеза L пуст. Это- условие окончания рекурсии. Во втором предложении syn утверждается, что можно найти список реакций L синтеза вещества Y, если решить более простые задачи: найти реакцию непосредственного получения Y из веществ X1 и X2; найти список веществ L1 и L2, необходимых для синтеза соответственно X1 и X2. Затем с помощью правила append объединить L1 и L2 в список Q, и наконец , для получения ответа , с помощью второго обращения к правилу  append поместить только что найденную реакцию высшего уровня в начало списка Q, в результате чего получится список реакций L.

  Правило syn рекурсивно вызывает само себя с новыми значениями аргумента Y (поиск идёт по данной ветви дерева в глубину), пока очередное вещество Y (например, «k», см.рис. к Заданию №2.1.) не станет опираться на исходные (сырые) материалы X1 и X2 (в данном случае это «e» и «f»), указанные в фактах rawmaterial в БД. Тогда в соответствии с первым предложением правила syn списки L1 и L2 пусты. С этого момента вступает в действие правило append, 1-ое обращение к которому объединяет 2 пустых списка L1 и L2 в список Q=[]. 2-ое обращение соединяет список, состоящий из одной реакции получения  последнего Y=k, а именно, [rxn(k,[e,f]], со списком Q=[ ]. Получается список L, состоящий из одной реакции [rxn(k, [e, f]] .Далее идёт возврат к реакции, 1-ым элементом которой был рассматриваемый Y (в нашем примере-«k»), т.е. к реакции rxn(r, [k, l]). Вторым ее элементом, согласно факту rxn, является «l». После аналогичных  процессов получим список, состоящий  из одной реакции получения l:   

        L = [rxn(l, [e, b])].

    Для рассматриваемой реакции более высокого уровня - получения «r» из «k» и «l» списки L1 и L2 содержат найденные реакции для k и l, и правило append после двойного применения даст список L=[[rxn(r, [k, l])], [rxn(k, [e, f])], [rxn(l, [e, b])]].

   Очевидно, рассматриваемый процесс возврата идёт к корню дерева, и приведёт в итоге к выводу всей последовательности реакций  получения корневого вещества (например, w). Полный текст программы содержится в файле lab2_2.pro.

Однако данная программа может работать только с бинарными реакциями, в то время как на практике вещество может синтезироваться из 3-х и более компонентов. Текст более универсальной программы содержится в файле lab2_2mm.pro. Ниже приведены основные правила и два примера протокола, без которых сложно понять, как работает программа с перекрестной рекурсией.

       

  syn(Y, []): - not(rxn(Y, _)).

  syn(Y, L): - rxn(Y, S),  synth(S, Q),  append([rxn(Y, S)], Q, L).

  

  synth([],L): - L = [ ].

  synth([Head|S], Q): - syn(Head, Q1),  synth(S, Q2), append(Q1, Q2, Q).

Рассмотрим два примера. Найти список реакций синтеза вещества w.

1.     
                        w

                                                   rxn(w, [a, b, c]).

                                                  Цель: syn(w, L)

              a         b         c

  

Интерпретатор находит среди предложений подходящее с именем цели syn. Это - второе предложение, и подставляет в его голову аргументы из цели, а в тело –  известный исходный факт. Далее идет вызов правила synth (сплошная линия; возврат значения – пунктир).

                                      

syn(w, L): - rxn(w, [a, b, c]), synth([a, b, c], Q), append([rxn(w, [a, b, c])], Q, L).

      

           

synth([a|b,c], Q):-  syn(a,  Q1),   synth (S1, Q2),  append (Q1,  Q2,  Q).

               S1

              

syn (a, [  ] ):-  not (rxn ( a, _)).

synth ( [b | c ],  Q2): - syn ( b, Q11),  synth ([c ], Q22), append (Q11, Q22, Q2).

syn (b, [  ] ): - not(rxn(b, _ )).

synth ([c |[  ] , Q22 ): -  syn (c, Q33), synth ([  ] , Q44), append(Q33, Q44, Q22).

syn (c, [  ]): - not(rxn(c, _  )).

synth ([  ],  Q44):  - Q44 = [  ].

С этого момента начинает работать правило append и идет обратный ход рекурсии.

append (Q33, Q44, Q22)  => append ([  ], [  ], [  ])  => Q22 = [  ].

Значение Q22 будет передано на предшествующий уровень.

append (Q11, Q22, Q2)  => append ([  ], [  ], [  ])  => Q2 = [  ].

Значение Q2 будет передано на предшествующий уровень.

append (Q1, Q2, Q)  => append ([  ], [  ], [  ])  => Q = [  ].

Значение Q будет передано на предшествующий уровень

append([rxn(w,[a,b,c])],Q,L) => append([rxn(w,[a,b,c])],[  ], ([rxn(w,[a,b,c])) => L= [rxn(w,[a,b,c])]

  1.  w                       rxn(w, [a, b, c ]).

                                                rxn(b, [d, e]).

               a      b       c

                   d    e                           Цель: syn(w, L)

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

syn(w, L): - rxn(w, [a, b, c]),  synth ([a, b, c], Q), append([rxn(w, [a,b,c])], Q,L).

                            

synth([a | b, c ], Q):  -  syn( a, Q1), synth(S1, Q2), append(Q1, Q2, Q).

                                           

        

syn(a, [  ]): - not(rxn(a, _ )).                              

                                                                 

         

synth([b|c], Q2): - syn(b, Q11), synth(c, Q22),  append(Q11, Q22, Q2).

                                        

                                       

syn(b, Q11): - rxn(b, [d, e]),  synth([d,e], Q3), append([rxn(b, [d, e])], Q3, Q11).

        

synth([d|e], Q3):  -  syn(d, Q33),  synth(e, Q44), append(Q33, Q44, Q3).

syn (d, [  ] ): - not(rxn(d, _)).

synth([e | [  ]],  Q44): -  syn(e, Q55),  synth([  ], Q66), append(Q55, Q66, Q44).

                                            

syn(e,[  ]): - not(rxn(e, _ )).                        

                                                                      

         

        

synth ([  ], Q66): - Q66 = [  ].

С этого момента вступает в действие правило append.

append(Q55, Q66, Q44)  => append([  ], [  ], [  ])  => Q44 = [  ]. Это значение передается на предшествующий уровень, заставляя срабатывать следующее правило append.

append(Q33, Q44, Q3) => append([  ], [  ], [  ])   => Q3=[  ].

append([rxn(b, [d, e])], Q3, Q11) => append([rxn(b, [d, e])], [  ], Q11)  => Q11 = [rxn(b, [d, e])).

 Это значение будет передано на предшествующий уровень (см. пунктир), и далее будет вызвано правило synth для вершины “с” (см. выше).

synth([c|[  ]], Q22):  - syn(c, Q32), synth([  ], Q42),  append(Q32, Q42, Q22).

                                                   

syn(c, [  ]): - not(rxn(c, _ )).

synth([  ], Q42): - Q42=[  ].

append(Q32, Q42, Q22) => append([  ], [  ], Q22)  => Q22 = [  ].  Это значение передается предикату synth(c, Q22) (см. 4-ую строку протокола). Далее работает правило append.

append(Q11, Q22, Q2) => append([rxn(b, [d, e])],  [  ],  Q2) => Q2 = [rxn(b, [d, e])]

append(Q1, Q2, Q) => append([  ], [rxn(b, [d, e])],  Q) => Q = [rxn(b, [d, e])]

append([rxn(w, [a, b, c])], Q, L) => append([rxn(w, [a, b, c])], [rxn(b, [d, e])] , L) =>

L= [(rxn(w, [a, b, c]), (rxn(b, [d, e])].

Самостоятельная часть работы

Объясните работу программы lab2_2 на примере БД из программы lab2_1, поставив цель syn(w, L), т.е.на том же дереве, которое использовалось в Задании 2.1.

Какие ограничения накладывает программа lab2_2?

Разберитесь с примерами протоколов работы программы lab2_2mm. Какими средствами достигается возможность работы с любым числом веществ, участвующих в реакции?

Задание №2.3. Выбор варианта химического синтеза по критерию допустимой стоимости.

 Для решения этой задачи необходимо ввести стоимостные оценки в виде дополнительных аргументов основных предикатов. Факты типа rawmaterial(d) изменятся и примут вид rawmaterial(d, С), где второй аргумент – число, характеризующее условную стоимость исходного материала d. Кроме того , каждая элементарная реакция в БД также имеет стоимость, поэтому вместо записи типа rxn(i,[a,b]) будем использовать запись rxn(path(i, [a, b]), С). Первым аргументом нового rxn является сложный объект path,  несущий информацию об используемых компонентах. Как видно, path взял на себя нагрузку прежнего предиката rxn. Второй аргумент С предиката  rxn выражает стоимость реакции path.

Таким образом, новый rxn объединяет путь получения продукта и стоимость реакции.  База данных может включать факты (реакции), допускающие альтернативные варианты синтеза одного и того же конечного продукта, например, w. В дереве реакций, изображенном на рисунке, имеется 2 варианта синтеза продукта w. На схеме около внутренних узлов указана в скобках стоимость реакции синтеза данного вещества.  Около терминальных узлов указана стоимость исходных материалов.

  

                                                                                                                     

                                                  

 

        Пользуясь деревом, Вы можете самостоятельно составить БД из двух групп фактов:

                          rawmaterial(d,7).

                          rawmaterial(f,3).

                          .  .   . . .

                          rawmaterial(b,1).

                         rxn(path(w, [p, q]), 2).

                         rxn(path(p, [n, m]), 1).

                          . . .

                         rxn(path(l, [e, b]), 2).

Общая стоимость синтеза складывается из стоимости исходных материалов плюс стоимость всех необходимых реакций синтеза. Например, стоимость синтеза w по левому поддереву составит 39 у.е., по правому - 28 у.е. Так как введя стоимостные оценки  мы изменили базисные факты, правило syn получит третий аргумент:

syn(Y, [], C): -  rawmaterial(Y, C).

syn(Y, L, CT): - rxn(path(Y, [X1, X2]), C),  syn(X1,L1,C1),

syn(X2, L2, C2),  CT=C+C1+C2,  append(L1, L2, Q),

append([rxn(path(Y, [X1, X2]), C)], Q, L).

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

        okaysyn(Y, syn(Y, L, CT),  Cutoff): - syn(Y, L, CT), CT < Cutoff.

 Запрос формируется в виде предиката okaysyn с указанием вместо Cutoff конкретной допустимой стоимости синтеза, например,

        

        okaysyn(w, syn(w, L, CT), 30).

 

Если условие выполнено, программа выводит список реакций синтеза и стоимость.                 Ввиду общности БД и многих предложений текста программ для Задания № 2.3 и последующего Задания № 2.4, позволяющего осуществить поиск синтеза по критерию минимальной стоимости, в приложении на дискете приведена единая программа lab2_34, к разным частям которой модно обращаться, задавая различные цели поиска.         Обратите внимание на разделы domains и predicates описания сложных объектов, используемых в программе.

Самостоятельная часть работы

  •    Объясните, как подсчитывается суммарная стоимость пути в дереве реакций синтеза вещества.
  •    Изобразите граф по приведенной в программе lab2_34 фактам. Задайте различные цели, например, okaysyn(p, L, 25). Как в итоговой стоимости учтена стоимость реакции rxn(path(n, [d, d]), 1)?
  •     Подберите в цели  okaysyn(w, L,  CT) такую стоимость СТ, чтобы стали возможны оба варианта синтеза. w.
  •     Какой недостаток имеет программа в сравнении с предыдущей и можно ли его устранить?

Задание №2.4. Выбор варианта химического синтеза по критерию минимальной стоимости.

    Для решения этой задачи надо найти способ объединения всех вариантов синтеза данного продукта в один список, а затем выбрать из него вариант с минимальной стоимостью. Задачу объединения в один список может решить предикат findall, но для этого сложный объект syn(Y, L, CT), где Y- конечный продукт, L- список всех реакций его получения, СТ - стоимость синтеза, следует превратить в один из аргументов вспомогательного предиката onesyn с помощью правила:

        onesyn(Y, syn(Y, L, CT)): -  syn(Y, L, CT).

      Теперь правило allsyn сможет собрать в список списков X все варианты списков реакций синтеза конечного продукта Y, оперируя со сложным аргументом S = syn(Y, L, CT):

        allsyn(Y, X): -  findall(S, onesyn(Y, S), X).

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

        bestsyn(Y, Z): -  allsyn(Y, X), min(X, Z).

Здесь Y – синтезируемое вещество, Z – искомый список реакций его синтеза, удовлетворяющий из двух возможных в данном случае вариантов критерию наименьшей стоимости.

 Правило min находит в списке вариантов синтеза заданного вещества вариант Z по критерию наименьшей стоимости CT.

       Правило поиска списка реакций синтеза по минимальной  стоимости:

min([syn(Y, L, CT)],  syn(Y, L, CT).

min([syn(Y, L, CT]|T],  syn(Y, L, CT)): - min(T, syn(Y, L1, C1)), CT <= C1,!.

min([syn(Y, L, CT]|T],  syn(Y, L2, C2)): - min(T, syn(Y, L2, C2)), C2 <= CT,!.

        

Чтобы лучше понять работу этого правила, ниже приведён его упрощённый вариант (с простыми элементами списка, например, с числами). Полный текст этой программы содержится в файле min.pro.

min([X],X).

min([H1|T],H1):-min(T,H2), H1<=H2,!.

min([H1|T],H2):-min(T,H2), H2<H1,!.

        Если в списке один элемент, то он является минимальным. Это условие окончания рекурсии. Второе и третье предложения являются рекурсивными правилами нахождения минимума списка (1-й аргумент – текущий список, 2-й - его минимум). Логический смысл 2-го предложения: головной элемент списка H1 является минимумом, если минимум  хвоста есть H2, и выполняется условие H1 <= H2. Если условие не выполнено, рассматривается третье предложение. Смысл третьего предложения:  минимумом  списка является H2, если H2 есть минимум хвоста, и H2 < H1.  Обратите внимание на знаки отсечки хвостовой рекурсии (!) в конце 2-го и 3-го предложений. При их наличии поиск заканчивается  за 53 шага, если в списке 4 элемента. Если убрать отсечку, то программа сделает более 150 шагов за счет излишней хвостовой рекурсии. Еще быстрее отыскивает минимум другая программа,  которая содержится в файле minst.pro:

domains

 cost = integer

 list = cost*

predicates

 minst(list, cost)

 min(cost, list, cost)

clauses

 minst([H|T], M): - min(H, T, M),!.

 min(M, [], M).

 min(Y, [Y1|T], M): - Y > Y1,  min(Y1, T, M).

 min(Y, [Y1|T],  M): - Y <= Y1,  min(Y, T, M).

Эта программ отыщет минимум в том же списке из 4-х элементов всего за 24 шага. Обратите внимание на знак отсечки в конце первого предложения, которым заканчивается фактический поиск минимума, хотя здесь хвостовая рекурсия и не столь велика, как в правиле min.

Самостоятельная часть работы

Объясните работу программы  с целью bestsyn(w, Z). Существуют ли варианты синтеза для других веществ в данном дереве?

Выполните трассировку программ min.pro и minst.pro для поиска минимума в списке чисел [5, 3, 1, 2].

Перейдите теперь к объяснению поиск минимума стоимости в основной программе.

 


i

 a

w

r

    j

l

  k

d

   c

b

e

f

   e

w(3)

w(2)

r(1)

q(1)

p(1)

l(2)

j(1)

 n(1)

k(2)

 i(2)

m(2)

b(1)

c(3)

f(3)

e(3)

d(7)

c(2)

d(7)

d(7)

f(3)

a(1))

a(1)

b(1)


 

А также другие работы, которые могут Вас заинтересовать

11827. Указатели и ссылки. Имя массива как указатель. Динамические массивы 220.5 KB
  Лабораторная работа №7. Указатели и ссылки. Имя массива как указатель. Динамические массивы 1 Цель и порядок работы Цель работы – изучить работу с указателями ссылками получить навыки программирования с использованием динамических массивов. Порядок выполнения ра...
11828. Лабораторная работа №8. Функции 175.5 KB
  Лабораторная работа №8. Функции 1 Цель и порядок работы Цель работы – изучить возможности языка по организации функций получить практические навыки в составлении программ с их использованием. Порядок выполнения работы: ознакомиться с описанием лабораторной ...
11829. Отладка программ в интегрированной среде Microsoft Visual C++ 2008 189.5 KB
  Лабораторная работа №9. Отладка программ в интегрированной среде Microsoft Visual C 2008 1 Цель и порядок работы Цель работы – изучить инструментальные средства и возможности отладки программ в интегрированной среде Microsoft Visual C 2008 Visual Studio 2008. Порядок выполнения работы...
11830. Типы данных, определяемые пользователем. Структуры и объединения 189.5 KB
  Лабораторная работа №10. Типы данных определяемые пользователем. Структуры и объединения 1 Цель и порядок работы Цель работы – ознакомиться с типами данных определяемыми пользователем и их применением в процессе программирования. Порядок выполнения работы: ...
11831. Работа со строками в C++. Потоки ввода-вывода. Файловые операции 338.5 KB
  Лабораторная работа №11. Работа со строками в C. Потоки вводавывода. Файловые операции 1 Цель и порядок работы Цель работы – ознакомиться с возможностями вводавывода языка C освоить основные операции работы со строками и файлами. Порядок выполнения работы: о...
11832. Перегрузка функций. Шаблоны функций 152.5 KB
  Лабораторная работа №12. Перегрузка функций. Шаблоны функций 1 Цель и порядок работы Цель работы – ознакомиться с возможностью перегрузки функций и научиться применять полученные знания на практике. Научиться использовать шаблоны функции и функции с переменным количе...
11833. Модули. Многофайловые проекты 227 KB
  Лабораторная работа №13. Модули. Многофайловые проекты 1 Цель и порядок работы Цель работы – ознакомиться с возможностью работы с многофайловыми проектами в среде разработки Visual Studio и научиться применять полученные знания при создании собственных модулей. Порядок...
11834. ВИЗНАЧЕННЯ КОЕФІЦІЄНТА ФІЛЬТРАЦІЇ ГРУНТУ 326.5 KB
  ВИЗНАЧЕННЯ КОЕФІЦІЄНТА ФІЛЬТРАЦІЇ ГРУНТУ Визначення коефіцієнта фільтрації грунту. Методичні вказівки до лабораторної роботи № 16 з дисциплін Гідравліка відкритих русел Гідрологія та гідрометрія Гідравліка гідрологія гідрометрія для студентів базових напрямів...
11835. Визначення коефіцієнта витрати при витіканні рідини через зовнішні насадки 546.5 KB
  Визначення коефіцієнта витрати при витіканні рідини через зовнішні насадки. Методичні вказівки до лабораторної роботи № 7 з дисциплін Технічна механіка рідин та газів Гідрогазодинаміка Гідравліка гідро та пневмоприводи для студентів базових напрямів Водні рес...