Здравствуйте, xma, Вы писали:

xma>п.2.1.1) находить циклы при этом придётся отсечением тех многоугольников (возможно и невыпуклых) где внутри есть другие атомы, по координатам .. (другого решения сходу не видать)

не видать, потому что в общем случае не определить (только по "графу" и без координат) — пересекает ли цепочка связанных атомов — многоугольник (потенциальный цикл), по внутренней его области (тогда этот многоугольник — точно не цикл) или всё таки — с внешней стороны ..

A>Ув. Khimik! Именно этой проблемой занимается математика, в частности — алгебра. Алгебра позволяет вывести и зафиксировать *любые* закономерности в абстрактных символах.
A>Дилемма состоит в том, что большинство специалистов функционирует в своих областях (например, химия), не осознавая глубину доступных средств из соседних областей (математика).



Подозреваю, что ты хотел использовать слово "проблема", но дилемма звучит лучше, признаю.

Здравствуйте, pagid, Вы писали:

P>Здравствуйте, Khimik, Вы писали:

K>>Дело в том что я упростил задачу — предложил определять вообще любые циклы. Такого вещества с 14-членным циклом конечно не существует, а вообще ароматические циклы могут быть разных размеров, например в азулене есть два смежных цикла из 5 и 7 атомов.
P>Забавно, о таких не знал.
P>Они могут только рядом быть и существую на пару? Или бывают одиночные варианты?

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

Здравствуйте, Khimik, Вы писали:

K>Я так и не понял, что вы привязались к этим сотам? Какая разница, все атомы цикла или не все входят в другие циклы?
Потомоу, что на второй картинке у тебя больше чем 4 цикла если не рассматривать циклы только из 6 вершин.

Здравствуйте, Kernan, Вы писали:

K>Здравствуйте, Khimik, Вы писали:

K>>Я так и не понял, что вы привязались к этим сотам? Какая разница, все атомы цикла или не все входят в другие циклы?
K>Потомоу, что на второй картинке у тебя больше чем 4 цикла если не рассматривать циклы только из 6 вершин.

Ну это подразумевается условиями задачи — из вложенных друг в друга циклов оставлять самые маленькие.

Здравствуйте, Khimik, Вы писали:

K>У меня возникла такая задача: определить в молекуле все циклы (точнее, ароматические циклы). Молекула – это набор атомов с декартовыми координатами и связей между ними. Например в этой молекуле два цикла по 6 атомов:
...
K>Возникает вопрос: можно ли разработать эвристические приёмы, которые переводят “интуитивно-понятное” в “формализованно-понятное”? Например большой список универсальных вопросов.

Например можно найти специализированный инструмент или понятийный аппарат, в котором предметную область уже формализовали, и оперировать этими терминами и возможностями.
Например в случае с циклами: загрузить граф в специализированную графовую БД типа Neojj, и тогда можно оперировать циклами очень лаконично, например, поиск циклов тогда будет выглядеть всего 1-2 короткими строками на специализированном графовом языке:
https://stackoverflow.com/questions/34136944/detecting-short-cycles-in-neo4j-property-graph

Ну а если тебя интересует сам общий подход формализации, то можно посмотреть в сторону DSL и платформы для этого, например Jetbrains MPS.
Т.е. идея заключается в том, что ты сначала придумываешь язык, термины и понятия для той области, которую хочешь формализовать и понять (создаёшь язык DSL), а затем оперируешь этим языком для решения задач этой предметной области. Поэтому ищи и читай про практики создания DSL, чтобы увидеть такие эвристические приёмы.

Здравствуйте, Khimik, Вы писали:

K>Здравствуйте, Kernan, Вы писали:

K>>Здравствуйте, Khimik, Вы писали:

K>>>Я так и не понял, что вы привязались к этим сотам? Какая разница, все атомы цикла или не все входят в другие циклы?
K>>Потомоу, что на второй картинке у тебя больше чем 4 цикла если не рассматривать циклы только из 6 вершин.

K>Ну это подразумевается условиями задачи — из вложенных друг в друга циклов оставлять самые маленькие.
Так не получится. Ты опять формулируешь задачу как поиск всех циклов в графе и потом поиска среди них наименьшего, но тут опять вопрос, что если будет цикл из 3х или 4х вершин, но будут и из 6 которые включают 2 по 3?

K>>>>Я так и не понял, что вы привязались к этим сотам? Какая разница, все атомы цикла или не все входят в другие циклы?
K>>>Потомоу, что на второй картинке у тебя больше чем 4 цикла если не рассматривать циклы только из 6 вершин.

K>>Ну это подразумевается условиями задачи — из вложенных друг в друга циклов оставлять самые маленькие.
K>Так не получится. Ты опять формулируешь задачу как поиск всех циклов в графе и потом поиска среди них наименьшего, но тут опять вопрос, что если будет цикл из 3х или 4х вершин, но будут и из 6 которые включают 2 по 3?

Я не понимаю что вы спрашиваете.
Вот молекула нафталина:



В ней, строго говоря, есть три цикла: два по 6 атомов и один из 10 атомов. Последний нужно отбросить, т.к. он включает в себя первый и второй цикл. Если перебирать циклы через графы, будут найдены все три цикла и алгоритм должен отбрасывать бОльший, содержащие вложенные меньшие циклы.

Здравствуйте, Khimik, Вы писали:
K>В ней, строго говоря, есть три цикла: два по 6 атомов и один из 10 атомов. Последний нужно отбросить, т.к. он включает в себя первый и второй цикл. Если перебирать циклы через графы, будут найдены все три цикла и алгоритм должен отбрасывать бОльший, содержащие вложенные меньшие циклы.
По-прежнему непонятно.
Смотрите:

    A   B
    |   |
C   D   E   F
 \ / \ / \ /
  G   H   I
  |   |   |
  J   K   L
 / \ / \ / \
M   N   O   P
    |   |
    Q   R

Вы видите здесь циклы GDHKNJ и HEILOK. Под "циклом из 10 атомов" вы подразумеваете что — GDHEILOKNJ? Что насчёт GDHKOLIEHKN? или мы должны отбрасывать циклы с самопересечениями?
Дальше — что значит "состоит из вложенных меньших циклов"? В GDHEILOKNJ есть фрагмент HEILOK, но нету GDHKNJ.
Интересуют ли вас циклы произвольной длины, или только 5/6 атомов, только углерода, и без самопересечений?
Могут ли встречаться случаи типа

       
       
A   B     C   
 \ /|\  / 
  D E F   
  |/  |   
  G   H  
   \ / \  
    I   J - K
    |   
    L

? Какие циклы должны быть построены в таком случае? GDBFHI/GEBFHI, или DBEG?

Здравствуйте, Sinclair, Вы писали:

S>Здравствуйте, Khimik, Вы писали:
K>>В ней, строго говоря, есть три цикла: два по 6 атомов и один из 10 атомов. Последний нужно отбросить, т.к. он включает в себя первый и второй цикл. Если перебирать циклы через графы, будут найдены все три цикла и алгоритм должен отбрасывать бОльший, содержащие вложенные меньшие циклы.
S>По-прежнему непонятно.
S>Смотрите:
S>

S>    A   B
S>    |   |
S>C   D   E   F
S> \ / \ / \ /
S>  G   H   I
S>  |   |   |
S>  J   K   L
S> / \ / \ / \
S>M   N   O   P
S>    |   |
S>    Q   R
S>

S>Вы видите здесь циклы GDHKNJ и HEILOK. Под "циклом из 10 атомов" вы подразумеваете что — GDHEILOKNJ?
Да

> Что насчёт GDHKOLIEHKN? или мы должны отбрасывать циклы с самопересечениями?

Да, конечно. Атомы в цикле должны встречаться только по разу.

S>Дальше — что значит "состоит из вложенных меньших циклов"? В GDHEILOKNJ есть фрагмент HEILOK, но нету GDHKNJ.

Почему нет? Можно же по-другому пронумеровать атомы в цикле.

S>Интересуют ли вас циклы произвольной длины, или только 5/6 атомов, только углерода, и без самопересечений?

Проще искать любые циклы, произвольной длины.

S>Могут ли встречаться случаи типа
S>

       
       
S>A   B     C   
S> \ /|\  / 
S>  D E F   
S>  |/  |   
S>  G   H  
S>   \ / \  
S>    I   J - K
S>    |   
S>    L   
S>

S>? Какие циклы должны быть построены в таком случае? GDBFHI/GEBFHI, или DBEG?

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

Здравствуйте, Khimik, Вы писали:

K>Я корпел несколько недель над алгоритмом, и то он получился несовершенным. А вы могли бы быстро что-то придумать?
Быстро бы я придумал загуглить https://www.google.com/search?q=алгоритм+поиска+циклов+в+графе.
Потом бы медленно думал над тем, что делать с "лишними" циклами, которые будет выдавать алгоритм.
K>Когда я писал этот алгоритм, возникли такие мысли. С одной стороны, достаточно мельком взглянуть на молекулу и сразу видно, где в ней циклы. В то же время формализовать это “видно” – задача на порядки более трудная. Судя по всему, понимание – штука сложная и понимание бывает на разных уровнях: одно дело – когда смотришь на молекулу и сразу понятно где в ней циклы, а другое дело – когда понятно с точки зрения алгоритма, что такое цикл и как его распознать.
Да, верно.
K>Возникает вопрос: можно ли разработать эвристические приёмы, которые переводят “интуитивно-понятное” в “формализованно-понятное”? Например большой список универсальных вопросов.
Этим всю жизнь занимаются математики — они учатся отбрасывать всё лишнее, оставляя в задаче только существенные характеристики.
Потом им иногда удаётся заметить, что получившаяся задача похожа на какую-то другую — например, распределение регистров вычисления неожиданно сводится к задаче о раскраске графа.
Для того, чтобы добиться успеха в какой-нибудь дисциплине, необходимо стоять на её стыке с какой-то другой дисциплиной. Потому что всё, что можно сделать "внутри" дисциплины уже сделали поколения учёных до нас.

Здравствуйте, Khimik, Вы писали:

K>Я корпел несколько недель над алгоритмом, и то он получился несовершенным. А вы могли бы быстро что-то придумать?

Я бы точно начал со штудирования матчасти, а не бросился с шашкой на танк. Вроде же более-менее очевидно, что задача про минимальные циклы в графе?
Там (в графах) вроде как все уже неплохо перепахано, зачем изобретать велосипед.

Здравствуйте, Khimik, Вы писали:
K>Да, конечно. Атомы в цикле должны встречаться только по разу.
Ну, тогда всё более-менее прямолинейно. Берём алгоритм Джонсона https://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF, применяем.
S>>Дальше — что значит "состоит из вложенных меньших циклов"? В GDHEILOKNJ есть фрагмент HEILOK, но нету GDHKNJ.
K>Почему нет? Можно же по-другому пронумеровать атомы в цикле.
Ок, формализуем понятие "цикл C1 входит в С2":
— Длина С1 < длины C2
— Цикл С2 содержит в себе последовательность тех же вершин, что и С1 (либо в обратном порядке).

Это сразу даёт нам алгоритм сравнения двух циклов:
1. Если длина С2 <= длины C1, то возвращаем НЕТ
2. Берём 1 вершину из C1, ищем её в C2 (O(len(C2)))
3. Если не нашли, то возвращаем НЕТ
4. Если нашли (по индексу m), то начинаем проверять следующие вершины:
4.1. C1[i] = C2[(m+i) mod len(C2)] (O(len(C1))) — если хотя бы один не совпал, прерываем цикл и идём в 4.2
4.2. С1[i] = C2[(m-i) mod len(C2)] (O(len(C1))) — если хотя бы один не совпал, возвращаем НЕТ
5. Возвращаем ДА

На основе этого алгоритма легко построить алгоритм изгнания дубликатов:
1. Сортируем список циклов по возрастанию длины, группируем его по длине. То есть у нас есть список L списков циклов, где L[i] — список циклов с одинаковой длиной; и длина циклов в L[i+1] строго больше длины циклов в L[i].
2. Цикл: i перебирает все индексы списка L
3. Цикл: j перебирает все индексы списка L[i]
4. Цикл: k перебирает индексы L от i+1 до конца
5. Цикл: m перебирает все циклы списка L[k]
3. Если L[i][j] входит в L[k][m], то выбрасываем L[k][m] из L[k]
После окончания работы алгоритма в списке L останутся только те циклы, в которые не входят другие циклы.

S>>Интересуют ли вас циклы произвольной длины, или только 5/6 атомов, только углерода, и без самопересечений?

K>Проще искать любые циклы, произвольной длины.
Ну, вообще-то проще искать циклы фиксированной длины
S>>Могут ли встречаться случаи типа
S>>

       
       
S>>A   B     C   
S>> \ /|\  / 
S>>  D E F   
S>>  |/  |   
S>>  G   H  
S>>   \ / \  
S>>    I   J - K
S>>    |   
S>>    L   
S>>

S>>? Какие циклы должны быть построены в таком случае? GDBFHI/GEBFHI, или DBEG?

K>Такие циклы встречаются, хотя для моей задачи их находить в принципе необязательно; по идее нужно выделить все три цикла которые вы назвали.