точные алгоритмы графа

Question

в структурах данных и алгоритмах, что понимается под «точных алгоритмов графа»? можете ли вы привести несколько примеров?

Answer 1

Я полагаю, это относится к тому, что алгоритм дает результат, оптимальный для данной задачи, или если он дает «просто» примерный результат.

Например, если вы смотрите на графике для shortest path от одного узла к другому, есть куча алгоритмов (Dijkstra, Floyd-Warshall ... вы называете их), которые решают эту проблему точно, то они дают кратчайший путь между двумя указанными узлами.

С другой стороны, рассмотрите проблему Travelling Salesman. В нем оговаривается вопрос о кратчайшем круговом пути, содержащем некоторые заданные узлы. Эта проблема NP-complete и, следовательно, (предположительно) не разрешима ровно в разумные сроки (по крайней мере, для общего случая). Тем не менее, существуют алгоритмы аппроксимации, работающие в разумные сроки, что дает решение, которое составляет самое большее 2*length(best route) (по крайней мере, для метрического TSP), поэтому решение по этому алгоритму не является точным, а просто приближенным.