StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>A small issue: you said "What slows is keeping the queue of nodes to be visited ordered.". In this case you can use a "Priority Heap". This is a partial ordered queue that always return the min (or max) item in e queue, insertions, retrieves - removes are O(log n), so this can make a bit fast your initial A* algorithm. Here a send you a simple implementation, but is made in C#, you need to translate it to Java...</p> <pre><code>public class PriorityHeap<T> { private int count; private int defaultLength = 10; private PriorityHeapNode[] array; private bool isMin; /// <summary> /// /// </summary> /// <param name="isMin">true si quiere que la ColaHeap devuelva el elemento de menor Priority, falso si quiere que devuelva el de mayor</param> public PriorityHeap(bool isMin) { this.count = 0; this.isMin = isMin; this.array = new PriorityHeapNode[defaultLength]; } public PriorityHeap(bool isMin, int iniLength) { this.count = 0; this.isMin = isMin; this.defaultLength = iniLength; this.array = new PriorityHeapNode[defaultLength]; } public class PriorityHeapNode { T valor; int _priority; public PriorityHeapNode(T valor, int _priority) { this.valor = valor; this._priority = _priority; } public T Valor { get { return this.valor; } } public double Priority { get { return this._priority; } } } public int Count { get { return this.count; } } /// <summary> /// Devuelve true si la cola devuelve el valor de menor Priority, falso si el de mayor /// </summary> public bool IsMin { get { return isMin; } } /// <summary> /// Devuelve y quita el Valor Minimo si la cola lo permite,si no, retorna null /// </summary> /// <returns></returns> public PriorityHeapNode GetTopAndDelete() { PriorityHeapNode toRet; if (count > 0) { if (count == 1) { toRet = array[0]; array[0] = null; count--; return toRet; } else { toRet = array[0]; array[0] = array[count - 1]; array[count - 1] = null; HeapyfiToDown(0); count--; return toRet; } } else return null; } /// <summary> /// Devuelve el tope pero no lo borra /// </summary> /// <returns></returns> public PriorityHeapNode GetTop() { return array[0]; } public void Insert(PriorityHeapNode p) { if (array.Length == count) Add(p); else array[count] = p; count++; HeapyfiToUp(count - 1); } public void Clear() { count = 0; } #region Private Functions private int GetFather(int i) { return ((i + 1) / 2) - 1; } private int GetRightSon(int i) { return 2 * i + 2; } private int GetLeftSon(int i) { return 2 * i + 1; } private void Add(PriorityHeapNode p) { if (array.Length == count) { PriorityHeapNode[] t = new PriorityHeapNode[array.Length * 2]; for (int i = 0; i < array.Length; i++) { t[i] = array[i]; } t[count] = p; array = t; } } private void HeapyfiToUp(int i) { if (isMin) { int father = GetFather(i); if (father > -1 && array[father].Priority > array[i].Priority) { PriorityHeapNode t = array[father]; array[father] = array[i]; array[i] = t; HeapyfiToUp(father); } } else { int father = GetFather(i); if (father > -1 && array[father].Priority < array[i].Priority) { PriorityHeapNode t = array[father]; array[father] = array[i]; array[i] = t; HeapyfiToUp(father); } } } private void HeapyfiToDown(int i) { if (isMin) { #region HeapyFi To down Min int l = GetLeftSon(i); int r = GetRightSon(i); if (r < count) { PriorityHeapNode right = array[r]; PriorityHeapNode left = array[l]; int t; if (right != null && left != null) { t = left.Priority < right.Priority ? l : r; } else if (right != null) t = r; else if (left != null) t = l; else return; if (array[t].Priority < array[i].Priority) { PriorityHeapNode temp = array[t]; array[t] = array[i]; array[i] = temp; HeapyfiToDown(t); } } else if (l < count) { PriorityHeapNode left = array[l]; int t; if (left != null) t = l; else return; if (array[t].Priority < array[i].Priority) { PriorityHeapNode temp = array[t]; array[t] = array[i]; array[i] = temp; HeapyfiToDown(t); } } #endregion } else { #region HeapyFi To down NOT Min int l = GetLeftSon(i); int r = GetRightSon(i); if (r < count) { PriorityHeapNode right = array[r]; PriorityHeapNode left = array[l]; int t; if (right != null && left != null) { t = left.Priority > right.Priority ? l : r; } else if (right != null) t = r; else if (left != null) t = l; else return; if (array[t].Priority > array[i].Priority) { PriorityHeapNode temp = array[t]; array[t] = array[i]; array[i] = temp; HeapyfiToDown(t); } } else if (l < count) { PriorityHeapNode left = array[l]; int t; if (left != null) t = l; else return; if (array[t].Priority > array[i].Priority) { PriorityHeapNode temp = array[t]; array[t] = array[i]; array[i] = temp; HeapyfiToDown(t); } } #endregion } } #endregion } </code></pre> <p>Hope this helps...</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

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