В чем разница между дискретной оптимизацией и комбинаторными алгоритмами?

Возможно, имелись в виду различия между дискретной оптимизацией и комбинаторной оптимизацией, хотя эти понятия тесно связаны. ru.wikipedia.org dspace.tltsu.ru

Дискретная оптимизация — раздел математики, в котором изучают и решают экстремальные задачи на конечных множествах. dspace.tltsu.ru Некоторые или все переменные, используемые в дискретной оптимизации, ограничены множеством дискретных значений, например, целыми числами. dspace.tltsu.ru К задачам дискретной оптимизации относятся, например, задача коммивояжёра или задача о кратчайшем пути. elar.urfu.ru dspace.tltsu.ru

Комбинаторная оптимизация — область теории оптимизации в прикладной математике, связанная с исследованием операций, теорией алгоритмов и теорией вычислительной сложности. ru.wikipedia.org Комбинаторная оптимизация заключается в поиске оптимального объекта в конечном множестве объектов. ru.wikipedia.org К задачам комбинаторной оптимизации относятся, в частности, поиск кратчайшего пути и дерева кратчайших путей, определение максимального потока, нахождение остовных деревьев и паросочетаний. ru.wikipedia.org

Таким образом, разница заключается в том, что дискретная оптимизация охватывает более широкий спектр задач, а комбинаторная оптимизация фокусируется на определённых группах задач, связанных с конкретными структурами (графами, матроидами и т. д.). ru.wikipedia.org dspace.tltsu.ru

При этом многие проблемы комбинаторной оптимизации могут быть смоделированы как целочисленные программы, и, наоборот, целочисленные программы часто могут иметь комбинаторную интерпретацию. dspace.tltsu.ru

Пользователь

Время добавления