| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Поиск путей на графе
negrila © (2004-11-27 16:44:00)Здравствуйте, не поможет ли мне никто? Дело в том, что мне нужно найти минимальный по нагруженности дуг путь на графе и минимальный по кол-ву промежуточных вершин. Граф задан массивом NxN где на пересечении i-й строки и j-го столбца задан вес дуги i-j либо 0, если дуга отсутствует. Писать "смотри Дейкстру" не надо, смотрю уже неделю, но мозгов понять алгоритм с algolist.ru мне не хватает.
Xerx (2005-01-01 09:44:00) [1]negrila > Т.е. тебе нужен путь минимальной длины из A в B, где длина - уто сумма расстояний между узлами графа(вес)? Если так, то не парься ты с Дейкстрой!
wiz (2004-11-29 20:11:00) [2]во-первых, что подразумевается под "нагруженность дуг"? минимальность их количества??? или минимальность длины пути??
во-вторых, на первый взгляд мне показалось, что задача может быть несовместна - кратчайший путь может не совпадать с путём с минимальным количеством вершин.
а вообще - листок и ручка спасут отца русской демократии. В своё время, многие алгоритмы на графах мне стали понятны именно тогда, когда я попробовал порешать задачи с помощью своего мозга на конкретном графе в тетради.
2 negrila[1]: при том, что алгоритмы поиска пути - базовая штука для создания хоть сколько-нибудь пристойных компьютерных противников (читай AI)
XProger (2004-11-29 18:56:00) [3]negrila, айяйяй, скажи ещё что о waypoint не слыхал... ;)
Sapersky (2004-11-29 11:25:00) [4]http://www.caravan.ru/~alexch/
negrila (2004-11-28 12:53:00) [5]При чем тут игры?
| |
