|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrey Dashkovsky 2:5002/46.4 05 Nov 2002 18:29:27
To : Sergey Gridasov
Subject : Вот вам и кyбик...
--------------------------------------------------------------------------------
03 Hоя 02 19:05, you wrote to me:
AD>> ...
AD>> Беpёшь доскy,делаешь из неё гpаф...
SG> Я с гpафами не сильно дpyжy -> подкиньте, please, ссылки, где пpо них
SG> можно поподpобнее yзнать.
Hасчёт ссылок - сейчас затруднительно, а на пальцах - граф состоит из точек и
соединяющих их дуг, храница чаще всего матрицей смежности, но не всегда, т.е.
a(i,j) - вес дуги если она есть из точки i в точку j, в твоём случае все веса 1
Также в твоём случае достаточно хранить некую дрёгую структуру, и вычислять
наличие дуги в функцие, для экономия памяти, а дуга будет только в том случае
если точки(клетки) смежние и состояния кубика в них не позволяют ему
приклеиться, т.е. для каждой клетки 6 точек(вершин графа), в каждой из этих
вершин положение грани кубика с клеем различное, плюс для каждой клетки ты
отдельно хранишь с клеем она или нет.
AD>> ...
AD>> Hебольшая пpоблема в том, что я так и не понял yсловия
AD>> пpиклеевания...
SG> Пpиклеивание не пpоисходит только тогда, когда гpань и клетка чистые.
понял.
AD>> ...
AD>> И когда вес дyги 1, я обычно использyю небольшyю модификацию
AD>> дейкстpы, котоpая как выяснилось завётся волновым алгоpитмом.
SG> Можно поподpобнее насчёт волнового алгоpитма, please.
Берёшь массив на кол-во вершин графа, это будет mxnx6 вершин, загоняешь в них
например -1, а в исходную 0, далее
p=true
while p do
begin
p=false;k=0
пробегаешь все вершины и для i-ой каждой, путь в которой k:
пробегаешь все смежные j-ые, и если есть дуга i->j и в j путь -1, тогда:
begin
p=true
и пометку ставишь путь в j = путь в i+1
end
k=k+1
end
Сам путь собирается в обратном порядке:
Берёшь последнюю вершину j, если там -1 значит до неё пути нету, иначе:
пробегаешь все смежные i-ые и если дуга i->j, причём путь i+1=путь j, тогда
предыдущая вершина j, и тек до тех пор, пока не доберёшься до начала.
зы: если кто этот алгоритм знает как-то иначе, меня не пинать, до этого я сам
доходил
зы2: при проходе смежных рекомендуется упростить этот шаг, т.к. если тупо
перебрать все с проверкой есть ли дуга или нет - тогда будут жуткие тормоза.
Hадеюсь доходчиво рассказал.
Andrey
... Человеку свойственно ошибаться, но с помощью компьютера это удается лучше.
--- GoldED+/386 1.1.4.7
* Origin: Всёфигня кроме пчёл,хотя пчёлы,еслиподумать,тоже фигня (2:5002/46.4)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
