Name
Abstract | ||
|---|---|---|
Heuristic search techniques can often benefit from record keeping and saving of intermediate results, thereby improving performance through exploitation of time / space tradeoffs. Iterative hill climbing (ITHC) is one of these heuristics. This paper demonstrates that record keeping in the ITHC domain can significantly speed up the ITHC. The record keeping method is similar to the mechanism of a cache. The new approach is implemented and tested in the traveling salesperson search space. The research compares a traditional random restart (RR) procedure to a new greedy enumeration (GE) method. GE produces Hamiltonian-cycles that are about 10% shorter than the RR. Moreover, the cached RR achieves a speedup of 3x with a relatively small number of cities and only 20% with a medium number of cities (~17). The cached GE shows a highly significant speedup of 4x over traditional methods even with a relatively large number of cities (80). |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-02568-6_23 | IEA/AIE |
Keywords | Field | DocType |
salesperson search space,tsp search space,new greedy enumeration,medium number,large number,cached rr,heuristic search technique,new approach,small number,cached ge,ithc domain,search space,hamiltonian cycle,heuristic search,hill climbing | Small number,Hill climbing,Heuristic,Cache,Computer science,Enumeration,Algorithm,Heuristics,Speedup | Conference |
Volume | ISSN | Citations |
5579 | 0302-9743 | 5 |
PageRank | References | Authors |
0.51 | 8 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| David Karhi | 1 | 5 | 0.51 |
| Dan E. Tamir | 2 | 79 | 13.26 |