Существует ли алгоритм или набор алгоритмов, которые позволили бы вам найти кратчайшее расстояние ходьбы от произвольного начального узла, чтобы каждый узел посещался в весовом неориентированном графе? Это не совсем коммивояжер, потому что мне все равно, если узел посещают более одного раза. (Это даже не имеет значения, если вы вернетесь к началу - ходок может оказаться в каком-то удаленном узле, если он был последним, необходимым для посещения всех узлов.) Это не совсем минимальное связующее дерево, потому что может случиться так, что движение A -> B -> C -> A -> D - это (неуникальный) кратчайший путь для посещения A, B, C и D. Моя интуиция говорит, что это не Это проблема NP, потому что она не имеет ограничений, которые делают проблемы NP настолько сложными. Я мог, конечно, быть совершенно не прав.