Показать сообщение отдельно
  (#6 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,961
Сказал(а) спасибо: 2
Поблагодарили 303 раз(а) в 303 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 06.04.2005, 11:11

Цитата:
т.е. если решать метод ветвей и границ, то могут некоторые задачи не решиться
Если количество вершин графа невелико (~ до 17-19), то задача решится.

Цитата:
А то я сделала этим методом, и если рассматривать случай: городов>5 и все стороны одинаковые, то программа не работает!!! этот метод предусматривает такие проблеммы???
1. Это вина не метода, а программиста. Вы уж меня извините, но где-то у Вас в алгоритме промашка вышла.
2. Если в прогу ввести эвристику, что мол веса связей у графа - целочисленные (и положительные), то прога в Вашем случае мгновенно (за один проход) поймёт, что любой цикл - минимальный, и сразу выдаст решение.
3. Если в прогу ввести эвристику об одинаковости всех путей (проверяется априорно), то прога также, найдя первый попавшийся цикл, выдаст решение.
Ответить с цитированием
Ads