Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Игры";
Текущий архив: 2005.03.27;
Скачать: [xml.tar.bz2];

Вниз

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

 
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;
Скачать: [xml.tar.bz2];

Наверх




Память: 0.45 MB
Время: 0.049 c
1-1110808721
lehich
2005-03-14 16:58
2005.03.27
winexec и передаваемые параметры


4-1108623210
dak_brn
2005-02-17 09:53
2005.03.27
Управление ICQ клиентом из Delphi


1-1110791122
qwe
2005-03-14 12:05
2005.03.27
FindFirst


3-1109782180
Bogdan
2005-03-02 19:49
2005.03.27
Как усмерить Excel


1-1110874865
Гость
2005-03-15 11:21
2005.03.27
Как сделать, чтоб нельзя было "уйти" из формы без ее закрытия?





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский