Научные направления - Маршрутизация


Маршрутизация - это раздел комбинаторной оптимизации. Задачи маршрутизации заключаются в поиске некоторых экстремальных подграфов в заданном графе.

К задачам маршрутизации следует отнести:

  • Задачу коммивояжёра;
  • Построение остовных деревьев, а также деревьев Штейнера;
  • Построение оптимальных иерархических структур;
  • и др.

Например, построение остовного (связывающего все вершины графа) дерева минимального веса можно осуществить за полиномиальное время. Если же необходимо связать подмножество вершин, то получаем задачу Штейнера на графах, которая является NP-трудной.

Задача коммивояжёра заключается в поиске простого замкнутого маршрута, проходящего через все вершины графа, минимальной или максимальной длины. Это классическая задача маршрутизации, которая возникает в множестве проблем в качестве подзадачи. К сожалению для неё также не известны полиномиальные алгоритмы решения.

Преподаватели: