Главная страница
Top.Mail.Ru    Яндекс.Метрика
Текущий архив: 2005.03.27;
Скачать: CL | DM;

Вниз

Поиск путей на графе   Найти похожие ветки 

 
negrila   (2004-11-27 16:44) [0]

Здравствуйте, не поможет ли мне никто? Дело в том, что мне нужно найти минимальный по нагруженности дуг путь на графе и минимальный по кол-ву промежуточных вершин. Граф задан массивом NxN где на пересечении i-й строки и j-го столбца задан вес дуги i-j либо 0, если дуга отсутствует. Писать "смотри Дейкстру" не надо, смотрю уже неделю, но мозгов понять алгоритм с algolist.ru мне не хватает.


 
negrila   (2004-11-28 12:53) [1]

При чем тут игры?


 
Sapersky   (2004-11-29 11:25) [2]

http://www.caravan.ru/~alexch/


 
XProger ©   (2004-11-29 18:56) [3]

negrila, айяйяй, скажи ещё что о waypoint не слыхал... ;)


 
wiz ©   (2004-11-29 20:11) [4]

во-первых, что подразумевается под "нагруженность дуг"? минимальность их количества??? или минимальность длины пути??

во-вторых, на первый взгляд мне показалось, что задача может быть несовместна - кратчайший путь может не совпадать с путём с минимальным количеством вершин.

а вообще - листок и ручка спасут отца русской демократии. В своё время, многие алгоритмы на графах мне стали понятны именно тогда, когда я попробовал порешать задачи с помощью своего мозга на конкретном графе в тетради.

2 negrila[1]: при том, что алгоритмы поиска пути - базовая штука для создания хоть сколько-нибудь пристойных компьютерных противников (читай AI)


 
Xerx ©   (2005-01-01 09:44) [5]

negrila > Т.е. тебе нужен путь минимальной длины из A в B, где длина - уто сумма расстояний между узлами графа(вес)? Если так, то не парься ты с Дейкстрой!



Страницы: 1 вся ветка

Текущий архив: 2005.03.27;
Скачать: CL | DM;

Наверх




Память: 0.48 MB
Время: 0.028 c
1-1110444992
juice
2005-03-10 11:56
2005.03.27
Отладка


3-1109307125
alex_pv2
2005-02-25 07:52
2005.03.27
ADO+MSSQL


3-1109330164
Inoemy
2005-02-25 14:16
2005.03.27
Как взять значение DataSet по заданному номеру строки грида?


3-1109448613
serko
2005-02-26 23:10
2005.03.27
Очистка базы


4-1108312250
Алексей
2005-02-13 19:30
2005.03.27
Не получается, отловить сообщения комбобокса, переполнение стека