Page 140 - 6197

2
4x  3x  ,
2 3
x  3x  2x  ,
3
1 2 3
x , x , x - невід’ємні цілі числа
1 2 3
методом меж і гілок.
10 Дайте словесний опис задачі комівояжера та наведіть
приклади практичного застосування такої задачі.
11 Які операції необхідно здійснити, щоб отримати
приведену матрицю віддалей?
12 Як знайти елемент матриці віддалей, що підлягає
розгалуженню?
13 Наведіть алгоритм розв’язання задачі комівояжера.
14 Сформулюйте ознаку закінчення процесу розв’язування
задачі комівояжера.
15 Є чотири міста, віддалі між якими наведені в табл.
Комівояжер вирушає із пункту 1, відвідує кожне місто тільки
один раз і повертається до пункту 1. Знайти найкоротший
шлях для комівояжера.
Таблиця – Віддалі між містами
1 2 3 4
1 M 2 4 8
2 6 M 6 7
3 5 2 M 5
4 3 2 7 M
16 Дайте визначення симетричної задачі комівояжера.
17 Як побудувати 1-дерево та яким чином визначити його
довжину?
18 У яких випадках відбувається розгалуження задач у
просі розв’язання симетричної задачі комівояжера?
19 Розв’яжіть симетричну задачу комівояжера. Віддалі між
містами вміщує табл.
Таблиця – Віддалі між містами
Номера пунктів

140