Глава что такое комбинаторика. Основные проблемы изучения комбинаторики

Задача о коммивояжере. Дана матрица L = {l_ij} размером nn – матрица расстояний между городами. Требуется построить кратчайший замкнутый маршрут, проходящий ровно по одному разу через каждый город.
Это задача оптимизации с фиксированной размерностью. Элемент плана x_i можно понимать как номер города, в который нужно ехать на i-том шаге, либо как номер города, в который нужно ехать из i-того города. Исходные данные p заданы в виде матрицы L. Функция ограничений задана неявно, в виде требований замкнутости маршрута и однократного посещения каждого города. Роль целевой функции играет длина маршрута. Задача решается достаточно трудно, далее будет рассмотрен один из алгоритмов решения.
Подобно многим другим математическим задачам, задача о коммивояжере допускает множество разных содержательных интерпретаций. Например, «расстояние» может также пониматься как стоимость или время, а «города» – как точки на электронной схеме или станции перекачки нефти. Матрица расстояний не обязана быть симметричной (т.е. расстояние от A до B может не совпадать с расстоянием от B до A).
Задача о кратчайшем пути в графе. Дан граф G = (V,E) и матрица длин ребер L. Заданы также две вершины A и B. Требуется найти кратчайший путь из A в B.
Это также задача оптимизации. Ее можно рассматривать как задачу фиксированной размерности (для каждого ребра указать, входит оно в кратчайший путь или нет), но, вероятно, более естественно считать размерность нефиксированной (составить список ребер, образующих кратчайший путь). Несмотря на очевидное сходство с предыдущей задачей, задача о кратчайшем пути решается намного легче, для нее в теории графов разработаны очень эффективные алгоритмы.
Задача о длиннейшем пути в графе. В условиях предыдущей задачи требуется найти самый длинный путь из A в B, не образующий циклов.
Как ни странно, эта задача, в отличие от предыдущей, весьма сложна для решения.