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

0 +1 -1
Gleb V спросил 4 месяца назад

В стену вбиты гвозди на одинаковом расстоянии. Нужно протянуть между ними нитку как можно меньшей длины так, чтобы она коснулась всех гвоздей.

Чтобы соединить три гвоздя ниткой как можно меньшей длины, нужно поступить следующим образом,

Три гвоздяведь сторона квадрата всегда короче его диагонали.

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

Соединить гвозди от А до В
Соединить гвозди от А до В



Таня ответил 3 месяца назад

А как вот такую последовательность гвоздей соединить ниткой?

admin Админ. ответил 3 месяца назад

Вероятно вот так:

Катерина ответил 3 месяца назад

Таня, огромное спасибо!

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

Решение задачи о соединении гвоздей ниткой

Из условия задачи следует, что соединять гвозди следует только горизонтально и вертикально. Тогда получим следующую картину.

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

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

Задача коммивояжера
Задача коммивояжера

Вам также могут быть интересны ответы на следующие вопросы: