Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[18.206.238.189] |
|
Сообщ.
#1
,
|
|
|
Всем хай! Сходу к делу!
Проблема: я осознал, что не до конца выкупаю семантическое значение слова "релаксация", когда оно встречается при описании алгоритмов, например, графовых. relaxation ---> отдых to relax ---> отдыхать То бишь релаксация - синоним отдыха. Но отдыха ОТ ЧЕГО! К примеру, если есть чел, колющий дрова, он работает уже час. Решил присесть, отдохнуть, попить водички. Типа он релаксирует. Т е не выполняет никакой физической работы. Здесь все ясно. Перейдем на информационные рельсы. Читая статейки про описание графовых алгоритмов (Дейстра, Форда-Беллмана и пр.) иногда попадаются фразы аля: - происходит релаксация всех ребер, из нее исходящих - на данной итерации происходит релаксация множества вершин и т.п. и я чувствую, что НЕ ВЫКУПАЮ семантическое значение релаксации в этих контекстах! Чтобы что-то могло релаксировасть, это что-то должно заниматься какой-то работой ДО релаксации. Причем графы - чисто информационные модели в контексте программирования. Я не понимаю, КАК РЕБРА могут релаксировать... Чем они занимались до этого, чтобы приступить к этапу релаксации. Или имеется в виду, что они были использованы при расчетах, а сейчас требуется снова их пересчитать. Тогда слово релаксация здесь неуместно! Поясните простым языком, какое семантическое значение вкладывается в термин "релаксация", когда, например, идет описание графовых структур. Буду признателен! |
Сообщ.
#2
,
|
|
|
В данном случае это расслабление, ослабление напряжения.
Пусть по первичному пути проложена резинка. Путь неоптимален - резинка растянута. Итерация Дейкстры находит очередное улучшение - резинка перекидывается на более короткий путь, и натяжение ослабевает - вот и релаксация |
Сообщ.
#3
,
|
|
|
MBo, хм...
если я правильно понял, да, то можно ли релаксацией считать следующее: 1) уменьшение количества вершин во множестве? Типа меньше вершин, стало больше "пространства", происходит "расслабление", "уменьшение давления на стенки множества" 2) Если у графа тупо взять и удалить 2-3 ребра, то происходит своего рода тоже релаксация, т к ОСЛАБЕВАЕТ компонента связности этого графа? 3) Если значения ячеек весовой матрицы графа уменьшаются, то этого тоже своего рода релаксация матрицы весов? и т.п. |
Сообщ.
#4
,
|
|
|
Я не понял, о каком алгоритме и какой целевой функции сейчас идёт речь.
В алгоритмах поиска кратчайшего пути - понятно, что целевая функция, которую нужно минимизировать - длина пути. |
Сообщ.
#5
,
|
|
|
Цитата MBo @ Я не понял, о каком алгоритме и какой целевой функции сейчас идёт речь. я в целом привел примеры, без привязки к конкретному алгоритму или это некорректно так делать просто я хочу глубоко понять в целом смысл релаксации, как таковой Добавлено или релаксация, если грубо, то это процесс, который приводит к "улучшению"/оптимизации целевой ф-ции? |
Сообщ.
#6
,
|
|
|
>или релаксация, если грубо, то это процесс, который приводит к "улучшению"/оптимизации целевой ф-ции?
Да |
Сообщ.
#7
,
|
|
|
Цитата MBo @ Да т е по сути это получается очередной расчет все равно странновато, что ввели такой термин для обозначения РАБОТЫ/вычисления, а не для ничего не делания... ну, тут, конечно, сразу возникают моменты, типа, а если после вычисления целевая ф-ция стала НЕ лучше, а ХУЖЕ, то это уже будет не релаксацией и пр. и можно ли что-то релаксировать, если нет целевой ф-ции, хотя, наверное, а этих алгоритмах она всегда есть спс. Mbo за помощь! ЗЫ: но я бы не сказал, что я понял фундаментально логику релаксации и навряд ли бы смог качественно объяснить это кому-нибудь |