Соедини все гвозди от А до В ниткой как можно меньшей длины

0 +1 -1
Александр Головин спросил 10 месяцев назад

Соедини все гвозди от точки А до точки В ниткой как можно меньшей длины.
Гвозди


1 ответ
0 +1 -1
admin Админ. ответил 10 месяцев назад

Для решения данной задачи стоит начать соединять гвозди, начиная с конца, то есть с точки В. Соединять гвозди следует либо по горизонтали, либо по вертикали.

Гвозди, соединенные ниткой
Гвозди, соединенные ниткой

В науке данная задача имеет название — задача коммивояжера.

Коммивояжер (бродячий торговец) должен выйти из города 1 и, посетив по разу в неизвестном порядке города 2, 3, … N, вернуться обратно в город 1. В каком порядке надо обходить города, чтобы путь коммивояжера был кратчайшим?

     Это наиболее полная задача, которая строго решается 
на сегодняшний день только перебором вариантов!

Очень плохоПлохоСреднеХорошоОтлично (Еще нет голосов, оставьте первым)
Загрузка...