Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

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

Автор: 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. Кто разберётся прокаментируйте или напишите на мыло [email protected]
Зарание спасибо!