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

0 +1 -1
Gleb V спросил 1 год назад

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

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

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

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

Соединить гвозди от А до В
Соединить гвозди от А до В
Таня ответил 1 год назад

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

admin Админ. ответил 1 год назад

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

Катерина ответил 1 год назад

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

1 ответ
0 +1 -1
admin Админ. ответил 1 год назад

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

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

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

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

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

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

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