Это связано с проблемой коммивояжера. Сначала необходимо сгенерировать все перестановки, а затем прикрепить пункт назначения (такой же, как источник). То есть: 1) abcd abdc .... 2) абвда абдца ....а У меня есть все расстояния, и мне нужен...

Недавно я пытался придумать общее количество гамильтоновых путей (в основном начиная с начальной вершины, посещая каждый узел ровно один раз и достигая конечной вершины). Brute force dfs долго гуляет по сетке среднего размера 7x8. Я придумал...

Я читал алгоритмы поиска минимального остовного дерева (в случае взвешенных графов) и определения того, имеет ли граф гамильтонов путь (который зависит от наличия гамильтонова цикла). У меня все перепуталось. Так в чем же разница между гамильтоновым...

Я ищу алгоритм, который быстрее, чем экспоненциальный, который найдет ЛЮБОЙ цикл в задаче коммивояжера. Неважно, насколько плохой цикл, он просто должен быть циклом. Что мне действительно нужно, так это алгоритм для гамильтоновой схемы. Что-то, что...

Предположим, что существует ориентированный граф, состоящий из вершин, названных ниже: "ABC", "ABD", "ACB", "ACD", "ADB", "ADC", "BAC", "BAD", "BCA", "BCD", "BDA", "BDC", "CAB", "CAD", "CBA", "CBD", "CDA", "CDB", "DAB", "DAC", "DBA", "DBC", "DCA",...

Ультрагамильтоновский цикл определяется как замкнутый обход, который посещает каждую вершину ровно один раз, за ​​исключением не более чем одной вершины, которая посещает более одного раза. Вопрос: Докажите, что NP-трудно определить, содержит ли...