Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Способы защиты от зацикливания.

Страницы: < 1 2
Riply © (2007-08-16 02:13:00)
Здравтсвуйте !
Допустим, мы работаем следующим образом:
Читаем адрес, идем по нему.
Там читаем следующий адрес и, снова, переходим на него.
И т.д., пока не получаем метку что данный адрес - последний.
Допустим, мы уверены, что она (метка) существует.
Какие методы определения, что мы стали ходить по кругу существуют ?
(Например, семнадцатый по счету адрес отправил нас на четвертый).
P.S.
Надеюсь не очень сумбурно объяснила :)

Riply (2007-08-16 12:29:00) [21]
> [8] oldman © (16.08.07 12:21)
>А если адрес повторился, а вот по кругу не ходим?
>1-2-3-4-5-1-7-8
Если адрес повторился, то ходим. Т.к. в нем (1 в примере) лежит 2.
Если мы снова попадаем в 1, то он снова пошлет нас на 2 :)
А пока мы бродим адреса не переписываются.

Riply (2007-08-16 12:26:00) [22]
> [7] Slym © (16.08.07 12:02)
> проще красить вершины (1 бит на вершину)
Не поняла. Как "1 бит на вершину" ?
Допустим я стою в начале "Великого Пути", имея на руках только один первый Pointer.
Пошла по нему, чтобы получить второй. Как мне покрасить первый, кроме как запомнить 4 байта ?

oldman (2007-08-16 12:21:00) [23]
А если адрес повторился, а вот по кругу не ходим?

1-2-3-4-5- 1-7-8

> Ох, если с каждого адреса переход только в 1 другую вершину,
> то конечно же дело упрощается

Slym (2007-08-16 12:02:00) [24]
проще красить вершины (1 бит на вершину)

Riply (2007-08-16 07:58:00) [25]
>[1] ferr © (16.08.07 02:30)
>Тема хорошо разобрана в книгах
>1) Кормен Лайзерсов Ривест "Алгоритмы : построение и анализ"
>2) Седжвик "Фундаментальный алгоритмы на C++" 4-ая часть, 2-ая книга.
Спасибо.

>[3] MBo © (16.08.07 06:58)
Этот способ мне больше понравился (по "понятности" и трудозатратам на реализацию :)

>[5] ferr © (16.08.07 07:21)
>P.S. Прекращаю обсуждать такую простую задачу. =)
Из того, что существует индивид, для которого данная задача является простой,
совсем не следует, что она проста и для другого, случайно выбранного, индивида.
Во как завернула :)

ferr (2007-08-16 07:21:00) [26]
Естественно крася мы тратим O(N) по памяти, но за это получаем дополнительную информацию. Также в большинстве случаев этот метод будет работать явно чуточку быстрее, хотя асимптотики естественно одинаковые.

P.S. Прекращаю обсуждать такую простую задачу. =)

ferr (2007-08-16 07:13:00) [27]
> Задача на обнаружение цикла в однонаправленном списке.
> Пускаем по списку два указателя, один идет с двойной скоростью,
> второй - с одинарной. Если есть цикл, то они встретятся.

Ох, если с каждого адреса переход только в 1 другую вершину, то конечно же дело упрощается, что-то я и не заметил.

А разьве Ваш подход имеет практический интерес? Не проще ли красить пройденные вершины в чёрный цвет?

P.S. Мозг соображает неважно, ввиду недосыпа.

MBo (2007-08-16 06:58:00) [28]
Задача на обнаружение цикла в однонаправленном списке.
Пускаем по списку два указателя, один идет с двойной скоростью, второй - с одинарной. Если есть цикл, то они встретятся.

ferr (2007-08-16 02:32:00) [29]
Кстати для отображения адреса на номер вершины графа я бы посоветовал использовать хеширование.

Например в c#

Dictionary<string, int> refl;

ferr (2007-08-16 02:30:00) [30]
Ваши походы можно представить в виде такой математической структуры как граф. Ваш граф ориентированный. Вам надо проверить является ли он DAG-ом(Direct Acyclic Graph). Это делается одним обходом в глубину за время O(V+E). Это если задан весь граф.

Если же он строится в процессе работы, и если в результате получается(что вероятно) дерево обхода в глубину то вам достаточно на каждом шаге проверять наличие обратных рёбер. Если обход идёт по другой стратегии то надо смотреть отдельно.

Объяснил ещё более сумбурно, 5ый час утра таки. Спрашивайте, отвечу. Задача кстати достаточно лёгкая.

Тема хорошо разобрана в книгах
1) Кормен Лайзерсов Ривест "Алгоритмы : построение и анализ"
2) Седжвик "Фундаментальный алгоритмы на C++" 4-ая часть, 2-ая книга.

Страницы: < 1 2

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »