Здравейте, налага ми се да реша следната задачка:
Имаме масив 24х4 клетки. В тези клетки попълваме произволни числа от 0 до 9. Същите тези числа запазваме и в един списък. Разбъркваме списъка.
Задачата е да елиминираме всички числа от масива като последователността е тази от списъка. Как става това.
Можем да изчистим число само ако:
- то е равно на поредното в списъка;
- в колонката под него всички клетки от масива вече са изчистени;
Тъй като може да се получи така, че да няма число, отговарящо на изискванията, можем да преместим число в празна клетка.

Крайната идея е да получа последователност от клетки от масива с най-малък брой премествания.
Ако може някой да помогне със идея или код, ще бъда много благодарен. Или поне дайте идея какво да чета?
Направил съм и малко програмче, което визуално показва задачката, за който се интересува...
Благодаря предварително...

Привет!

Кажи първо с каква цел решаваш тази задача? Нещо в работата или в университета?

Уточни коя размерност е за колони и коя за редове?

При първото премахване започваме от дъното на матрицата?

Когато се мести число в празна клетка, то тази празна клетка може да е която и да е или има изискване спрямо празната клетка (примерно всички клетки над нея да са запълнени)?

Остави информация за контакт, така че ако човек се интересува да може да се свърже с теб?

На какъв език е писана програмата и на какъв език трябва да е решението?

Поздрави,
Тодор

Здравей,

Става въпрос за работа, понеже съм добра душа и искам да помогна на колеги, които го правят на хартия, съответно не се получава оптимизирана работа + отнема ДОСТА време.

Съдържаниет е скрито
Влезте за да го видите

Съдържаниет е скрито
Влезте за да го видите

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

Освен това, бъговете в програмата са повече от един. Списъкът с числа в матрицата не е същия както списъкът с разбърканите числа.

Здравей,
като пуснеш програмата, числата си отговарят, при 'NEW' съм забравил да изчистя списъка вдясно, затова става така, че не си отговарят числата. Но това няма значение според мен, важна е идеята. Колкото до ситуацията без свободни места - ами представи си че имаш още един свободен ред примерно, няма значение, както казах - важна е идеята.

Ако може някой да даде идея (метод) как може да се реши това, ще бъда много благодарен. Като алгоритми досега не съм се сблъсквал с нещо по-сериозно от рекурсия за обикаляне на дърво или метод на вълната, а висшата математика не ми е от силните страни :)
Не го правя за пари, просто искам да помогна на хората, които работят с това.
Благодаря, и ако някой има идеи нега ги обсъдим тук?

Поздрави,
Кирил Хаджиев

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

Това с рекурсията ясно. Лошото е, че вариантите са милиони, в момента ми отнема около 10 мин и нагоре да ги извърви всички. А всъщност матрицата е по-голяма (средно 250-300 клетки), числата са 1 до 20 или 30 обикновено.

Аз се надявах да намеря някакъв математически модел или алгоритъм, нещо с матрици и детерминанти, "разкрояване на материали" или нещо от сорта.. Абе математика.. Май не пуснах задачката в правилния форум :)

Да беше написал от началото точните параметри на задачата. Гледай, комбинаторните задачи винаги са си с NP сложност. Държиш ли решението да е напълно оптимално или може да е близко до оптималното? Предполагам, че може с динамично оптимиране нещо да се направи, но това ми е твърде сложно и не бих могъл да ти предложа точен алгоритъм.

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

Също можеш да си намислиш нещо като експертна система, което би било бързо и би давало относително добри резултати. Обаче да направиш експертна система ще ти трябва доста повече от познания по висша математика. Ако използваш някой готов рулс енджин имаш малко по-добри шансове.

Инае, оптимизирането на този процес е много добра идея и определено си заслужава.

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

Благодаря за интереса и за съветите.