Skip to main content
added 48 characters in body
Source Link
Alexander Chervov
  • 24.9k
  • 20
  • 102
  • 209

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 ?

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.

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 ?

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 ?

added 329 characters in body; edited tags; edited title
Source Link
Alexander Chervov
  • 24.9k
  • 20
  • 102
  • 209

Algorithm to solve Sokoban-like game on graphs - move markerschips 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 orienteda directed graph (multi-graph). AssumeConsider some set of vertices is marked chips (chip1, chipe2,..., chipM). Put chips on some set of vertices 'Init1','Init2','Init3'... and anotherAnd consider some other set of vertices is marked by vertices 'Final1','Final2',..., 'FinalM'.

I am interested in theQuestion Propose an "efficient" algorithmsalgorithm which will determine is it possible to "MOVE" markerschips from positions "InitNN" to positions 'FinalNN'. Where

Where we are allowed to "MOVE" markerchip from a vertex to an outgoing edge and from incoming edge to corresponding vertex. With With the CONSTRAINT that two markerschips 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"breadth-first search" ("wave algorithm". I in Russian) (I mean let us enumerate all possible markerchip 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 "wave algorithm" "breadth-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 ?

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

Consider an oriented graph (multi-graph). Assume some set of vertices is marked 'Init1','Init2','Init3'... and another set of 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 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 vertices of the "new graph". Let us connect two 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 vertices connected to vertices found on the previous step; and so on....

Question What about efficiency of this algorithm ? Can one propose better ?

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

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.

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 ?

vertexes -> vertices
Source Link
Gerry Myerson
  • 39.9k
  • 10
  • 186
  • 247

Algorithm to move markers from one set of vertexesvertices of a graph to another

Consider an oriented graph (multi-graph). Assume some set of vertexesvertices is marked 'Init1','Init2','Init3'... and another set of vertexesvertices 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 vertexesvertices 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 vertexesvertices of the "new graph". Let us connect two vertexesvertices (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 vertexesvertices connected to vertexesvertices found on the previous step; and so on....

Question What about efficiency of this algorithm ? Can one propose better ?

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

Consider an oriented graph (multi-graph). Assume some set of vertexes is marked 'Init1','Init2','Init3'... and another set of vertexes 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 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 of the "new graph". Let us connect two vertexes(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 connected to vertexes found on the previous step; and so on....

Question What about efficiency of this algorithm ? Can one propose better ?

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

Consider an oriented graph (multi-graph). Assume some set of vertices is marked 'Init1','Init2','Init3'... and another set of 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 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 vertices of the "new graph". Let us connect two 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 vertices connected to vertices found on the previous step; and so on....

Question What about efficiency of this algorithm ? Can one propose better ?

Source Link
Alexander Chervov
  • 24.9k
  • 20
  • 102
  • 209
Loading