|
Научные направления - Дискретная оптимизация
В рамках дискретной (комбинаторной) оптимизация рассматриваются оптимизационные задачи, в которых число допустимых решений конечно. Это допускает перебор всех решений и выбор наилучшего. Однако в реальных задачах количество допустимых решений столь велико, что их перебор невозможно осуществить за приемлемое время даже с помощью самой мощной вычислительной техники...
В связи с этим основным направлением в дискретной оптимизации является разработка алгоритмов, которые не перебирают всё множество решений, а находят оптимальное решение с невысокой трудоёмкостью. К сожалению не всегда это возможно. Так для, так называемых, NP-трудных задач общепринято считать (хотя строго это не доказано), что не существует эффективных (имеющих полиномиальную трудоёмкость) алгоритмов их решения.
Это обстоятельство вынуждает специалистов искать частные полиномиально разрешимые случаи задач, а также разрабатывать малотрудоёмкие алгоритмы построения приближенных решений.
Преподаватели:
|
