2016-12-15 6 views
1

Неполадка поиска формулы для TSP Количество узлов. Допустим, у нас есть асимметричная матрица смежности с 4 городами.Число продавцов торговых узлов

matrix = {{0,1,2,3},{4,0,5,6},{7,8,0,9},{10,11,12,0},}; 

В матрице 5х5 физические упражнения подсчета всего узлов дается, что 41.

Каждый следующий уровень дерево п-1 возможные следующие узлы для поиска. Другое дело, что из последнего города путь должен заканчиваться в первом городе. Например: [0,2,1,3,0]. 5x5 Matrix nodes Как видно на картинке, каждый уровень имеет n-1 возможных маршрутов слева.

+0

Можете ли вы объяснить свой конкретный вопрос? Что вы понимаете под общим количеством узлов? –

+0

Общее количество узлов - это количество узлов, для которых алгоритм жадного решения работает, чтобы найти лучшее решение. Добавлен иллюстративный образ. – Aficionado

+0

Как вы можете видеть сверху, этот вопрос касался формулы подсчета узлов для этого общего решения. Программа уже закончена и работает с резкой BSF. – Aficionado

ответ

0

Если я понимаю, вы пытаетесь выяснить количество узлов в дереве. Верх - 1, следующая строка имеет (n-1), следующая имеет (n-1) (n-2) и так далее, пока дно, которое (n-1) (n-2) ... 2. Итак, вы собираетесь суммировать их:

1 + (n-1) + (n-1) (n-2) + (n-1) (n-2) (n-3) +. .. + (п-1) (п-2) ... 2

Эта серия OEIS 000248