Блог

Я пытаюсь построить путь, используя ближайших соседей. У меня есть двумерный список расстояний между двумя узлами, и я ранее заполнил этот список следующим образом:

 distance[i][j]
 

Я хочу, чтобы путь начинался с узла 0, заканчивался на узле 8, и я также хочу, чтобы путь имел в общей сложности 8 узлов. Таким образом, обратный путь должен быть:

 [0, a, b, c, d, e, f, 8] 
 

В моем коде я начинаю с нулевого узла и успешно нахожу ближайший узел от 0, что равно 10. Но для остальных ближайших узлов я также получаю 10. Поэтому, найдя первый ближайший узел, я не могу найти следующий ближайший узел из 10. Мой код выводит следующее:

 [0, 10, 10, 10, 10, 10, 10, 8]
 

Почему мой код не обновляет текущий узел для следующих ближайших соседей? Чего мне не хватает, чтобы найти следующего ближайшего соседа из 10 и так далее?
Заранее спасибо!

         startNode = 0
        endNode = 8
        path = [0]*8 # Create a list for the path
        path[0] = startNode # Add the starting point
        path[endNode-1] = endNode # Add the end point

        currentNode = startNode
        
        for i in range(1, endNode-2): #index 1 to 6 because path[0]=0 and path[7]=8
            a = currentNode   1
            closest = distance[currentNode][a]
            for j in range(a 1, endNode-1):
                if distance[currentNode][j] < closest :
                    closest = distance[currentNode][j] 
            currentNode = j
            path[i] = currentNode # Add the closest node to the new permutation list

        return path
 

Ближайшим узлом к любому узлу является он сам, с расстоянием, равным нулю

Используемая матрица расстояний, единственное отличие в том, что расстояние между 0 и 10 равно 0, чтобы сделать 10 кратчайшим узлом от 0, как в описании задачи.

 np.random.seed(4)
distances=np.random.randint(1,30,(11,11))
x=np.triu(distances)
y=x np.transpose(x)
for i in range(11):
    y[i,i]=999
y[0,10]=0
y[10,0]=0
print(y)

[[999  15  24   6   2   9  24   9  19  10   0]
 [ 15 999  14  24  24  26   9   5  19  13   7]
 [ 24  14 999   1  24  22  22  10   7   7  25]
 [  6  24   1 999  18   3  27  24   1   9  20]
 [  2  24  24  18 999  29   4  19  20  16   3]
 [  9  26  22   3  29 999  10  28  17  13  24]
 [ 24   9  22  27   4  10 999   7   8  14  11]
 [  9   5  10  24  19  28   7 999  16   5  28]
 [ 19  19   7   1  20  17   8  16 999  23   8]
 [ 10  13   7   9  16  13  14   5  23 999  22]
 [  0   7  25  20   3  24  11  28   8  22 999]]
 

Ваш код на самом деле не выводится [0, 10, 10, …, 10, 8]. Похоже, он выводит [0, 6, 6, 6, 6,…, 6, 8], из-за currentNode=j после завершения цикла for просто каждый раз помещает j=6 в currentNode. Модификация вашего кода, которая работает.

 distance=y
for i in range(1, endNode-1): #index 1 to 6 because path[0]=0 and path[7]=8
    closest = 999
    nextNode=-1
    for j in range(1, 11):
        if np.isin(j, path):
            continue
        if distance[currentNode][j] < closest :
            closest = distance[currentNode][j] 
            nextNode = j
    path[i] = nextNode
    currentNode= nextNode

print(path)
[0, 10, 4, 6, 7, 1, 9, 8]