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

    Начальная ячейка (5,1)
    user posted image

    Может есть какой нибудь алгоритм?

    Основная проблема в том, что в строке могут быть несколько -1 и 1. Как реализовать запоминание тех ячеек, которые уже обработаны, а которые еще нет? :wacko:
      >Основная проблема в том, что в строке могут быть несколько -1 и 1
      если строки соответствуют дугам, то этого не может быть (у дуги одно начало, один конец, в остальных элементах строки нули)

      собственно, сама задача - как мне кажется из условия - смахивает на нахождение Эйлерова цикла в графе (пройти по всем ребрам один раз, вершины могут повторяться). Хотя условие обхода всех ребер не озвучено...
        да обходить все вершины не нужно
        и все-таки мне кажется, что эйлеров цикл это нечто другое :no-sad:
          А, когда писал прошлый пост, картинку не видел.
          Здесь дуги по столбцам идут, а вершины по строкам.
          Можно выполнять обход в ширину, пока не наткнемся на начальную ячейку. Таким образом будет найден кратчайший цикл.
          При обходе ячейки помечаются, чтобы дважды не заходить
            Цитата luna82 @
            Основная проблема в том, что в строке могут быть несколько -1 и 1. Как реализовать запоминание тех ячеек, которые уже обработаны, а которые еще нет?

            Прибавляй к значениям обработанных ячеек, скажем, 100. При необходимости снять отметку отнимешь 100 взад.
              С пометкой вершин всё понятно теперь. :thanks:
              А как реализовать движение по графу?
              И то что после -1 нужно искать 1, потом опять -1 и т.д.
              Может сделать 2 процедуры для поиска по строкам и по столбцам и передавать значение ячейки, в которой в данный момент находимся... :-?
                Если находимся в ячейке с -1 - ищем в столбце +1, переходим туда. Больше ничего делать не надо, вариант однозначный.
                Если в ячейке с +1 - перебираем все ячейки с -1 в данной строке.
                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                0 пользователей:


                Рейтинг@Mail.ru
                [ Script execution time: 0,0384 ]   [ 15 queries used ]   [ Generated: 17.06.24, 14:40 GMT ]