Loading...
+ Нов въпрос
netherblood avatar netherblood 95 Точки

[Homework] Combinatorial Algorithms - Snakes*

Аз я докарах до тука:
http://pastebin.com/Sf4g7t3k

Разбрах, че може с алгоритъм който пропуска дубликати, или с ротация на матрица да се отрежат дубликати, но нямам идея как да го имплементирам като код.
Ако някой може да ми обясни задачата, ще съм му много благодарен.

 

Тагове:
0
Структури от данни и алгоритми 12/04/2016 13:32:42
a_rusenov avatar a_rusenov 1103 Точки
Best Answer

Супер си се сетил с матрицата да си следиш да не се захапе змията. :) Това, което остава е за всяка генерирана поредица да генерираш и нейните възможни варианти при ротации/флипове. Най-лесно това става като работиш със стрингове, а не да ротираш/флипваш цели матрици. Например, SRRD при хоризонтален флип става SRRU (просто обръщаш U с D и обратно). Ротация по часовниковата стрелка е на същия принцип, само че там посоките се променят така - R -> D, L -> U, D -> L, U -> R.

Всички възможни флипове/ротации на 1 поредица ги вкарваш в един HashSet<string>. Когато генерираш нова поредица и нейните флипове/ротации -> проверяваш дали вече няма такава в хешсета. И това работи, но дава само за 50/100, защото при достатъчно голямо n програмата заспива.

И тука идва моментът как да оптимизираме:

След достатъчно рисунки забелязваме, че за почти всяка 1 поредица генерираме още 8 чрез ротации/флипове. Почти всички от тях са дубликати по условие и е излишно да въртим през тях. Затова извикваме първоначално GenSnake от SR... нататък (змията SR е началото на рекурсията). Така си спестяваме генерирането на SU..., SL... и SD... змии, които и без това не ни трябват (задраскани са в картинката).

От тук нататък единствения друг вариант, който генерираме е хоризонтален флип на текущия (напр. SRRU -> SRRD). Защо? Защото само до него можем да достигнем, когато генерираме змии, започващи с SR...

До момента да обобщим: когато генерираме 1 редица, генерираме и флипнатия вариант. Ако в хешсета вече съществува 1 от двете -> редицата се дублира и нищо не правим. В противен случай, добавяме и вариантите на текущата редица в сета и я принтираме.
---------
Остана още едно нещо - възможно е да генерираме поредици като SRDD (дублира се с SRRU). Обаче от SRRU само с ротации/флипове не можем да стигнем до SRDD. Причината е, че взимаме предвид началото S и посоките, в които се движим. По условие обаче това са 2 еднакви поредици. 

  • Как от SRRU получаваме SRDD тогава? Обръщаме реда на на SRRU и получаваме SDLL (виж картинката). След този reverse имаме вариант, получен в следствие на ротации на SRDD. Затова ротираме получената фигура надясно (по часовниковата стрелка), докато тя не започва с SR... (Защо? Защото само тогава ни интересува. Контрапример: ако я добавим като SDLL тя е недостижима от текущото генериране на змии).

И в крайна сметка, освен оригиналния и флипнатия, запазваме и този reversed вариант. Това са трите варианта, които ни интересуват за всяка една змия, когато тя започва с SR... Всички останали са ненужни.

Като цяло доста трябва да се порисува, за да се схване идеята. Ако не е станало ясно, пишете да доразяснявам. И ако някой има по-добър/оптимален алгоритъм, нека споделя. :)

8
13/04/2016 02:49:11
netherblood avatar netherblood 95 Точки

Страхотно обяснено и с картинка какво повече да иска човек.

Благодаря много Наско!

2
netherblood avatar netherblood 95 Точки

Един бърз и може би глупав въпрос:
Защо SRDD не се смята за уникална комбинация?
Моето решение генерира 5 комбинации за n = 4 а примерите показват 4.

Ето го и то, все още неоптимизирано:
http://pastebin.com/YkziJtbz

1
a_rusenov avatar a_rusenov 1103 Точки

SRDD е SRRU ротирано 1 път наляво + reverse.

0
RFilipov avatar RFilipov 136 Точки

Тръгваш винаги надясно с DFS-a и така елиминираш повторенията. Дъното на рекурсията е на 4та стъпка вместо на пета.

1
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.