Musala Soft Logo Конкурс по програмиране на Musala Soft и PC Magazine Bulgaria PC Magazine Bulgaria Logo
  Състезателна система
Сезон 2010 - 2011
Сезон 2009 - 2010
Сезон 2008 - 2009
Сезон 2007 - 2008
Сезон 2006 - 2007
Сезон 2005 - 2006
Сезон 2004 - 2005
Сезон 2003 - 2004
Сезон 2002 - 2003
Сезон 2001 - 2002
Сезон 2000 - 2001
Правила
Задача 1
Задача 2
Задача 3
Задача 4
Задача 5
Задача 6
Класиране
Финален кръг
Коментар относно решениeтo на задача 2 (Жилищни блокове)

Задачата се решава с алгоритъм от типа Back-Track - търсене с връщане назад. Това е типична стратегия за изчерпване на възможните комбинаторни конфигурации на някакво множество - в случая сгради с различна височина, разположени в квадратен регион.

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

Ще изложим алгоритъма на журито. Описаните стъпки и похвати могат да се прилагат не само в решението на конкретната задача, но и генерално, в схемата на алгоритми от типа Back-Track.

В конкретната задача имаме доста допълнителни условия към разположението на сградите, така че да създадем някакъв критерий, с помощта на които можем да намалим изчерпваните конфигурации. От голямо значение са фактите, че всички сгради са с еднаква форма и че имат различна височина. Също така, на помощ идват и силуетите (входните данни), според които не може да поставим по-висока сграда от конкретната стойност на силуета в тази линия.

Да се върнем отново към условието на задачата - входните данни - силуетите, представляват критерий дали една конфигурация от сгради е решение на задачата - тоест ако конфигурацията има тези силуети, то тя е решение. Естествено, може да има много конфигурации, които са решения, но ние се интересуваме само от една от тях.

Първата стъпка от алгоритъма е, да определим колко и какви сгради ще участват в решението - минималният брой сгради е броят на различните височини в силуетите. Евентуално решение може да се получи и с повече сгради, но за нас представлява интерес възможно минималния брой сгради, защото броят на комбинаторните конфигурации е по-малък. Така, на база на силуетите, определяме участващите в евентуалното решение сгради със съответните им височини.

Втората стъпка представлява предварително изследване на възможните координати на една сграда. Например за сграда с височина 56 и широчина 5, нека имаме три последователни височини в един от двата силуета (южния), на координати 10,11,12. Можем да направим извод, че възможната X-координата на сградата с височина 56 е между 8, 9 и 10. Можем още повече да ограничим координатата, евентуално ако има по ниска съседна сграда отдясно (на координата 13 в силуета да имаме височина 40) - тогава е ясно че отпадат вариантите X-координатата на сградата да бъде 9 и 10, по простата причина, че тогава в силуета на коорд.13 трябва да има височина 56, а не 40. Правим този извод благодарение на факта, че има по-ниска сграда (ограниченито идва от същността на силуета). Аналогичен извод можем да направим ако по-ниската сграда е отляво.
Също така можем да направим и предварителен извод, че задачата няма решение - ако например сградите са с широчина 5 и имаме следния фрагмент от силует: "... 10 10 10 20 20 20 15 15 ..." - Сградата с височина 20 няма Х-координата, такава че да не нарани силуета на другите сгради (широчината и е 5, а се виждат само 3 от нея, и е оградена отляво и отдясно с по-ниски сгради).
Резултатът от тази стъпка трябва да представлява максимално орязани множества от координатите за всяка сграда пример:
      за сграда 34, X - от 13 до 15, Y - от 25 до 30.
      за сграда 41, X - от 10 до 11, Y - от 0 до 100. (не е намерено в случая ограничение по Y)
      и т.н.

Третата стъпка представлява оптимизиране на плана на изчерпващия алгоритъм. На базата на ограниченията от съпка 2, можем да определим броя на възможните места на които можем да поставим една сграда в изчерпването. Например сграда 34 можем да я поставим на
(15-13 +1)х(30-25 +1) = 3х6 = 18 възмочни положения, за сграда 41 - (11-10+1)х101 = 202 възможни положения. Вероятността за по-бързо намиране на решение в процеса на изчерпването е много по-голяма ако проиграваме възможните ситуации за сграда 34 преди сграда 41. Тоест изчерпването трябва да започне със сградите, които имат най-малко възможни положения за поставане. Най-високата сграда винаги има само едно възможно положение, защото със сигурност присъства и в двата силуета. Така със сигурност поставяме първо фиксираните сгради, а после продължаваме да проиграваме ситуациите за тези които са по-слабо фиксирани и т.н. Третата стъпка (планирането) увеличава с пъти-повече ефективноста на изчерпването и намирането на решение. Може да се направи и друг план, който не се базира на някакви сериозни резултати от изследвания - да се изчерпват сградите по големина, сортирани низходящо. Най-високата сграда (която е фиксирана) ще бъде сложена първа както при предищния план. В общия случай обаче този план е по-лош от първия, защото в конкретния пример ще постави сграда 41 преди 34, а както забелязваме това е по-лош вариант.

Четвърта стъпка - изчерпване. Може да се направи както итеративно, така и чрез рекурсивна изчерпваща функция, но това не е от голямо значение за бързината на алгоритъма. Изчерпването се състои от генериането на всички възможни конфигурации според ограниченията от стъпка 2, проверяването на всяка една от тях дали удоволетворява изискванията (силуетите) и евентуално отхвърляне на други групи конфигурации при построяването им ако се забележи, че не могат да изпълният изискванията.

 

Анализи на решения изпратени от участници

  • Петър Петров

  • За въпроси можете да ни пишете на адрес: konkurs@musala.com.

    Supported by Musala Soft Ltd.

    Copyright 2000-2010 by Musala Soft Ltd. All rights reserved.