algorithm - maximise the special elements in the matrix -

-

below problem statement:

there matrix of size m*n , all numbers 1 m*n occupy place in it. now, element called special if(recursive definition)

-it top left corner element(at position (0,0))  -an element @ (x,y) special if neighbour element (m,n) such (m,n)      special , element @ (x,y) greater element at(m,n) , of (m,n)'s neighbours.

a neighbour cell cell shares edge it. therefore, internal cell has 4 neighbours, edge cell has 3 neighbours , corner cell has 2 neighbours.

the problem states few(maybe 0) cells in matrix have been filled. rest filled in such way numbers 1 m*n used , maximise number of special elements. also, if multiple answers possible, lexicographically smallest matrix considered answer.

a matrix lexicographically smaller other if string of row-major view lexicographically smaller other.

test case 1: //2 x 3 matrix 2 ? ?  ? ? 3   solution 1: 2 1 4  5 6 3   test case 2: //6 x 6 matrix ? ? ? ? ? ?  ? ? ? ? ? ?  ? ? ? ? ? ?  ? ? ? ? ? ?  ? ? ? ? ? ?  ? ? ? ? ? ?   solution 2:  1  2  3 13 14 15   4  6  8 10 11 16   5  7  9 12 19 17  28 26 24 22 20 18  29 27 25 23 21 36  30 31 32 33 34 35

my logic: special elements in matrix contiguous. so, have find out longest such path formed joining special elements contiguous. also, before placing element @ neighbouring cell (x,y) of special element(m,n), first fill out neighbours(except (x,y)) of special element(m,n) , choose value greater of them fill (x,y).

i don't know how proceed forward , how include lexicographically smallest condition. please help.

thanks in advance.

the best solution find algorithm solve problem, , prove correct. lacking that, there more options.

backtracking

this combinatorial problem, can solve backtracking. key points need implement backtracking algorithm solve problem are:

  1. find heuristic next step
  2. find stopping heuristic, branch , bound

i solve this:

  • find possible places next special element can placed. there won't many such places, pointed out already.
  • select possible combinations of values can used add next special value, regardless of next steps in backtracking. keep track of numbers still placed , "usual" , special values on every step (either using recursion or creating tailored data model). rest of matrix can left empty (or 0), filled further in backtracking. sort possibilities provide lexicographically smaller solutions first. try out viable possibilities.
  • if no special values left place, fill empty spots in matrix in lexicographic order, requirement.

early stopping can done when you're placing k th special value i, never able better current best solution. of course must stop branch when no more special values can added. creating initial solution proposed start, , allow more branch cutting cold start.

or maybe little guesswork...

maybe backtracking slow, if optimized, because tries find possible solutions. alternative use heuristic algorithm, genetic algorithms, tabu search, variable neighborhood search, simulated annealing, ...

such algorithms may find viable solution quickly, on downside, solution may not optimal one.


Comments

Post a Comment

Popular posts from this blog

java - Run a .jar on Heroku -

-
i trying run .jar file on heroku, , can't find instructions anywhere on how this. have read wants me compile uploading heroku. possible, , if is, how this? if helps, trying run minecraft craftbukkit server, , don't have pom.xml file yet. you didn't provide details i'll try give , people reaches question way it. first of all, create heroku account , create heroku application (assumed have done that). second, need generate application jar , upload heroku. so, open terminal , install heroku cli (assuming unix terminal): $ sudo npm install -g heroku-cli you need have npm , nodejs installed, can check link: https://www.digitalocean.com/community/tutorials/how-to-install-node-js-on-ubuntu-16-04 once done that, can use npm update node version acceptable heroku-cli: $ sudo npm install -g n $ sudo n 7.10.0 and run: $ sudo npm install -g heroku-cli in order deploy jars, need install deploy plugin: $ sudo heroku plugins:install heroku-cli-deploy ...
Read more

java - Jtable duplicate Rows -

-
Image
when add new rows in jtable duplicate rows many times this method update jtable public final void tableaucomande(){ ((defaulttablemodel)tabcommande.getmodel()).getdatavector().clear(); session s=hibernateutil.getsessionfactory().opensession(); criteria cr1= s.createcriteria(commande.class); list <commande> lcs=cr1.list() ; criteria cr2= s.createcriteria(lignecommande.class); list <lignecommande> lck=cr2.list() ; if(lcs.size()!=0 && lck.size()!=0) { (commande lc:lcs) { for(lignecommande lig:lck){ ((defaulttablemodel)tabcommande.getmodel()).addrow(new object[]{ lc.getid_cmd(),lc.getnumcmd(),lc.getdate_cmd(),lc.getclient().getnomprenom(), lig.getproduit().getlib_prd(),lig.getquantite(),lig.getproduit().getid_prd() }); } } // tabcommande.setrowselectioninterval(tabcommande.getrowcount()-1,tabcommande.getrowcount()-1); } } this code add add data rows displaye...
Read more

validation - How to pass paramaters like unix into windows batch file -

-
i need pass various parameters .cmd file unix format file.cmd -configuration=value -source=value -flag but, try this: startlocal @echo off cls setlocal set cmdline=%* set configuration= set source= set badargs= set validation= goto main :splitargs echo splitargs(%*) if "%*" neq "" ( /f "tokens=1,2,* delims== " %%i in ("%*") call :assignkeyvalue %%i %%j & call :splitargs %%k ) goto :eof :assignkeyvalue echo assignkeyvalue(%1, %2) if /i %1==-configuration ( set configuration=%2 ) else if /i %1==-source ( set source=%2 ) else ( rem append unrecognised [key,value] badargs echo unknown key %1 set badargs=%badargs%[%1, %2] ) goto :eof :validate echo validating set validation=fail if defined configuration ( echo -configuration ok if defined source ( echo -source ok if not defined badargs ( set validation=success ) ) ) goto :eof :main cl...
Read more