/
test_a_star.js
115 lines (106 loc) · 3.85 KB
/
test_a_star.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
var assert = require('assert');
const { search } = require('../search/aStar');
/*
startPositions, {
getScore,
isGoal,
getNeighbors,
heuristic,
maxPathLength }
*/
describe('search tests', function () {
it('minimal search', function () {
function heuristic(position){
return Math.abs(10 - position)
}
function getNeighbors(position){
return [position + 8, position - 3]
}
let res = search([0],{getNeighbors,heuristic})
assert.equal(res.pop(),0)
assert.equal(res.pop(),8)
assert.equal(res.pop(),5)
assert.equal(res.pop(),13)
assert.equal(res.pop(),10)
});
it('longer search', function () {
function heuristic(position){
return Math.abs(131 - position)
}
function getNeighbors(position){
return [position + 8, position - 3, position + 30, , position + 97]
}
let res = search([0],{getNeighbors,heuristic, maxPathLength: 10})
assert.equal(res.pop(),0)
assert.equal(res.pop(),97)
assert.equal(res.pop(),105)
assert.equal(res.pop(),135)
assert.equal(res.pop(),132)
assert.equal(res.pop(),129)
assert.equal(res.pop(),126)
assert.equal(res.pop(),134)
assert.equal(res.pop(),131)
assert.equal(res.pop(),undefined)
});
it('longer search with isGoal and getScore', function () {
function heuristic(position){
return Math.abs(132 - position)
}
function getNeighbors(position){
return [position + 8, position - 5, position + 30, position + 97]
}
function isGoal(position){
if( position == 132){
console.log("full")
return true
}
else {
return false
}
}
let res = search([0],{getNeighbors, heuristic, isGoal, maxPathLength: 10})
assert.equal(res.pop(),0)
assert.equal(res.pop(),97)
assert.equal(res.pop(),127)
assert.equal(res.pop(),122)
assert.equal(res.pop(),117)
assert.equal(res.pop(),147)
assert.equal(res.pop(),142)
assert.equal(res.pop(),137)
assert.equal(res.pop(),132)
assert.equal(res.pop(),undefined)
});
it('longer search for closest complex', function () {
function heuristic(position){
return Math.abs(12 - position.value)
}
function getNeighbors(position){
return [{op: '+8', value: position.value + 8},{op:'-5', value: position.value - 5}]
}
let res = search([{value: 0}],{getNeighbors, heuristic, maxPathLength: 10})
console.log(res)
assert.deepEqual(res.pop(), {value: 0})
assert.deepEqual(res.pop(), {op: '+8', value: 8})
assert.deepEqual(res.pop(), {op: '+8', value: 16})
assert.deepEqual(res.pop(), { op: '-5', value: 11 })
assert.deepEqual(res.pop(), { op: '-5', value: 6 })
assert.deepEqual(res.pop(), { op: '+8', value: 14 })
assert.deepEqual(res.pop(), { op: '-5', value: 9 })
assert.deepEqual(res.pop(), { op: '+8', value: 17 })
assert.deepEqual(res.pop(), { op: '-5', value: 12 })
});
it('sort search for closest complex', function () {
function heuristic(position){
return Math.abs(12 - position.value)
}
function getNeighbors(position){
return [{op: '+8', value: position.value + 8},{op:'-5', value: position.value - 5}]
}
let res = search([{value: 0}],{getNeighbors, heuristic, maxPathLength: 6})
console.log(res)
assert.deepEqual(res.pop(), {value: 0})
assert.deepEqual(res.pop(), {op: '+8', value: 8})
assert.deepEqual(res.pop(), {op: '+8', value: 16})
assert.deepEqual(res.pop(), { op: '-5', value: 11 })
});
})