Сколько времени мне потребуется, чтобы запрограммировать программу коммивояжера с 5 узлами?

Question

Я подумываю решить задачу коммивояжера для моего курса по вычислительной технике и хотел бы знать, сколько времени потребуется стандартному компьютеру для прохождения кратчайшего маршрута между 5 различными местами. Я просто хочу знать, является ли проект жизнеспособным. Заранее спасибо! Я буду использовать VB Express.

Answer 1

Сколько существует возможных маршрутов? Неофициально, конечно, не много? Формально, я позволю тебе решить это. Сколько времени вам понадобится с бумагой и карандашом, чтобы перечислить их и найти самый короткий? Конечно, менее чем за 5 минут? Так что это дает вам представление, что это не облагается налогом даже на медленном компьютере.

Это может быть идея сделать бумагу и карандаш для 5 и 6 узлов и убедиться, что вы понимаете, что происходит с увеличением количества узлов, и, следовательно, почему эта проблема начинает усугубляться, когда число узлов становится большим .

Answer 2

Простое решение задачи коммивояжера на 5 мест требует перечисления 5! путей.5! = 1*2*3*4*5 = 120.Перечисление 120 путей не было большой проблемой для любого современного компьютера, начиная с 80-х годов.

Но, конечно, если вы хотите сделать его медленным, вы всегда можете написать свою программу ужасно плохо, особенно на VB.