Anatoly Levenchuk (ailev) wrote,
Anatoly Levenchuk
ailev

Алгоритмический прорыв: от графов и путей к матрицам и уравнениям

Новости алгоритмики: http://web.mit.edu/newsoffice/2010/max-flow-speedup-0927.html

Суть в том, что "перебор-подбор по путям в графе" в проблеме нахождения максимальной пропускной способности сети-графа заменен решением уравнений по представляющей граф матрице. И это получается вычислительно эффективней, чем улучшать стратегии перебора (улучшить перебор не удавалось последние 10 лет). Некоторые ученые приготовились попробовать эту же "матризацию графа" и в других областях, так что мы еще много чего услышим про "матризацию графа и последующее решение уравнений".

То-то я гляжу, у vvagr проснулся интерес к матрицам, он их уже несколько дней хочет рисовать. Хотя это и совсем другие матрицы :)
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

  • 2 comments