Тематичний архів статей

Завдання Комівояжер


Якщо ви здавали ЄДІ з інформатики, то її основний принцип вам буде зрозумілий. Суть завдання в тому, що треба об'їхати всі запропоновані міста і повернутися в початковий місто з найменшими витратами. Отже, розглянемо приклад такого завдання.

ABCDEA 0 10 50 40 20 B 10 0 40 20 50 C 50 40 0 30 60 D 40 20 30 0 90 E 20 50 60 90 0

Тут як ви бачите літерами A, B, C, D, E позначені міста і також показано час за який можна доїхати від одного міста до іншого. Наприклад з міста А в місто С можна доїхати за 50 (хвилин). Потрібно знайти найменший час, за який наш комівояжер об'їде всі міста і приїде назад.

Можна вирішувати цю задачу тим же способом як і «булижники» (С3 ЄДІ з інформатики), тобто шляхом складання виснажливої таблиці і перебором всіх можливих варіантів. Але я розповім вам свій спосіб розв'язання задачі. Почнемо.

Спочатку визначимо самі мінімальні витрати на подолання шляху (нехай такого варіанту руху в принципі бути не може). Тобто 10 (з А в В) 20 (з В в D) 30 (з З в D) 40 (з D в А) 20 (Е в А) = 120. Як бачите цей варіант неможливий, але це і є саме мінімальний час в дорозі. Далі виписуємо парні числа по одному разу (бо наприклад числа 10 - 10 це подорож з А в В і назад). У нас це виходять числа 10, 50, 40, 40, 20, 20, 50, 30, 60, 90. А тепер завдання початкового класу. Зробити число 130 з 5 чисел. (Тому що 120 не існуючий варіант). 130 можна скласти з чисел 10, 20, 20, 30, 50 і 10, 20, 20, 40, 40. Перевіряємо ці варіанти на правильність. Ці варіанти неможливі. Значить переходимо до 140. Тут підходять 3 варіанти. 10, 20, 20, 30, 60, 10, 20, 20, 40, 50, 10, 20, 30, 40, 40. Підходить з них тільки перший варіант. Тобто шлях комівояжера проходить: ABDCEA (повертається назад) разом 140 (хвилин).

На вирішення цього прикладу йде (реального часу): 1 хвилина (знайти саме мінімально час шляху) 3 хвилини (знайти і перевірити варіанти 130) 3 хвилини (знайти і перевірити варіанти 140). Разом 7 хвилин (за умови, що ви добре володієте усним рахунком час скорочується в два рази). На вирішення цього завдання складанням таблиці, записи всіх варіантів і т. д. (тобто офіційним методом) пішло б близько хвилин 20-ти, причому велика ймовірність помилок. Можливо що перебирати варіанти доведеться довше. Тоді можна спростити рішення задачі. Для цього знайдіть на ваш погляд найменше рішення для цього завдання і вже виходите з інтервалу {саме мінімально час шляху: ваше знайдене час шляху}.

Посилання на статтю: тут


  Схожі новини:
  •  Про один спосіб Підрахунку В Іграх
  •  Причини ненадійності криптографічну систему
  •  Дистанційне Навчання: Підготовка До ЄДІ
  •  Метрики Коду та їх практичної реалізації У Subversion І Clearcase. Частина ...
  • Www.nataxi.ru