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

Задача 2 от брой 11/2005 - ПОДАРЪК - Анализ


Втора задача от нашия Конкурс е модификация на известната игра Puzzle-15, като състезателите трябваше да решават вариант с размер на дъската 5x5.

За игри като тази с голяма популярност, съществуват много и различни подходи за подреждането на дъската. За начало ще опишем два от тях, които винаги подреждат числата по желания начин.

При първия подход се подреждат последователно първи, втори и трети ред. За всеки ред се подреждат трите най-леви числа отляво надясно. Оставащите две числа се нареждат като четвъртото от реда се поставя в края му, а петото се поставя под него. След това празното поле се поставя на четвърта позиция на реда и последователно се преместват последното число и това под него. Така се получава желаното нареждане. Тази последователност се изпълнява за редове едно, две и три. Остават да се наредят редове четири и пет. За тях подреждането се прави по колони. Започва се от най-лявата. Всяка колона се състои от две числа. Нека те са A и B, като A трябва да стои над B. B се поставя там където трябва да стои A, а вдясно от него се поставя A. Празното квадратче се поставя под B и след това се преместват последователно B и A като това ги поставя на местата им. Това се прави за трите най-леви колони. На края остават четири квадратчета. Едно от тях е празното поле. Другите три са числа, които все още не са подредени. За да бъдат подредени е нужно да се завъртят по начин, който не е трудно да се установи.

Вторият подход е и един от подходите реализиран от победителката в кръга – Ивелина Захариева. При него първо се подрежда първият ред както бе описано по-горе. След това по аналогичен начин се подрежда първата колона. Най-горната клетка в нея е вече подредена, но оставащите четири не са. Остават 16 неподредени полета. Те образуват квадрат с размери 4x4. За него се изпълняват стъпките, които бяха описани по-горе. След това последователно се достига до квадрати с размери 3x3 и 2x2. Подреждането на квадрат с размер 2x2 е тривиално.

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

За подобен вид игри може да се използва подхода A* (A звезда). При него се използва функция, чрез която се оценява дадена ситуация. Нека това е f(n) за конкретна ситуация n. f(n) се дефинира като сумата на други две функции g(n) и h(n). g(n) е цената, за да се достигне от началната ситуация до текущата. h(n) е някаква евристична оценка на цената, за да се достигне от текущата ситуация до крайната. В дадената задача една подходяща оценка е сумата от манхатановите разстояния за всяко число от текущата му позиция до мястото, където трябва да се намира. Нека се разглеждат две клетки с координати (x1,y1) и (x2,y2). Манхатановото разстояние между тях е |x1-x2| + |y1-y2|. Сега вече като се има предвид тази оценяваща функция може да се приложи следният подход:

1.      За началната ситуация s, g(s) = 0, а h(s) е равно на евристичната оценка, за която стана дума по-рано. За всички останали ситуации f(n) е безкрайност, тъй като все още не се знае стойността на g(n) за тях. Образуват се две множества от ситуации – M1 и М2. M1 съдържа тези, които вече са били разгледани от алгоритъма, M2 съдържа тези, които не са. В началото всички ситуации са в множеството M2.

2.      Намира се ситуацията от М2, която има най-малка стойност на f(n). Нека тя е обозначена с P. Тя се поставя в M1 и се изважда от M2. За ситуациите, които могат да се достигнат от P с един ход се подобрява стойността на g(n) и съответно на f(n), ако се получава по-добра стойност идвайки от P. Ако P е крайната ситуация се прекъсва изпълнението на алгоритъма. В противен случай се изпълнява стъпка 2 отново.

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

Решението на Радослав Герганов използва подхода Weighted A*. При него f(n) = g(n) + W * h(n), като W ≥ 1. Така се дава по-голяма тежест на евристичната оценка. Следствието от това е, че броят ситуации, които се разглеждат, за да се намери решение намалява като се използва W > 1. Радослав е използвал решение, което се изпълнява с различни стойности за константата W като се започва от по-големи и се върви към по-малки. Повече за подхода използван от него можете да прочетете на сайта на конкурса.

Решението на победителката Ивелина Захариева прави обхождане в дълбочина докато търси такава последователност от ходове, която нарежда дъската. На всяка стъпка от алгоритъма се разглеждат определен брой позиции. За всяка една се генерират тези позиции, които се получават от нея с един ход. От тях се получава следващото множество от позиции, които на свой ред се разглеждат. Разбира се по този начин много скоро броят на разглежданите позиции ще нарасне значително. Ето защо в решението на победителката на всяка стъпка се избират тези 5000, които имат най-добри стойности за f(n). Разбира се може да се експериментира с тази стойност, за да се получи решение, което ще работи достатъчно бързо и заедно с това да получава максимално добри резултати.

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


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

Supported by Musala Soft Ltd.

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