Доброго времени суток всем!!!
не пойму как мне алгоритм применить к задаче!!! ПОМОГИТЕ ПОЖАЛУЙСТА
вот и алгоритм:
3.3. Алгоритм поиска в ширину
Основная идея такого поиска – последовательный просмотр списков инцидентности вершин, смежных с данной. При поиске в ширину, попав в новую вершину, просматривают все смежные с ней непросмотренные вер-шины и заносит их в список, после чего эта вершина считается обработан-ной. Далее переходят в новую вершину, стоящую первой в списке необрабо-танных вершин. Иными словами, просмотр осуществляется по принципу очереди: чем раньше вершина просмотрена, тем раньше она будет обработа-на.
Сложность реализации алгоритма в том, что рекурсивные процедуры действуют по принципу стека, а не очереди. Поэтому в этом случае возможен только нерекурсивный вариант алгоритма
procedure BREADTH( v ) ;
begin ОЧЕРЕДЬ:=nil; {ОЧЕРЕДЬ – локальная структура }
ОЧЕРЕДЬ := v; NOWY[v]:= False;
while ОЧЕРЕДЬ <> nil do
begin p := ОЧЕРЕДЬ; write(p);
for u := СПИСОК[p] do
if NOWY[u] then
begin ОЧЕРЕДЬ := u;
NOWY[u]:= False
end
end
end;
Как мы уже говорили, основная программа отличается от соответствую-щей программы поиска в глубину только именем вызываемой во втором цикле процедуры.
А суть самой задачи такая:
ПЕРЕДВИНУТЬ мебель в комнате!!!условно это всё назовем так
1-стол
2-стул
3-шкаф
4-кресло
0-ничаво нету
изначальное расположение такое
1 2 3
2 0 4
необходимо поменять местами 3 и 4 и остальные предметы вернуть на своё же месте!!!
ЗЫ физмодель сделал!!!28 переприсваиваний!!!
ребят ну если не графами тогда как???просто очень срочно надо решить прогу!!!за мной не заржавеет!!!
[Ответ]
dn2k4 19:47 01.06.2008
Почти пятнашки =)
Я так думаю, что общая идея в построении графа состояний комнаты - каждая комбинация мебели в пространстве - вершина. Вершины, которые получаются одна из другой перестановкой одного предмета мебели, соединяются дугами. После построения выбираешь исходную точку и конечную точку (означающие исходную и конечную расстановку предметов в комнате) и натравливаешь на граф поиск в ширину для получения маршрута. Пройденные дуги и есть собсно шаги по перестановке мебели.
[Ответ]
jakysh 20:50 01.06.2008
Спасибо конечно!!! ещё бы понять как это написать на Паскале!!!что к чему привязать???
мы не писали ни одной проги по графам) я даже нее представляю как они организуются((( в лекциях два обзаца первый - определине графа, второй определение дерева!!!и фсё
[Ответ]
dn2k4 21:30 01.06.2008
"А есть вы за меня тоже будете, да?"
1) Пронумеровать все возможные состояния комнаты, их будет 5^6 штук (или 6^6 если стулья "2" считать разными предметами) - это будут вершины графа. Запомнить номера исходной и конечной точек.
2) Организовать структуру хранения вершин и дуг графа, учитывая, что из одной вершины в другую можно вести максимум 5 дуг (ну или меньше - если нельзя двигать по диагонали),
3) Запустить алгоритм, приведенный тобой с исходной точки, и гнать, пока не обработается финишная точка.
Алгоритм поиска в ширину объяснять не буду, это должны были сделать более умные дядьки до меня =)
Изначальная просьба была "...как мне алгоритм применить к задаче"...
[Ответ]
adrenalin 21:55 01.06.2008
dn2k4, научи меня расставить 6 предметов в комнате 46656 ю разными способами! jakysh, чиайте книги. по волновым алгоритмам много писано-переписано...
[Ответ]
dn2k4 22:04 01.06.2008
adrenalin, да, это я шибко погорячился... Ну суть не меняется - будет у него 720 узлов, какая разница-то... 640 килобайт будет достаточно для каждого =)
[Ответ]
jakysh 09:07 02.06.2008
как это всё организуется в Паскале???какой тип имеет вершина???или чего???я ни разу не видел реализации графа в Паскале!!!!не писали проги вообще с графами!!!
[Ответ]
Constantine 18:05 03.06.2008
Ну а как ты думаешь? Можно использовать матрицу смежности. Если у нас N вершин, то имеем матрицу NxN, a(i,j) = 1 если вершина i смежна c j, и a(i,j) = 0 в противном случае. Все просто
[Ответ]
jakysh 18:12 19.06.2008
смежность это как???
как узнат что они передвинулись...мне это всё ещё графически деалть
[Ответ]
дядя Дима 10:26 20.06.2008
Смежность это просто. книжку хоть прочти по графам, иначе дальнейший диалог бессмысленен. смежна если от i есть "стрелка" к j
[Ответ]
Constantine 15:08 22.06.2008
Согласен с дядя Дима
Если возникают вопросы "а что такое смежность", то сабж следовало формулировать "Решите за меня задачу"
[Ответ]