Читайте также:
|
Згідно методу динамічного програмування розв’язання починається з останнього етапу. Зафіксуємо 
- кінцеве місто, куди має потрапити комівояжер. При цьому комівояжер може знаходитись в 
, 
місті. Стан системи будемо представляти у формі Mi (0), де Аі - місто, в якому знаходиться комівояжер перед прийняттям рішення;
(0) - означає, що між кінцевим і даним містом відсутні проміжні міста. Така форма запису, є зручною та наочною.
Кожному стану системи (місцю перебування комівояжера) відповідає певний локальний дохід, який обчислюється як відстань DMi Mn від Мі до Мn міста.
Передостанній етап - комівояжеру треба потрапити в кінцеве місто, за умови, коли є одне проміжне місто. Тобто комівояжеру з міста Мi треба заїхати в проміжне місто, а звідти в Mn.
І так далі для всіх етапів, поки кількість проміжних міст не буде дорівнювати загальній кількості міст.
Дата добавления: 2015-08-17; просмотров: 76 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Пошук найкоротшого шляху кур’єра компанії «tianDE» на прикладі задачі кімівояжера | | | Приклад |