search

jinnaiyuu / Hash-Distributed-Astar

Hash Distributed A*
https://sites.google.com/site/yuujinnaishomepage/home/parallel-search
MIT License
3 stars 1 forks source link

TODO: 2015/01/26 #65

Closed jinnaiyuu closed 9 years ago

jinnaiyuu commented 9 years ago
  1. More instances for HDA* vs. AHDA*

Need to show HDA* > AHDA*. Just run for all instances in korf_instances & grid_pathfinding.

  1. HDA* vs. AHDA* in node quality
  2. Zobrist Hash vs. Simple Hash in node quality
  3. More instances for multiheap HDA*
jinnaiyuu commented 9 years ago
  1. Running 2&3. Implemented tracker for node quality
  2. Going to
  3. Optimize multiheap HDA*
jinnaiyuu commented 9 years ago
  1. More instances for HDA* vs. AHDA*

Running.

  1. HDA* vs. AHDA* in node quality

Got the expected result. Hash-based distribution is better.

  1. Zobrist Hash vs. Simple Hash in node quality

Got the expected result. Obviously Zobrist hash is better.

  1. More instances for multiheap HDA*

First I should come up with some optimizations. At least it is working thou.

jinnaiyuu commented 9 years ago
  1. More instances for HDA* vs. AHDA Clearly HDA* (zobrist) > AHDA
  2. HDA* vs. AHDA* in node quality Clearly HDA* > AHDA*
  3. Zobrist hash vs. Simple hash Running. Pretty sure that Zobrist > Simple
  4. Multiheap HDA* Thinking.
jinnaiyuu commented 9 years ago
  1. Zobrist hash vs. Simple hash Clearly Zobrist > Simple
  2. Multiheap HDA* Thinking.
jinnaiyuu commented 9 years ago

5 . Why is there a search overhead in AHDA*? Printed the discrepancy of work distribution on threads. In short, there is a imbalance in work distribution.

6 . Why is there a search overhead in Simple Hash HDA*? Printed the discrepancy of work distribution on threads. In short, there is a imbalance in work distribution.

jinnaiyuu commented 9 years ago

4 . Multiheap HDA* Ok, lets first just drop a job. Running it for 100 instances.

7 . HDA* vs. AHDA* in Grid pathfinding I'm not entirely sure which algorithm is faster...