. Есть брутто-формула молекулы, например C6H6. Нужно перебрать все осколки, и далее для каждого осколка перебрать все возможные связи в нём, чтобы проверить – можно ли расставить связи так, чтобы валентность водорода была всегда 1, а валентность углерода от 1 до 4. Т.е. c C6H6 можно сгенерировать осколок CH4 или H2, но нельзя CH5 или H3.
Я пока решил эту задачу в лоб. Для молекулы из n атомов строится массив n*(n-1)/2 – все возможные пары атомов. В массиве хранятся булевы значения, т.е. если true – значит эта связь есть. Программа перебирает все комбинации связей по алгоритму в теме по ссылке выше; если например в молекуле 10 атомов, то число возможных пар атомов будет 10*9/2=45, и число всех комбинаций 2^45. Для каждой комбинации программа проверяет текущую валентность всех атомов (попадает ли она в мои критерии). И даже для десятитомной молекулы ресурсов компьютера не хватает, чтобы всё перебрать.
Как оптимизировать этот алгоритм?
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.
. Есть брутто-формула молекулы, например C6H6. Нужно перебрать все осколки, и далее для каждого осколка перебрать все возможные связи в нём, чтобы проверить – можно ли расставить связи так, чтобы валентность водорода была всегда 1, а валентность углерода от 1 до 4. Т.е. c C6H6 можно сгенерировать осколок CH4 или H2, но нельзя CH5 или H3.
K>Я пока решил эту задачу в лоб. Для молекулы из n атомов строится массив n*(n-1)/2 – все возможные пары атомов. В массиве хранятся булевы значения, т.е. если true – значит эта связь есть.
Зачем так делать?
K>Программа перебирает все комбинации связей по алгоритму в теме по ссылке выше; если например в молекуле 10 атомов, то число возможных пар атомов будет 10*9/2=45, и число всех комбинаций 2^45.
???
K>Для каждой комбинации программа проверяет текущую валентность всех атомов (попадает ли она в мои критерии). И даже для десятитомной молекулы ресурсов компьютера не хватает, чтобы всё перебрать.
А что мешает рассчитывать использовать энергию связи атома, и по ней судить развалится или нет?
K>Как оптимизировать этот алгоритм?
Используйте кэш. Выстройте ваши осколки в виде дерева и используйте данные которые проанализированы.
Здравствуйте, Nuzhny, Вы писали:
K>>Как оптимизировать этот алгоритм?
N>Эта задача не похожа на шахматы? Минимак, альфа-бета — строить дерево вариантов и заранее отсекать то, что проверять не надо?
Наверно с шахматами сходство есть, но главное различие — в шахматах всех комбинаций всё равно не переберёшь и надо использовать эвристики, а тут надо именно всё перебрать и дать однозначный ответ.
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.
. Есть брутто-формула молекулы, например C6H6. Нужно перебрать все осколки, и далее для каждого осколка перебрать все возможные связи в нём, чтобы проверить – можно ли расставить связи так, чтобы валентность водорода была всегда 1, а валентность углерода от 1 до 4. Т.е. c C6H6 можно сгенерировать осколок CH4 или H2, но нельзя CH5 или H3.
K>>Я пока решил эту задачу в лоб. Для молекулы из n атомов строится массив n*(n-1)/2 – все возможные пары атомов. В массиве хранятся булевы значения, т.е. если true – значит эта связь есть. _>Зачем так делать?
Ну между каждой парой атомов может либо быть связь, либо не быть.
K>>Как оптимизировать этот алгоритм? _>Используйте кэш. Выстройте ваши осколки в виде дерева и используйте данные которые проанализированы.
Не понял пока.
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.
Здравствуйте, kov_serg, Вы писали:
K>>Для каждой комбинации программа проверяет текущую валентность всех атомов (попадает ли она в мои критерии). И даже для десятитомной молекулы ресурсов компьютера не хватает, чтобы всё перебрать. _>А что мешает рассчитывать использовать энергию связи атома, и по ней судить развалится или нет?
Это теоретический расчёт масс-спектра, надеюсь в будущем я смогу это тоже сделать. Тут надо реализовать свою квантовую химию...
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.
Здравствуйте, Khimik, Вы писали:
K>Ну между каждой парой атомов может либо быть связь, либо не быть.
У вас количество связей ограничено. Вообще за связь отвечает энергия связи что её мешает использовать?
_>>Используйте кэш. Выстройте ваши осколки в виде дерева и используйте данные которые проанализированы. K>Не понял пока.
Что не понятного у вас осколки иерархичны, более сложные состоят из более простых, можно построить дерево или хотя бы hash таблицу, что бы уже обсчитанные данные переиспользовать.
Это позволяет в рекурсивных алгоритмах очень сильно снизить вычислительную сложность.
Но если вы хотите собирать осколки в длинные полимеры, то вам скорее всего еще придётся учитывать вероятность канала и совсем мало вероятные выкидывать или оценивать по упрощенной схеме.
Т.к. перебрать всё фазовое пространство не возможно, его надо ограничивать и переиспользовать информацию которая получена ранее — таков путь. Еще вариант использовать вероятностные методы типа монтекарло, но сходимость там гавно как sqrt(n)
Здравствуйте, Khimik, Вы писали:
K>Наверно с шахматами сходство есть, но главное различие — в шахматах всех комбинаций всё равно не переберёшь и надо использовать эвристики, а тут надо именно всё перебрать и дать однозначный ответ.
Кажется, что по условию задачи не все осколки возможны. Есть ли состояние, из которого уже не выйдет ничего хорошего? Если есть, то этот путь оценивать и отсекать.
. Есть брутто-формула молекулы, например C6H6. Нужно перебрать все осколки, и далее для каждого осколка перебрать все возможные связи в нём, чтобы проверить – можно ли расставить связи так, чтобы валентность водорода была всегда 1, а валентность углерода от 1 до 4. K>Т.е. c C6H6 можно сгенерировать осколок CH4 или H2, но нельзя CH5 или H3.
Непонятно. Я не химик, но вроде бы если мы собрали из двух H один H2, то он уже самостоятельная молекула и прицепить его ни к чему не удастся.
А если мы собрали из одного C и одного H кусочек СH, то из него "торчит" 3 связи C, и можно доприцепить к нему ещё что-то.
Поэтому напрашивается простой алгоритм:
1. Вынимаем из "коробки" атом, и для каждой из его связей
1.1. смотрим — можно ли из оставшихся в коробке что-то к нему прицепить
1.1.1. если да — то прицепляем это что-то, и рекурсивно обращаемся к п.1 — то есть пытаемся к каждой из оставшихся связей что-то прицепить
1.1.2. Если в коробке не осталось атомов, то у нас получилась не молекула, а свободный радикал.
1.1.3. Если у нас кончились связи, а в коробке остались ещё атомы, то мы задачу не решили. Так что нужно вернуть последний прицепленный кусочек в коробку и выйти из рекурсии для перебора следующей попытки.
Начинаем разгребать HHHHHHCCCCCC:
1. достали H
2. .достали второй H
3. ..получилось H2, но атомов ещё полно — кладём H обратно в коробку и берём следующий
4. .Берём C (очевидно, что пробовать остальные четыре H не имеет смысла, т.к. они дадут тот же результат), получаем CH. У него три "свободных" связи.
5. ..Берём из коробки H, получаем CH2. У него 2 связи
6. ...Берём из коробки H, получаем CH3. У него 1 связь
7. ....Берём из коробки H, получаем CH4. У него нет свободных связей, но атомов ещё полно — кладём H обратно в коробку
8. ....Берём из коробки C, получаем C2H3. У него 3 cвязи.
9. .....Берём из коробки H, получаем C2H4. У него 2 связи.
10. .....Берём из коробки H, получаем C2H5. У него 1 связь.
11. ...... Берём из коробки H, получаем C2H6. У него нет свободных связей, но атомов ещё полно — кладём H обратно в коробку.
12. ...... Берём из коробки С, получаем C3H5. У него 3
.....
Берём из коробки H, получаем C6H6, свободных связей нет, атомов в коробке нет. Задача решена.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>Берём из коробки H, получаем C6H6, свободных связей нет, атомов в коробке нет. Задача решена.
Это ещё зависит от того как он связи разрывает. Может он их гамма квантами облучает, или из ускорителя протонами, альфа-частицами или бета-частицами расстреливает. Может там возбуждённые и заряженный осколки разлетаются.
Здравствуйте, Nuzhny, Вы писали:
K>>Наверно с шахматами сходство есть, но главное различие — в шахматах всех комбинаций всё равно не переберёшь и надо использовать эвристики, а тут надо именно всё перебрать и дать однозначный ответ.
N>Кажется, что по условию задачи не все осколки возможны. Есть ли состояние, из которого уже не выйдет ничего хорошего? Если есть, то этот путь оценивать и отсекать.
Ну это я и пытаюсь сделать. Для масс-спектра нужно перечислить возможные ионы, которые дают такие-то пики. По-хорошему надо это решить методами квантовой химии, и мне хочется в будущем этим заняться. Кажется это делается так: проводится расчёт ионизированной формы молекулы, придаётся большая кинетическая энергия и программа смотрит, как этот ион развалится на куски (на какие куски). Процесс повторяется много раз и усредняется.
А пока я хочу сделать более простую вещь, как описал в оп. Плюс такого подхода в том, что он максимально предсказуемый, пользователь будет полностью понимать что от него ждать и что не ждать.
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.
Здравствуйте, Sinclair, Вы писали:
S>Берём из коробки H, получаем C6H6, свободных связей нет, атомов в коробке нет. Задача решена.
Прошу прощения я пока не начал скрипеть мозгами и разбирать ваш алгоритм; это не задача — отсеять перегруппировочные ионы? Если да, я это уже сделал.
Перегруппировочные ионы в масс-спектре — это ионы с новыми связями, которые успели образоваться после ионизации молекулы. Например формула бензола C6H6 показана на рисунке в предыдущем посте, и если отсеивать перегруппировочные ионы, то можно получить C6H4, C6H3, но нельзя CH3.
Слышал что есть какие-то отдельные изученные виды перегруппировок: перегруппировка Маклаферти, миграция двойной связи. Надо разобраться, что это такое и как это закодить.
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.
Здравствуйте, Nuzhny, Вы писали:
K>>Как оптимизировать этот алгоритм?
N>Эта задача не похожа на шахматы? Минимак, альфа-бета — строить дерево вариантов и заранее отсекать то, что проверять не надо?
По-моему, эта задача похожа на задачу вывода всех возможных перестановок строк заданной длинны из заданного набора символов (возможно с повторами) в лексикографическом порядке.
Здравствуйте, Pzz, Вы писали:
Pzz>По-моему, эта задача похожа на задачу вывода всех возможных перестановок строк заданной длинны из заданного набора символов (возможно с повторами) в лексикографическом порядке.
Я понял. Но вдруг, получив очередную перестановку из M символов сразу понятно, что все перестановки M+1 не годятся.
Я уже писал что сделал отсеивание перегруппировочных ионов, но сейчас понял что мой алгоритм тоже не годится для больших молекул из-за плохой оптимизации.
Сейчас я сделал так. Предположим есть молекула:
У нас 12 атомов и мы можем перебрать все комбинации, когда каждый атом либо есть либо удалён. И для каждой комбинации можно посчитать, не является ли она не единой. Если убрать атом N12 — получится молекула C6H5, нормальная. Если убрать атом 1 — получатся две молекулы и это можно отбросить (вместе с атомом удаляются связи). Если убрать атомы 1 и 12 — снова получится нормальная связанная молекула C5H5.
Чтобы проверить, является ли молекула нормальной (единой), у меня выполняется как бы два вложенных цикла. Итого для N атомов общее время алгоритма пропорционально (2^N)*(N^2). Для больших молекул это много. Как ускорить алгоритм?
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.
Здравствуйте, Nuzhny, Вы писали:
Pzz>>По-моему, эта задача похожа на задачу вывода всех возможных перестановок строк заданной длинны из заданного набора символов (возможно с повторами) в лексикографическом порядке.
N>Я понял. Но вдруг, получив очередную перестановку из M символов сразу понятно, что все перестановки M+1 не годятся.
Я не знаю. Я так глобоко эту задачу не продумывал. В конце концов, за нее платят химику, а не мне. Но интуиция мне подсказывает посмотреть в эту сторону.
Пока у меня есть идея, как сделать алгоритм для линейных алканов:
Изначально все атомы включены, потом выключаем N11, потом 10, потом 9, потом 8 и так далее. И на каждой итерации смотрим, какая выстраивается цепочка от первого атома. Если выключить восьмой атом, то выстроится C2H5; и поскольку число атомов в этой цепочке не совпадает с числом атомов в целом, то атомы после цепочки мы можем разом выключить, т.е. не перебирать когда 11-й выключен а 10-й включен и так далее.
При этом надо выстроить порядок атомов как на картинке. И уже для разветвлённых алканов этот алгоритм нужно улучшать:
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.
Здравствуйте, Khimik, Вы писали:
K>Пока у меня есть идея, как сделать алгоритм для линейных алканов:
У вас атом развывают чем? Если его обстреливают. То имеет смысла так осколки и строить по томуже принципу а не все подряд. Попали в атом, он получил энергию достаточную что бы разорвать связи и улететь вместе с ближайшим окружением, т.е. порвать наиболее слабые связи. Далее имея некое распределение вероятностей осколков вы можете их комбинировать в более сложные конструкции, при этом приписывая им вероятность на основе вероятностей составных частей. Нафига перебирать конфигурации с около нулевой вероятностью
. Есть брутто-формула молекулы, например C6H6. Нужно перебрать все осколки, и далее для каждого осколка перебрать все возможные связи в нём, чтобы проверить – можно ли расставить связи так, чтобы валентность водорода была всегда 1, а валентность углерода от 1 до 4. Т.е. c C6H6 можно сгенерировать осколок CH4 или H2, но нельзя CH5 или H3. K>Я пока решил эту задачу в лоб. Для молекулы из n атомов строится массив n*(n-1)/2 – все возможные пары атомов. В массиве хранятся булевы значения, т.е. если true – значит эта связь есть. Программа перебирает все комбинации связей по алгоритму в теме по ссылке выше; если например в молекуле 10 атомов, то число возможных пар атомов будет 10*9/2=45, и число всех комбинаций 2^45. Для каждой комбинации программа проверяет текущую валентность всех атомов (попадает ли она в мои критерии). И даже для десятитомной молекулы ресурсов компьютера не хватает, чтобы всё перебрать. K>Как оптимизировать этот алгоритм?
Для начальной молекулы есть только брутто формула? (Не структура?)
Молекулы только из С и H, или элементов может быть больше?
Нужны только брутто формулы осколков, или структуры осколков? (Т.е. нужно знать что структура с такой брутто формулой возможна, или найти структуру?)
Есть простые простые неравенства, для проверки существования молекул из C и H по брутто формуле. Можно обобщить на С+H+O+P+N.
Но, с учетом структуры начальной молекулы, будет разрешено много меньше осколков, чем из брутто формулы.
что её мешает использовать?
