3.06.3. Задача о коммивояжере

Имеется полный взвешенный граф. Требуется отыскать гамильтонов цикл минимального веса.

К данной формулировке можно свести и задачу отыскания гамильтонового цикла в неполном графе. В этом случае отсутствующим ребрам присваивают вес .

Если нужно найти гамильтонов цикл в обычном (не взвешенном графе), то рёбрам присваивают вес 0, а отсутствующим рёбрам вес и ищут гамильтонов цикл веса 0.

Существуют специальные алгоритмы решения данной задачи. Самый примитивный, но чрезвычайно трудоёмкий, из них – полный перебор. Количество вариантов, которые при этом нужно рассмотреть, равно числу циклических перестановок, т. е. (N-1)!, где N – порядок графа.

< Предыдущая		Следующая >