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

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

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

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

Перемещу-ка я эту тему в другой раздельчик...

Fedor Переместить та ты переместил, а подсказать не подсказал Лесно, что моя задачка в таком матёром разделе

Цитата(klimskiy @ 19.6.2005, 22:27)

Fedor Переместить та ты переместил, а подсказать не подсказал

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

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

Решается просто:
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;

Это сообщение отредактировал(а) dvs15 - 20.6.2005, 01:10

А как насчет того, что автомобиль занимает две клетки? И ещё, в самом деле:

Цитата

проблема доказать что получен максимум...

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

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

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

Это сообщение отредактировал(а) rsm - 28.6.2005, 11:47

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