На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Релаксация в алгоритмах (например, при обработке графов)
    Всем хай! Сходу к делу!
    Проблема: я осознал, что не до конца выкупаю семантическое значение слова "релаксация", когда оно встречается при описании алгоритмов, например, графовых.
    relaxation ---> отдых
    to relax ---> отдыхать
    То бишь релаксация - синоним отдыха. Но отдыха ОТ ЧЕГО! :wall:

    К примеру, если есть чел, колющий дрова, он работает уже час. Решил присесть, отдохнуть, попить водички. Типа он релаксирует. Т е не выполняет никакой физической работы. Здесь все ясно.

    Перейдем на информационные рельсы.
    Читая статейки про описание графовых алгоритмов (Дейстра, Форда-Беллмана и пр.) иногда попадаются фразы аля:
    - происходит релаксация всех ребер, из нее исходящих
    - на данной итерации происходит релаксация множества вершин
    и т.п.

    и я чувствую, что НЕ ВЫКУПАЮ семантическое значение релаксации в этих контекстах!
    Чтобы что-то могло релаксировасть, это что-то должно заниматься какой-то работой ДО релаксации. Причем графы - чисто информационные модели в контексте программирования. Я не понимаю, КАК РЕБРА могут релаксировать... Чем они занимались до этого, чтобы приступить к этапу релаксации. Или имеется в виду, что они были использованы при расчетах, а сейчас требуется снова их пересчитать. Тогда слово релаксация здесь неуместно!

    Поясните простым языком, какое семантическое значение вкладывается в термин "релаксация", когда, например, идет описание графовых структур. Буду признателен!
      В данном случае это расслабление, ослабление напряжения.
      Пусть по первичному пути проложена резинка. Путь неоптимален - резинка растянута.
      Итерация Дейкстры находит очередное улучшение - резинка перекидывается на более короткий путь, и натяжение ослабевает - вот и релаксация
        MBo, хм...
        если я правильно понял, да, то можно ли релаксацией считать следующее:
        1) уменьшение количества вершин во множестве? Типа меньше вершин, стало больше "пространства", происходит "расслабление", "уменьшение давления на стенки множества"
        2) Если у графа тупо взять и удалить 2-3 ребра, то происходит своего рода тоже релаксация, т к ОСЛАБЕВАЕТ компонента связности этого графа?
        3) Если значения ячеек весовой матрицы графа уменьшаются, то этого тоже своего рода релаксация матрицы весов?
        и т.п.
          Я не понял, о каком алгоритме и какой целевой функции сейчас идёт речь.
          В алгоритмах поиска кратчайшего пути - понятно, что целевая функция, которую нужно минимизировать - длина пути.
            Цитата MBo @
            Я не понял, о каком алгоритме и какой целевой функции сейчас идёт речь.

            я в целом привел примеры, без привязки к конкретному алгоритму или это некорректно так делать :no:
            просто я хочу глубоко понять в целом смысл релаксации, как таковой

            Добавлено
            или релаксация, если грубо, то это процесс, который приводит к "улучшению"/оптимизации целевой ф-ции?
              >или релаксация, если грубо, то это процесс, который приводит к "улучшению"/оптимизации целевой ф-ции?
              Да
                Цитата MBo @
                Да

                т е по сути это получается очередной расчет
                все равно странновато, что ввели такой термин для обозначения РАБОТЫ/вычисления, а не для ничего не делания...

                ну, тут, конечно, сразу возникают моменты, типа, а если после вычисления целевая ф-ция стала НЕ лучше, а ХУЖЕ, то это уже будет не релаксацией и пр.
                и можно ли что-то релаксировать, если нет целевой ф-ции, хотя, наверное, а этих алгоритмах она всегда есть

                спс. Mbo за помощь!

                ЗЫ: но я бы не сказал, что я понял фундаментально логику релаксации и навряд ли бы смог качественно объяснить это кому-нибудь
                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                0 пользователей:


                Рейтинг@Mail.ru
                [ Script execution time: 0,0283 ]   [ 16 queries used ]   [ Generated: 29.03.24, 11:21 GMT ]