|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Viktor Karev 2:5080/1003 20 Mar 2003 13:07:04
To : Graf Alex
Subject : Re: Умная pекypсия
--------------------------------------------------------------------------------
Приветствия!
> >> Кто что дyмает по этомy поводy?
> VK> Поиск в шиpинy. Он же волновой алгоpитм.
> А по подpобнее можно?
> Конспект по дискpетке в моем стиле: как pаз в месте, где объясняется поиск
в
> шиpинy/гpyбинy - стоит пометка мол "все понятно....". Ессно самой лекции
нетy.
> Видимо тогда я это все понял, а сейчас вот чеpез 3 года yже забыл....
Прошу прощения. Более глубокие размышления показали, что я неправильно понял
задачу. Все-таки нужно применять поиск в глубину, но специального типа. А
именно - типа заполнения рюкзака. У тебя есть рюкзак заданного объема (в
твоем случае это - глубина отслеживания последовательности событий), Тебе
надо получить все возможные наборы, которые влезают в рюкзак. Критерий
стоимости не нужен. Объем каждого события равен единице.
Создаем массив событий и пытаемся получить все возможные допустимые наборы.
Предварительно массив следует частично упорядочить по зависимым событиям.
Если упорядочение невозможно из-за циклической зависимости каких-либо
событий, то эти события следует вообще исключить из рассмотрения.
Работаем с текущим множеством событий S, вначал пустым.
процедура проба_события(номер_события)
1: // пробуем добавить
если допустимо_добавление(номер_события) то
добавляем_событие(номер_события);
если достигнут_какой-либо_результат то
печатаем_результат
иначе
проба_события(номер_события+1);
конец если;
удаляем_событие(номер_события);
конец если;
2: // пробуем обойтись
проба_события(номер_события+1);
конец процедуры;
Виктор
--- ifmail v.2.15dev5
* Origin: Fidolook Express 2.000 www.fidolook.da.ru (2:5080/1003@fidonet)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
