|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
30.09.2011, 01:29 | #1 |
Пользователь
Регистрация: 14.04.2011
Сообщений: 31
|
Алгоритм Дейсктры
Доброго времени суток.Уважаемые форумчане возник вопрос.Качается вопрос алгоритма Дейкстры.Сам алгоритм впринципе понятен.Но я пишу его реализацию с некоторым упрощением. Точнее не полным пребором вершин а вершины перебеираются для каждой отдельно. т.е. вот с такой последовательностью.
1.Одна из вершин графа выбирается за начальный пункт маршрута, другая – за конечный. 2.h начального пункта маршрута принимаем равным нулю, h всех остальных вершин принимаем равными бесконечности. 3.Берем начальный пункт маршрута в качестве текущей вершины. 4.Отмечаем текущую вершину и пересчитываем h для каждой из смежных с ней вершин следующим образом: x[i].h=MIN(x[i].h , x[i].w+x[j].h), где x[j] – текущая рассматриваемая вершина, x[i] – текущая смежная вершина. Внимание! Если мы определяем h для уже отмеченной вершины x[i] и значение (x[i].w+x[j].h) оказалось меньше, чем x[i].h, то делаем ее Неотмеченной, чтобы затем пересчитать h для всех смежных с ней вершин. 5.Берем каждую из неотмеченных вершин, смежных с только что рассмотренной, в качестве текущей и проделываем для них п. 4 (и так до тех пор, пока все вершины не станут отмеченными). Если графически то это вот как http://clip2net.com/s/1cXTS http://clip2net.com/s/1cXUl http://clip2net.com/s/1cXUl http://clip2net.com/s/1cXV0 Хотя я реализовываю без диагональных ходов т.е. только влево вправо и вверх вниз напрямую от рассматриваемой вершины. Ну а после этих действий уже выбирается оптимальный маршрут.Так вот у меня возник вопрос можно ли каким то образом упростить механизм первоначальной разметки матрицы.Поскольку простой циклической структурой будет сложно разметить здесь похоже что удобней рекурсией .В общем у меня вышла перемудрёная структура.Можно ли её упростить как то.Я не понимаю как тут лучшим образом процедуру организовать поскольку каждый раз мы отправлять по идее по 8 индексов должны 2влево 2вправо 2вверх 2 вниз. Файл прилагается.Заранее благодарен. Последний раз редактировалось Nicko_mt; 30.09.2011 в 11:35. |
03.10.2011, 00:21 | #2 |
Пользователь
Регистрация: 14.04.2011
Сообщений: 31
|
Возник сопутствующий вопрос.Как правильно реализовать такую структуру как матрица матриц.Т.е. в начальной матрице есть у элемента(вершины) есть своя матрица которая содержит веса смежных ей вершин.
Впринципе реализовать реализовал но проблема с выводом.Взгляните пожалуйста кто может.Заранее благодарен. |
04.10.2011, 02:21 | #3 |
Пользователь
Регистрация: 14.04.2011
Сообщений: 31
|
Всё тему можно закрывать.Решение было найдено. Пришлось переписать код в другой среде с применением ООП поскольку структур здесь много.
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Алгоритм TMDS (Алгоритм передачи данных интерфейса DVI) | Pro4RE | Помощь студентам | 2 | 24.04.2011 21:55 |
Алгоритм | Eugene_Brikov | Помощь студентам | 0 | 17.04.2011 10:59 |
Алгоритм | Dmart92 | Помощь студентам | 1 | 05.03.2011 08:47 |
Алгоритм | Victor88 | Помощь студентам | 0 | 09.12.2010 13:12 |
Волновой алгоритм (алгоритм Ли) | MrRockchip | Общие вопросы C/C++ | 4 | 10.05.2010 13:26 |