4

Тут питання з цим bottleneck. Зазвичай перекладають як вузьке місце, але тут таке означення:

In the bottleneck traveling-salesman problem, we wish to find the hamiltonian cycle that minimizes the cost of the most costly edge in the cycle.

Тобто, мінімізувати ціну найдорожчого ребра. Мені це так нагадує стратегію мінімакса, де треба мінімізувати максимально можливий програш. Тоді, якщо позначити довільний гамільтонів цикл через ГЦ, формула має такий вигляд:

min{ max{ вартість(ребро) | ребро ∈ ГЦ } | ГЦ }

Чи можна як мінімаксова задача комівояжера? Чи ще якісь варіанти?

  • Може це якось переоформити у відповідь? Було б добре для наступних поколінь і для статистики сайту. Також, вартість ребра може бути не тільки відстань, а справді вартість квитка чи ще щось. Щодо сходження маршруту, то 1+1+1+5 < 3+3+3+3, тобто це не вимагає зменшити найбільшу вартість ребра. – Yola Dec 15 '18 at 19:07
  • @Sasha а як іще тут можна зрозуміти мінімакс? Тобто, який ще максимум тут можна мінімізувати? – Yola Dec 15 '18 at 19:10
  • @Sasha гадаю те, що всередині min{max{...}} не має значення для назви методу – Yola Dec 15 '18 at 19:11
  • @Sasha так, з цифрами я помилився і ще я неправильно зрозумів про можливість припинення шляху. Щодо важливості того, що в дужках - ось. І взагалі. – Yola Dec 15 '18 at 19:33
  • @Sasha важилво, що і там, і там вживається це слово і принцип за вживанням цього слова один. Я міг би говорити і про прицип Куранта. Але з теорії ігор мінімакс наочніший. – Yola Dec 15 '18 at 20:18
3

Мін(і)максна/мін(і)максова задача комівояжера

Загалом, Ви можете назвати це мін(і)максною/мін(і)максовою задачею комівояжера. Навіть англійською її зрідка так називають, наприклад:

  • У «Guaranteed performance heuristics for the bottleneck travelling salesman problem» R. Gary Parker, Ronald L. Rardin:

    We consider constant-performance, polynomial-time, nonexact algorithms for the minimax or bottleneck version of the Travelling Salesman Problem.

  • Також «minimax travelling salesman problem» з'являється й у інших роботах, наприклад, 1, 2 і 3 С. І. Сергєєва й інших, 4 А. О. Алексєєва й інших, 5 Н. Н. Дорошка й інших, але я не маю доступу до цих робіт, тому не можу гарантувати, що вони саме про цю задачу (найімовірніше вони саме про це, але «minmax» з'являється також ще й в іншому варіанті задачі комівояжера — «m-travelling salesman problem» — коли він робить m циклів з однієї стартової вершини й мінімізує сумарну ціну найдорожчого циклу — наприклад, у 6 Paulo M. França, Michel Gendreau, Gilbert Laporte, Felipe M. Müller).

Хоча мені, якщо чесно, все ще не подобається такий переклад. Бо на мій погляд, назва «minimax TSP» фокусується на формальному вигляді формул — на відміну від назви «bottleneck TSP», яка фокусується на змісті. І навіть англійською перша зустрічається значно рідше за другу.

До мінімаксу, як стратегії в теорії ігор / прийняття рішень, ця задача не має прямого стосунку. Адже в цьому значенні мінімакс — це стратегія, визначена для частково непередбачуваних обставин (дії ігрових опонентів абощо), що полягає в тому, щоб діяти таким чином, щоб незалежно від того, як обернуться ці непередбачувані обставини, відвернути найбільше лихо. Тут у нас немає непередбачуваних обставин: ціни всіх ребер заздалегідь відомі, просто змінена цільова функція — ми мінімізуємо не суму цін ребер, а максимум цін ребер. Хіба що, якщо зводити ці задачу до іншої задачі, але тоді я тим більше застосував би іншу назву.

Інші варіанти перекладу

У російському перекладі це називається чимось на зразок задачі про комівояжера з униканням вузьких місць.

Якщо намагатися проектувати на реальне життя, то це комівояжер, який бажає не мінімізувати сумарні витрати на весь маршрут, а через якісь причини уникати дорогих (або «далеких» чи «довгих», якщо умовно вважати, що ціна — це відстань або час) переходів між вершинами. Наприклад, це може бути хворий комівояжер (якому в будь-який момент часу може знадобитися медична допомога, а чим «далі»¹ він від вершини, тим важче її отримати), або комівояжер на небезпечній території (чим «далі»¹ він від вершини, тим більший ризик зазнати нападу диких звірів або злодіїв), або ледачий/легковтомлюваний комівояжер (що вже через це намагається уникати «далеких» переходів). Отож, якщо Вам науковий редактор дозволить таку вільність, можна спробувати назвати це задачею ледачого/нерішучого/полохливого/швидковтомлюваного комівояжера — хоча я невпевнений.

¹ Під «відстанню» тут мається на увазі таке узагальнення:
• в момент перебування у вершині «відстань» до неї становить 0;
• в момент перебування в точці k, де 0≤k≤1, ребра u→v, ціна якого w, «відстані» до вершин u і v становлять kw і (1−k)w відповідно.
Це фактично і є інтуїтивним зведенням саме до мінімакс-задачі з теорії ігор: комівояжер обирає маршрут, опонент (доля, злодій тощо) обирає ребро, на якому станеться лихо й комівояжеру доведеться тікати у вершину, комівояжер намагається уникати дорогих ребер — тоді min{max{w(e)|e∈p}|p} перетворюється на max{min{v(a, b)|b}|a} з a=p, b=e, v(e, p) = −if(e∈p then w(e) else 0).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.