Hyжны алгоpитмы pешения тpанспоpтной задачи

From

Evgenij Masherov (2:5020/175.2)

To

Alex Krivospitsky

Date

2002-10-19T12:41:52Z

Area

RU.ALGORITHMS

From: "Evgenij Masherov" <EMasherow@nsi.ru>

Sat Oct 19 2002 11:37, Alex Krivospitsky wrote to Evgenij Masherov:

 
 SI>>>> Есть такая вот задача: дана матpица, описывающая pасстояния
 SI>>>> междy пyнктами (гоpодами), так вот в этой матpице надо найти
 SI>>>> оптимальный (то есть наименьший) пyть, пpоходящий чеpез все
 SI>>>> пyнкты. То есть надо выбpать точкy отпpавления и описать
 SI>>>> маpшpyт. Интеpесyют алгоpитмы pешения такого типа задач, мож y
 SI>>>> кого завалялось?
 AK>>> точно эта задача решается только полным перебором. количество
 AK>>> итераций равно n!, где n - количество городов. можно попробовать
 AK>>> решить эту задачу при помощи нейронных сетей, например сети
 AK>>> хопфилда.
 EM>> Нет, здесь есть алгоритмы существенно лучшие полного перебора, скажем,
 EM>> ветвей и границ.

 AK> а он всегда дает лучшее решение?

Да. Он всегда дает оптимальное решение. В худшем случае за экспонениальное
время, однако в реальности полином.

Евгений Машеров АКА СанитарЖеня

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)