|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgenij Masherov 2:5020/175.2 19 Oct 2002 12:41:52
To : Alex Krivospitsky
Subject : Hyжны алгоpитмы pешения тpанспоpтной задачи
--------------------------------------------------------------------------------
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>> Hет, здесь есть алгоритмы существенно лучшие полного перебора, скажем,
EM>> ветвей и границ.
AK> а он всегда дает лучшее решение?
Да. Он всегда дает оптимальное решение. В худшем случае за экспонениальное
время, однако в реальности полином.
Евгений Машеров АКА СанитарЖеня
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
