Информация об изменениях

Сообщение Re: Оптимизационная задача в комбинаторике от 10.06.2024 16:16

Изменено 10.06.2024 16:22 Khimik

Re: Оптимизационная задача в комбинаторике
Я уже писал что сделал отсеивание перегруппировочных ионов, но сейчас понял что мой алгоритм тоже не годится для больших молекул из-за плохой оптимизации.
Сейчас я сделал так. Предположим есть молекула:



У нас 12 атомов и мы можем перебрать все комбинации, когда каждый атом либо есть либо удалён. И для каждой комбинации можно посчитать, не является ли она не единой. Если убрать атом N12 — получится молекула C6H5, нормальная. Если убрать атом 1 — получатся две молекулы и это можно отбросить (вместе с атомом удаляются связи). Если убрать атомы 1 и 12 — снова получится нормальная связанная молекула C5H5.
Чтобы проверить, является ли молекула нормальной (единой), у меня выполняется как бы два вложенных цикла. Итога для N атомов общее время алгоритма пропорционально (2^N)*(N^2). Для больших молекул это много. Как ускорить алгоритм?
Re: Оптимизационная задача в комбинаторике
Я уже писал что сделал отсеивание перегруппировочных ионов, но сейчас понял что мой алгоритм тоже не годится для больших молекул из-за плохой оптимизации.
Сейчас я сделал так. Предположим есть молекула:



У нас 12 атомов и мы можем перебрать все комбинации, когда каждый атом либо есть либо удалён. И для каждой комбинации можно посчитать, не является ли она не единой. Если убрать атом N12 — получится молекула C6H5, нормальная. Если убрать атом 1 — получатся две молекулы и это можно отбросить (вместе с атомом удаляются связи). Если убрать атомы 1 и 12 — снова получится нормальная связанная молекула C5H5.
Чтобы проверить, является ли молекула нормальной (единой), у меня выполняется как бы два вложенных цикла. Итого для N атомов общее время алгоритма пропорционально (2^N)*(N^2). Для больших молекул это много. Как ускорить алгоритм?