ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Andrzej Novosiolov                   2:5020/400     31 Jul 2001  12:44:23
 To : Stepan Kuznetsov
 Subject : Re: Лабиринт
 -------------------------------------------------------------------------------- 
 

 On Tue, 31 Jul 2001 01:28:46 +0400, Stepan Kuznetsov wrote:
 
 SK>>> Подскажите алгоpитм для pешения такой задачи: нужно на "поле"
 SK>>> pазмеpом x на y, постpоить лабиpинт с m входами, и n выходами.
 
 Уточни, что подразумевается под "m входами и n выходами". Чем входы отличаются
 от выходов, кроме висящих рядом с ними табличек? :) Требуется ли полная
 связность (от любого входа можно дойти к любому из выходов), или, напротив,
 неполная?
 
 В своё время у меня получались достаточно красивые связные лабиринты с
 применением следующего алгоритма:
 
 1. Выбираем на границе поля произвольную точку. Она образует список текущих
 точек A. В переменной N будем хранить количество точек, принадлежащих проходам
 лабиринта (на этом шаге N = size(A) = 1). 
 
 2. Перебирая список A от головы к хвосту, для каждой точки выполняем пункты
 (2a-2d).
 
 2a. Составляем два списка точек, соседних с текущей точкой из списка A: B -
 точки, ещё не являющиеся частью лабиринта, и C - точки, через которые уже
 проходит какая-либо ветка лабиринта, но ещё не соединённые проходами с текущей
 точкой. 
 
 2b. Выбираем случайное число PB: 0 <= PB <= size(B). Из списка B случайным
 образом выбираем PB точек, соединяем их проходами с текущей точкой и добавляем
 в хвост списка A. N := N + PB.
 
 2c. Выбираем случайное число PС: 0 <= PС <= size(С). Из списка С случайным
 образом выбираем PС точек и соединяем их проходами с текущей точкой.
 
 2d. Удаляем текущую точку из списка A.
 
 3. Если полученный лабиринт нас устраивает, то переходим к пункту 7. (В
 качестве критерия можно использовать условие N >= Nmax(x*y), или подсчитать N1
 - количество точек лабиринта, находящихся на краю поля и потребовать N1 >= m +
 n, или любые другие условия, по вкусу)
 
 4. Выбираем произвольное множество точек, не являющихся частью лабиринта, для
 которых size(C) > 0 (то есть соседних с какой-либо точкой лабиринта).
 Добавляем их в список A. N := N + size(A)
 
 5. Перебирая список A от головы к хвосту, для каждой точки выполняем пункт
 (5a).
 
 5a. Выбираем случайное число PС2: 0 < PС2 <= size(С). Из списка С случайным
 образом выбираем PС точек и соединяем их проходами с текущей точкой.
 
 6. Переходим к пункту 2.
 
 7. Составляем список точек лабиринта, находящихся на краю поля, и каким-либо
 образом выбираем из них m входов и n выходов (вероятно, делая входы и выходы
 более-менее равноудалёнными и следя, чтобы длина минимального пути от каждого
 входа до каждого выхода была не слишком маленькой)
 
 Примечания: распределения случайных чисел PB, PC и PC2 лучше брать не
 равномерными. Вероятности проще всего подобрать эмпирически, добиваясь
 желаемого количества ветвлений, тупиков и циклов.
 
 ... 2:463/1124.5@fidonet, ICQ 8481158, http://surf.to/andrzej
 --- ifmail v.2.15dev5
  * Origin: SoftElegance (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Лабиринт   Stepan Kuznetsov   29 Jul 2001 23:53:17   Лабиринт   Dron Grigoriev   30 Jul 2001 08:59:56   Лабиринт   Stepan Kuznetsov   31 Jul 2001 02:28:46   Лабиринт   Dron Grigoriev   31 Jul 2001 08:50:08   Re: Лабиринт   Andrzej Novosiolov   31 Jul 2001 12:44:23   Лабиринт   Vladimir Polyanin   01 Aug 2001 00:22:54   Лабиринт   Egorov Pavel   03 Aug 2001 08:20:28