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

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

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


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

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

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

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

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

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