Шукати за:
Роком видання
Автором
Назвою статті
Швидкий алгоритм розв’язання задачі про призначення для знаходження нижньої межі вартості маршруту комівояжера
Повний текст (PDF)
УДК: 519.161
Мова публікації: Російська
Stuc. intelekt. 2011; 16; (4):406-416
Анотація: Показано, що якщо в оптимальному розв’язку задачі про призначення (ЗП) та її матриці вартостей порядку n замінити значення якого-небудь елемента на нескінченно велике число, то оптимальний розв’язок ЗП для отриманої матриці знаходиться за час О(n²).
Ключові слова:
Посилання:
- Kristofides N. Teorija grafov. Algoritmicheskij podhod. M.: Mir. 1978 . 432 s.
- Papadimitriu H. Kombinatornaja optimizacija. Algoritmy i slozhnost'. M.: Mir. 1975. 510 s.
- Panishev A.V. Modeli i metody optimizacii v probleme kommivojazhera. Zhitomir: ZhGTU. 2006. 300 s.
- Borhanov I.F. Uchenye zapiski Kazanskogo gosudarstvennogo universiteta. Fiziko-matematicheskie nauki.2006. T 148. Kn 2. S 18-22