| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Задача коммивояжера метод ветвей и границ |
| Автор: n4ela 25.9.2009, 02:34 |
| Решил что создать новую тему будет правильнее. Пишу программу для решения задачи коммивояжера, методом ветвей и границ. Столкнулся с тем что не понимаю один шаг в алгоритме. Вот есть матрица с произведенной редукцие строк и столбцов http://ipicture.ru/ По ней получается что максимальное значение Ai+Bj = 10 т.е. звено 1;4 Получается что мы вычеркиваем 1-у строку и 4-ый столбец А на место элемента 4,1 берем бесконечность http://ipicture.ru/ Тут получается что максимальное значение = 16, следовательно берем звено 2;1 Вычеркиваем 2-ую сроку и 1-ы столбец Значит мы должны поставить символ бесконечности заместо элемента 1;2 Но в книжке по которой я это делаю берется элемент 4;2 http://ipicture.ru/ Вопрос почему? Какой принцип этого действия? Я думал что мы просто из звена которое у нас получилось, (например 1,4 меняем местами цифры т.е. 4,1 и ставим бесконечность за место этого элемента) Смотрел в двух книжках(с разными исходными данными) объяснения не нашел. |
| Автор: motorway 26.9.2009, 00:12 |
| А я хотел спросить: можно ли свести эту задачу к системе отношений в виде уравнений и неравенств + логические условия, для которой нужно определить решение? Насколько я понял, здесь нужно максимизировать функцию, т.е. фактически все равно это система отношений в виде уравнений и неравенств, и нужно определить коэф-ты целевой функции? |