Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Интересные и занимательные задачи по программированию > Автостоянка


Автор: klimskiy 19.6.2005, 20:32
Подскажите как решить такую задачу:
автостоянка имеет форму клеточного поля. Одна клетка на границе является выездом с автостоянки. Любой автомобиль занимает 2 соседние клетки (не по диагонали)
Написать программу поиска размещения максимального кол-ва автомобилей, такого что любой автомобиль имеет возможность выезда.
Автомобиль может выехать, если у его границ есть хотя бы одна свободная клетка (не по диагонали), и перемещаясь по свободным клеткам, он может "добраться" до выезда.

Прошу помочь с идеями, алгоритмами и т.д. В принципе я неплохой программист, но еще неопытный (первокурсник). Мне кажется эта задача немного рановата для меня так как мы еще даже недопрошли способы задания графа, а по всей видимости тут без этого не обойтись, и к тому же до методов оптимизации еще учится и учится. ПРошу подать методы решения этой задачи с кратким пояснением (так как эти методы еще не учил, и их названия мне мало помогут). Заранее благодарен!

Автор: Fedor 19.6.2005, 20:54
klimskiy А какие ограничения на размер автостоянки? Я просто подумал, может эту задачу полным перебором решить?

Автор: klimskiy 19.6.2005, 21:48
ограничение на размеры автостоянки не заданы (ну я думаю в разумных пределах). размер поля задает юзер N*M. Вот так вот. Я тоже так думал, что надо полным перебором (поскольку других способов пока что я не знаю smile ) Ну даже если и полным, то все равно сложновато

Автор: Fedor 19.6.2005, 22:14
Перемещу-ка я эту тему в другой раздельчик...

Автор: klimskiy 19.6.2005, 22:27
Fedor Переместить та ты переместил, а подсказать не подсказал smile Лесно, что моя задачка в таком матёром разделе smile

Автор: Fedor 19.6.2005, 23:22
Цитата(klimskiy @ 19.6.2005, 22:27)
Fedor Переместить та ты переместил, а подсказать не подсказал

просто не знаю что сказать... У меня завтра экзамен, я после экзамен приду, подумаю... Интересная на первый взгляд задача.
Но вроде графы тут не причем...

Автор: Akina 19.6.2005, 23:26
Задачка действительно любопытная... нет, то есть построить заполнение - элементарно, проблема доказать что получен максимум... бум подумать.

Автор: dvs 20.6.2005, 01:02
Решается просто:
1. Строим граф в виде сетки NxM
2.Строим минимальное стягивающее дерево, но (классические алгоритмы Остовное дерево наименьшей стоимости, алгоритмы Прима и Краскала)
3. От въезда/выезда тянем дорогу...
4. Концы, точнее листья получишегося дерева - места для машин.

Интересный момент в задаче - не нужно расстанавливать автомобили, нужно прокладывать дорогу, тогда, по-моему, проще решать.

Решение в действии не проверял - не хватает времени, но это должно работать. На листочке получилось!

Описание алгоритма(Реализация на Паскале(Делфи)):

Цитата


Построение минимального остовного дерева (алгоритм Краскала)
Алгоритм предназначен для нахождения минимального остовного дерева, т.е. такого подграфа который бы имел столько же компонент связности, сколько и исходный, но не содержал петель и сумма весов всех его ребер была бы минимальной.
Вначале опишем алгоритм (возможно не достаточно строго), а затем обсудим какой способ задания графа был бы наилучшим в данном случае, а так же покажем как от тех способов задания, которые мы использов
али ранее перейти к способу применимому здесь.
Итак, алгоритм Краскала:
1. Сортируем ребра графа по возрастанию весов.
2. Полагаем что каждая вершина относится к своей компоненте связности.
3. Проходим ребра в "отсортированном" порядке. Для каждого ребра выполняем: а) если вершины, соединяемые данным ребром лежат в разных компонентах связности, то объединяем эти компоненты в одну, а рассматриваемое ребро добавляем к минимальному остовному дереву б) если вершины, соединяемые данным ребром лежат в одной компоненте связности, то исключаем ребро из рассмотрения.
4. Если есть еще нерассмотренные ребра и не все компоненты связности объединены в одну, то переходим к шагу 3, иначе выход.
В данном случае работать с матрицей весов не удобно, это выявляется уже на этапе упорядочивания ребер по весу, поэтому создадим временный массив ребер Edges: array of TEdges с соответствующими весами. Каждый элемент этого массива имеет три свойства: начальная вершина, конечная вершина и вес.
 TEdges=record          // временная структура для ребер
   n1: word;            // № первой вершины
   n2: word;            // № второй вершины
   A : integer;         // вес ребра
 end;
Упорядочиваем ребра по неубыванию весов пузырьковой сортировкой. Далее в алгоритме вводиться массив Link: array of integer элементы, которого характеризуют номер компоненты связности соответствующих вершин (две вершины u1, u2 лежат в одной компоненте связности, если и только если Link[u1] = Link[u2]). Теперь все структуры, используемые в алгоритме, описаны, и его работу легко будет понять из блок-схемы.
В алгоритме используется переменная q, которая инициализируется значением N-1 и затем, при объединении двух компонент связности на шаге 3, q уменьшается на единицу, таким образом, условие q=0 означает, что все вершины лежат в одной компоненте связности и работа алгоритма завершена.
Найденное дерево будет определено с помощью стека, в который мы помещаем номера ребер.
Алгоритм Краскала
 procedure Craskal;
 // Алгоритм Краскала
 var i,j,q,m,t: integer;
     h: TEdges;
     Link: array of integer;// № связности для вершин
 begin
   ClearVisit; Stack_Init(Stack);
   N:=Length(Node); m:=0;
   for i:=0 to N-1 do    // формируем массив всех ребер
   with Node[i] do begin
     LL:=Length(Edge);
     for j:=0 to LL-1 do begin
       Inc(m); SetLength(Edges,m);
       Edges[m-1].n1:=i; Edges[m-1].n2:=Edge[j].NumNode;
       Edges[m-1].A:=Edge[j].A;
     end;
   end;

   for i:=0 to m-2 do // Сортируем ребра графа по возрастанию весов
   for j:=m-1 downto i+1 do
   if Edges[j].A<Edges[j-1].A then begin
     h:=Edges[j]; Edges[j]:=Edges[j-1]; Edges[j-1]:=h;
   end;

   SetLength(Link,N); // Вначале все ребра в разных компонентах
                      // связности
   for i:=0 to N-1 do Link[i]:=i;

   i:=0; q:=N-1;
   while (i<=m-1) and (q<>0) do begin
     // если вершины в разных компонентах связности
     if Link[Edges[i].n1]<>Link[Edges[i].n2] then begin
       t:=Edges[i].n2; Push(Stack,i); // поместить в стек № ребра
       for j:=0 to N-1 do
         if Link[j]=t then
           Link[j]:=Link[Edges[i].n1];// в один компонент связности
       q:=q-1;
     end;
     Inc(i);
   end;
   SetColorEdge; // закраска ребер
   SetLength(Edges,0);
 end;
Процедура SetColorEdge извлекает номера ребер из стека и перекрашивает ребра структуры Node[i] (листинг 14.39)
Закраска ребер минимального остова
 procedure SetColorEdge;     // закраска ребер
 var i,j,t: integer;
 begin
   while not Stack_IsEmpty(Stack) do begin
     Stack_Pop(Stack,t);     // взять из стека № ребра
     for i:=0 to N-1 do
     with Node[i] do begin
       LL:=Length(Edge);
       for j:=0 to LL-1 do
       if ((i=Edges[t].n1) and (Edge[j].NumNode=Edges[t].n2)) or
          ((i=Edges[t].n2) and (Edge[j].NumNode=Edges[t].n1)) then
         SetEdgeBlack(i,j);  // закрасить ребро
     end;
   end;
 end;

Автор: Underdark 28.6.2005, 10:13
А как насчет того, что автомобиль занимает две клетки? И ещё, в самом деле:
Цитата
проблема доказать что получен максимум...


Интересная задачка! Именно такие задачки всегда побуждают к действию (по крайней мере меня) smile

Автор: rsm 28.6.2005, 11:46
Если кто-нибудь ухитрится это расчитать, не сочтите пожалуйста за труд кинуть алгоритмом в приват. Я студент-автомобилист (специальность 150200 "Автомобили и автохозяйство"), на 5-ом курсе в димпломном проекте буду считать нечто подобное (оптимальное проектирование автопредприятия - АТП, автостоянки, заправки, автосервиса и пр.) и пример расчета был бы очень полезен.

Кстати теорию графов мы в курсе вышки вообще не изучали, но оптимально проектировать будем. Значит, задачу можно решить каким-то более простым способом.

Автор: SeregaPopenko 13.3.2006, 21:58
Решение задачи не такое уж простоё (сам сижу парюсьsmile(( ). Взята она из олимпиады 95 года, правда не знаю какой. Нашёл ссылку где выложено решение, кстати основывается на ГРАФАХ.
http://www.g6prog.narod.ru/books.html
качайте книгу Окулов "Информатика в задачах" в главе 4 условие а в главе 5 решение, код задачи о95_3. Кто разберётся прокаментируйте или напишите на мыло maugly_man_good@rambler.ru
Зарание спасибо!

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)