1 Тема от SvetlanaY

  • SvetlanaY
  • Участник
  • Неактивен
  • Зарегистрирован: 2011-05-25
  • Сообщений: 1

Тема: Линейное программирование или теория графов?

Подскажите, пожалуйста, есть ли разница в расчетах, к примеру  решения задачи максимального потока минимальной стоимости или задачи с другой математической постановкой, симплекс-методом и методом из теории графов?

2 Ответ от e-maxx

  • e-maxx
  • admin
  • Неактивен
  • Откуда: Саратов
  • Зарегистрирован: 2009-06-10
  • Сообщений: 360

Re: Линейное программирование или теория графов?

(... почему-то пост остался без ответа?..)

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

По меньшей мере в теории, симплекс-метод не работает за полиномиальное время, в отличие от "классических" алгоритмов теории графов.


С другой стороны, надо учитывать, что алгоритмы теории графов умеют быстро решать только очень ограниченный круг задач, в отличие от весьма общей постановки задачи линейного программирования.

Сайтe-maxx