ВУЗ:
Составители:
Рубрика:
70
При этом можно выделить четыре основных оператора:
1. Перемещение пустой фишки вниз;
2. Перемещение пустой фишки вверх;
3. Перемещение пустой фишки влево;
4. Перемещение пустой фишки вправо.
Оценочная функция f(n) формируется как стоимость оптимального
пути к цели из начального состояния
через n вершин дерева поиска. Значение
оценочной функции для вершины n равно: f(n)=g(n)+h(n), где g(n) –
стоимость оптимального пути от начальной вершины до n-ой, а h(n) –
стоимость оптимального пути от n-ой вершины до целевой. Понятно, что h(n)
это эвристическая гипотеза, основанная на имеющейся информации о данной
конкретной задаче.
При этом
g(n) принимается равной глубине пройденного пути на
дереве поиска от начальной вершины до n-ой, а h(n) – расстояние Хемминга
от n-ой вершины до целевой (в данном случае оно равно числу фишек,
стоящих не на своих местах). Существует модификация алгоритма А*, в
которой представляет сумму манхэттеновских расстояний (считается как
сумма расстояний
в горизонтальном и вертикальном направлениях) от
1 3
8 2 4
7 6 5
1 2 3
8 4
7 6 5
1 3
8 2 4
7 6 5
1 3
8 2 4
7 6 5
1 3 4
8 2
7 6 5
1 3
8 2 4
7 6 5
1 2 3
8 4
7 6 5
1 3 4
8 2 5
7 6
1 3 4
8 2
7 6 5
Страницы
- « первая
- ‹ предыдущая
- …
- 68
- 69
- 70
- 71
- 72
- …
- следующая ›
- последняя »
