В настоящее время я работаю над проектом, в котором сочетаются коммивояжер и кратчайший путь. Это происходит следующим образом:
Мне дан набор из 9 вершин, все с положительными координатами в пространстве 2 (x, y), где x и y - положительные действительные числа. Затем меня просят вычислить кратчайший путь, по которому может пойти коммивояжер, и пройти через все точки. По сути, граф — это просто набор узлов с координатами, и мне нужно расположить ребра так, чтобы было соединение от узла 1 до узла 9, то есть кратчайшее из возможных. Предполагается, что я уже посетил в начале узел 1 (x1,y1), и мне нужно посетить каждый узел один и только один раз. Я закончу на узле 9, заданном (x9,y9).
Я пишу программу на Java, хотя профессор сказал, что программу можно написать на любом языке.
Я начал с написания класса узла, который представляет каждый узел и имеет поля x, y, которые представляют координаты x и y соответственно. Однако я совершенно не понимаю, как выполнить оптимизацию.
Буду очень признателен за любую помощь в решении этой проблемы.
Большое спасибо, и я рад стать членом этого сообщества!