Главная страница
    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.038 c
1-1110638833
[k]NikolaZ
2005-03-12 17:47
2005.03.27
Алгоритмы Архивирования


14-1109866583
kaif
2005-03-03 19:16
2005.03.27
Вопрос[1] О религии


1-1111053076
Dimich1978
2005-03-17 12:51
2005.03.27
очитисть array of Ansistring


8-1102814820
Black
2004-12-12 04:27
2005.03.27
как вывести звук с микрофона на прямую к колонкам?


3-1109259943
cherrex
2005-02-24 18:45
2005.03.27
Commit и CommitRetaining





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
Английский Французский Немецкий Итальянский Португальский Русский Испанский