show/hide this revision's text 4 added 48 characters in body

The question is close to the Sokoban game (thanks to Dima Pasechnik !), but a little different in details.

Consider a directed graph (multi-graph). Consider some set of marked chips (chip1, chipe2,..., chipM). Put chips on some set of vertices 'Init1','Init2','Init3'... And consider some other set of vertices 'Final1','Final2',..., 'FinalM'.

Question Propose an "efficient" algorithm which will determine is it possible to "MOVE" chips from positions "InitNN" to positions 'FinalNN'.

Where we are allowed to "MOVE" chip from a vertex to an outgoing edge and from incoming edge to corresponding vertex. With the CONSTRAINT that two chips are NOT allowed to be at the same place. One move - moves only ONE chip. ChipK should go to position FinalK - same "K".

Question There can be many approaches to solve the problem, I am interested in analysis their complexity. Any ideas are welcome. For example if graph is "random" in certain sense what can be the algorithm the least average complexity ?

Where complexity is counted in number of operations (write a C-code (I actually wrote a Matlab code), compile to and calculate the number of cycles - this is well-defined complexity measure, different compilers and CPU will give approximately same result).

Example of algorithm It seems the simplest way to solve a problem is the following. Essentially it can be reduced to determining where two vertices are connected in some bigger graph, which in turn can be solved by "breadth-first search" ("wave algorithm" in Russian) (I mean let us enumerate all possible chip configurations - it will give vertices of the "new graph". Let us connect two vertices (configurations) if there is a "MOVE" which goes form one to another.) By "breadth-first search" ("wave algorithm" in Russian) I mean the following - take an initial vertex and find all connected to it; next step find all vertices connected to vertices found on the previous step; and so on....

Question What about efficiency of this algorithm ? Can one propose better ?
show/hide this revision's text 3 added 329 characters in body; edited tags; edited title

Algorithm to solve Sokoban-like game on graphs - move markers chips from one set of vertices of a graph to another

The question is close to the Sokoban game (thanks to Dima Pasechnik !), but a little different in details.

Consider an oriented a directed graph (multi-graph). Assume Consider some set of vertices is marked chips (chip1, chipe2,..., chipM). Put chips on some set of vertices 'Init1','Init2','Init3'... and another And consider some other set of vertices is marked by 'Final1','Final2',...

I am interested in the Final1','Final2',..., 'FinalM'.

Question Propose an "efficient" algorithms algorithm which will determine is it possible to "MOVE" markers chips from positions "InitNN" to positions 'FinalNN'.

Where we are allowed to "MOVE" marker chip from a vertex to an outgoing edge and from incoming edge to corresponding vertex. With the CONSTRAINT that two markers chips are NOT allowed to be at the same place. One move - moves only ONE chip.

Question There can be many approaches to solve the problem, I am interested in analysis their complexity. Any ideas are welcome. For example if graph is "random" in certain sense what can be the algorithm the least average complexity ?

Where complexity is counted in number of operations (write a C-code (I actually wrote a Matlab code), compile to and calculate the number of cycles - this is well-defined complexity measure, different compilers and CPU will give approximately same result).

Example of algorithm It seems the simplest way to solve a problem is the following. Essentially it can be reduced to determining where two vertices are connected in some bigger graph, which in turn can be solved by "wave algorithm". breadth-first search" ("wave algorithm" in Russian) (I mean let us enumerate all possible marker chip configurations - it will give vertices of the "new graph". Let us connect two vertices (configurations) if there is a "MOVE" which goes form one to another. another.) By "wave algorithmbreadth-first search" (it is Russian name I am not sure "wave algorithm" in English translationRussian) I mean the following - take an initial vertex and find all connected to it; next step find all vertices connected to vertices found on the previous step; and so on....

Question What about efficiency of this algorithm ? Can one propose better ?
show/hide this revision's text 2 vertexes -> vertices

Algorithm to move markers from one set of vertexes vertices of a graph to another

Consider an oriented graph (multi-graph). Assume some set of vertexes vertices is marked 'Init1','Init2','Init3'... and another set of vertexes vertices is marked by 'Final1','Final2',...

I am interested in the "efficient" algorithms which will determine is it possible to "MOVE" markers "InitNN" to positions 'FinalNN'. Where we allowed to "MOVE" marker from a vertex to an outgoing edge and from incoming edge to corresponding vertex. With the CONSTRAINT that two markers are NOT allowed to be at the same place.

Question There can be many approaches to solve the problem, I am interested in analysis their complexity. Any ideas are welcome. For example if graph is "random" in certain sense what can be the algorithm the least average complexity ?

Where complexity is counted in number of operations (write a C-code, compile to and calculate the number of cycles - this is well-defined complexity measure, different compilers and CPU will give approximately same result).

Example of algorithm It seems the simplest way to solve a problem is the following. Essentially it can be reduced to determining where two vertexes vertices are connected in some bigger graph, which in turn can be solved by "wave algorithm". I mean let us enumerate all possible marker configurations - it will give vertexes vertices of the "new graph". Let us connect two vertexes(configurations) vertices (configurations) if there is a "MOVE" which goes form one to another. By "wave algorithm" (it is Russian name I am not sure in English translation) I mean the following - take an initial vertex and find all connected to it; next step find all vertexes vertices connected to vertexes vertices found on the previous step; and so on....

Question What about efficiency of this algorithm ? Can one propose better ?
show/hide this revision's text 1