волновой метод, кратчайшее расстояние
Релиб
Форумы       Участники    Календарь    Кто он-лайн?
Добро пожаловать, гость ( Вход | Регистрация )
        



волновой метод, кратчайшее расстояние Expand / Collapse
Автор
Сообщение
01.07.2007 13:54
Forum Member

Forum MemberForum MemberForum MemberForum MemberForum MemberForum MemberForum MemberForum Member

участник
Last Login: 15.08.2008 21:32
Сообщ.: 33, Visits: 346
ниже рисунком привожу карту, нормальный вид карты можно увидеть по адресу http://2983.ru/road.jpg , на карте два варианта конечной точки (верхняя и нижняя)
где красное поле - непроходимая область,
желтое - проходимое
синее - конечная точка 'переменная
розовое - начальная 'переменная
цифрой "-5" - объявляю непроходимые поля, "-4" - поля где дорога равна нулю, "-2" нормальная дорога со стандартной длиной, "0" - конечная точка
первой группой циклов я заполняю массив M(i,j) или M(12,8) количеством переходов, причем расстояния с "нулевым" переходом не увеличивают путь...
 
Теперь требуется обратным методом дойти до конца... 
мои идеи: если M(2,5)=M(3,5)-1 тогда записываем в например пустые массивы A(n) и B(n) значения 3 и 5 соответственно на n=1, где n-максимально возможное количество переходов, только как все это сунуть в массив... учитывая что например начальному полю соответствует так же еще одна ячейка с таким же значением...
 
P.s. косяк так же если конечная(начальная) точка находится рядом с нулевым путем...
Сообщ. #914454
01.07.2007 18:34
Forum Member

Forum MemberForum MemberForum MemberForum MemberForum MemberForum MemberForum MemberForum Member

участник
Last Login: 15.08.2008 21:32
Сообщ.: 33, Visits: 346
есть идея дальше пойти вот так:
 
'очистка массивов с координатами проходов 
for n=1 to 13 step 1 ' n - максимально возможное кол-во переходов + 1 на всяк случай
A(n)=0
B(n)=0
next n
' цикл поиска пути
f = 13 ' случайное число для точки отсчета
M(2,5) = 13 'присвоил чтоб найти начало
for n = 1 to 13 step 1
for i = 2 to 11 step 1
for j = 2 to 7 step 1
 
if M(i+1,j) = 0 then ' проверяем не это ли конечная точка
goto 100 'как подругому выйти не знаю
end if
' такие циклы для всех M(i+1,j), M(i,j+1), M(i-1,j), M(i,j-1)
 
if M(i,j) = f and M(i+1,j) < M(i-1,j) and M(i+1,) < M(i,j+1) and M(i+1,j) < M(i,j-1) and M(i+1,j) > -5  then ' ищем самую маленькую координату вокруг, но чтоб была больше -5
A(n) = i+1
B(n) = j
M(i+1,j)=f+1 ' присваиваем значение на единицу больше
end if
' такие циклы для всех M(i+1,j), M(i,j+1), M(i-1,j), M(i,j-1)
next j
next i
f = f + 1 ' увеличиваем для следующего прохода...
next n
100 далее...
 
В результате получаем по идее массивы A(n) и B(n) с последовательностью координат точек прохода...терь вопрос просто по незнанию...как заставить выполняться команды в соответсвии с путем, т.е. например:
есть A(1)=3 и B(1)=5 это координата пути первого шага, нужно чтобы к этой точке была привязана функция (post запрос в инет)...
далее A(2)=4 и B(2)=5 следующая функция....
Сообщ. #914456
01.07.2007 18:54
Forum Member

Forum MemberForum MemberForum MemberForum MemberForum MemberForum MemberForum MemberForum Member

участник
Last Login: 15.08.2008 21:32
Сообщ.: 33, Visits: 346
попробую объяснить проще...
 
или в нормальном виде - http://2983.ru/road2.jpg 
 
т.е. к каждой координате привязана должна быть определенная функция и программа потом следуя по массивам A и B должна выполнить функцию соответствующую координатам M( A(1),B(1) ), далее M( A(2),B(2) ), и т.д. до 13-ой...
Сообщ. #914457
01.07.2007 18:59
Forum Member

Forum MemberForum MemberForum MemberForum MemberForum MemberForum MemberForum MemberForum Member

участник
Last Login: 15.08.2008 21:32
Сообщ.: 33, Visits: 346
можно по идее сделать еще цикл n = 1 to 13 и впихнуть кучу if, равное количеству доступных к проходу клеток, а их 29 штук:
if A(n) = 1 and B(n) = 1 then
h=p(10)
else if A(n) = 2 and B(n) = 1 then
h=p(20)
... и т.д.....
next n
 
но мож можно как покороче...ибо чет писанины уж очень....
 
P.s. в проге-клиенте уже совсем мало остается букв под переменные...)))))))))
P.s.s. диалог сам с собой, но если у кого есть идеи как укоротить или ченить обсудить - буду очень рад...
Сообщ. #914458
01.07.2007 22:13
Forum Member

Forum MemberForum MemberForum MemberForum MemberForum MemberForum MemberForum MemberForum Member

участник
Last Login: 15.08.2008 21:32
Сообщ.: 33, Visits: 346
есть ошибка....в обратном ходе нужно еще goto на конец циклов вешать, иначе путь "распушается" и получается фигня...
и еще нужно там же в обратном ставить "<=" вместо "<", а то тож косяк...
 
P.s. удивляюсь как я раньше в школе/ВУЗе любил математику....дискретка жесть как вспоминается...еще чуть чуть и убьюсь апстенку...
Сообщ. #914460
09.07.2007 16:31
Supreme Being

Supreme BeingSupreme BeingSupreme BeingSupreme BeingSupreme BeingSupreme BeingSupreme BeingSupreme Being

участник
Last Login: 09.07.2007 16:29
Сообщ.: 178, Visits: 1 955
я всегда решал подобные задачи рекурсивно (если нет доп требований - наприм - производительность)
Сообщ. #914590
« пред. тема | след. тема »


Эту тему читают Expand / Collapse
Посетители: 0 (0 гостей, 0 участников, 0 скрыт.участников)
Сейчас нет участников, просматривающих тему.
Модераторы: Alexey, boombastik, bazile, pl, Comanche, Alexey Spirin

Время GMT +3:00, Сейчас 2:46