Помогите пожалуйста!!!(задача на Pascal'е)

[jakysh]

Доброго времени суток всем!!!
не пойму как мне алгоритм применить к задаче!!! ПОМОГИТЕ ПОЖАЛУЙСТА
вот и алгоритм:
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]

Почти пятнашки =)
Я так думаю, что общая идея в построении графа состояний комнаты - каждая комбинация мебели в пространстве - вершина. Вершины, которые получаются одна из другой перестановкой одного предмета мебели, соединяются дугами. После построения выбираешь исходную точку и конечную точку (означающие исходную и конечную расстановку предметов в комнате) и натравливаешь на граф поиск в ширину для получения маршрута. Пройденные дуги и есть собсно шаги по перестановке мебели.

[jakysh]

Спасибо конечно!!! ещё бы понять как это написать на Паскале!!!что к чему привязать???
мы не писали ни одной проги по графам) я даже нее представляю как они организуются((( в лекциях два обзаца первый - определине графа, второй определение дерева!!!и фсё

[dn2k4]

"А есть вы за меня тоже будете, да?"

1) Пронумеровать все возможные состояния комнаты, их будет 5^6 штук (или 6^6 если стулья "2" считать разными предметами) - это будут вершины графа. Запомнить номера исходной и конечной точек.
2) Организовать структуру хранения вершин и дуг графа, учитывая, что из одной вершины в другую можно вести максимум 5 дуг (ну или меньше - если нельзя двигать по диагонали),
3) Запустить алгоритм, приведенный тобой с исходной точки, и гнать, пока не обработается финишная точка.
Алгоритм поиска в ширину объяснять не буду, это должны были сделать более умные дядьки до меня =)

Изначальная просьба была "...как мне алгоритм применить к задаче"...

[adrenalin]

dn2k4, научи меня расставить 6 предметов в комнате 46656 ю разными способами!
jakysh, чиайте книги. по волновым алгоритмам много писано-переписано...

[dn2k4]

adrenalin, да, это я шибко погорячился... Ну суть не меняется - будет у него 720 узлов, какая разница-то... 640 килобайт будет достаточно для каждого =)

[jakysh]

как это всё организуется в Паскале???какой тип имеет вершина???или чего???я ни разу не видел реализации графа в Паскале!!!!не писали проги вообще с графами!!!

[Constantine]

Ну а как ты думаешь? Можно использовать матрицу смежности. Если у нас N вершин, то имеем матрицу NxN, a(i,j) = 1 если вершина i смежна c j, и a(i,j) = 0 в противном случае. Все просто

[jakysh]

смежность это как???
как узнат что они передвинулись...мне это всё ещё графически деалть

[дядя Дима]

Смежность это просто. книжку хоть прочти по графам, иначе дальнейший диалог бессмысленен. смежна если от i есть "стрелка" к j

[Constantine]

Согласен с дядя Дима
Если возникают вопросы "а что такое смежность", то сабж следовало формулировать "Решите за меня задачу"

[jakysh]

спасибо всем кто писал здесь...
задача решена несколько другим спосбом...и преподователем принята...осталась одна загвоздочка сопственно вот она http://www.u-antona.vrn.ru/forum/sho...d.php?t=297282

[jakysh]

спасибо всем кто писал здесь...
задача решена несколько другим спосбом...и преподователем принята...осталась одна загвоздочка собственно вот она
http://www.u-antona.vrn.ru/forum/sho...d.php?t=297282