Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>This sounds like Dijkstra's algorithm. The hardest part would lay in properly setting up the graph (keeping track of which node gets which children), but if you can devote some CPU cycles to that, you'd be fine afterwards.</p> <p>Why don't you want a breadth-first search?</p> <p>Here.. I was bored :-) This is in Ruby but may get you started. Mind you, it is not tested.</p> <pre><code>class Node attr_accessor :parents, :children, :value def initialize args={} @parents = args[:parents] || [] @children = args[:children] || [] @value = args[:value] end def add_parents *args args.flatten.each do |node| @parents &lt;&lt; node node.add_children self unless node.children.include? self end end def add_children *args args.flatten.each do |node| @children &lt;&lt; node node.add_parents self unless node.parents.include? self end end end class Graph attr_accessor :graph, :root def initialize args={} @graph = args[:graph] @root = Node.new prepare_graph @root = @graph[0][0] end private def prepare_graph # We will iterate through the graph, and only check the values above and to the # left of the current cell. @graph.each_with_index do |row, i| row.each_with_index do |cell, j| cell = Node.new :value =&gt; cell #in-place modification! # Check above unless i.zero? above = @graph[i-1][j] if above.value == cell.value # Here it is safe to do this: the new node has no children, no parents. cell = above else cell.add_parents above above.add_children cell # Redundant given the code for both of those # methods, but implementations may differ. end end # Check to the left! unless j.zero? left = @graph[i][j-1] if left.value == cell.value # Well, potentially it's the same as the one above the current cell, # so we can't just set one equal to the other: have to merge them. left.add_parents cell.parents left.add_children cell.children cell = left else cell.add_parents left left.add_children cell end end end end end end #j = 0, 1, 2, 3, 4 graph = [ [3, 4, 4, 4, 2], # i = 0 [8, 3, 1, 0, 8], # i = 1 [9, 0, 1, 2, 4], # i = 2 [9, 8, 0, 3, 3], # i = 3 [9, 9, 7, 2, 5]] # i = 4 maze = Graph.new :graph =&gt; graph # Now, going from maze.root on, we have a weighted graph, should it matter. # If it doesn't matter, you can just count the number of steps. # Dijkstra's algorithm is really simple to find in the wild. </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POFewest number of turns heuristic
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USTrevoke
    1. USTrevoke
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COI don't want a breadth first search because it will never finish when you ramp this up to a square with large enough sides. The algorithm will run on an example square blown up to have edge lengths of 15 per side. The average number smallest turns runs about 22 turns, and the branching factor of the actual problem is about 7 at each level.
      singulars
      1. PO
      1. USNick Larsen
    2. COAnd do you specifically need that shortest path before you can do anything else? Because if that's your only problem, a weighted bidirectional graph with all equal weights and finding the shortest path, you don't have a whole lot of options. If your search tree is too big, you may well need to prune your search tree first. Here : http://rubylearning.com/blog/2009/12/27/rpcfn-mazes-5/ That last one is an implementation of finding the shortest path, you've got plenty of codes to look at ;)
      singulars
      1. PO
      1. USTrevoke
    3. CO@NiskLarsen: a 15*15 square can have a maximum of 225 nodes. BFS is O(V+E), the branching-factor stuff does not some into play in your graph because not all edges lead to new nodes.
      singulars
      1. PO
      1. USMAK
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload