Optimal Satisficing Tree Searches
Abstract
We provide an algorithm that finds optimal search strategies for and trees and or trees. Our model includes three outcomes when a node is explored: (1) finding a solution, (2) not finding a solution and realizing that there are no solutions beneath the current node (pruning), and (3) not finding a solution but not pruning the nodes below. The expected cost of examining a node and the probabilities of the three outcomes are given. Based on this input, the algorithm generates an order that minimizes the expected search cost.
Cite
Text
Geiger and Barnett. "Optimal Satisficing Tree Searches." AAAI Conference on Artificial Intelligence, 1991.Markdown
[Geiger and Barnett. "Optimal Satisficing Tree Searches." AAAI Conference on Artificial Intelligence, 1991.](https://mlanthology.org/aaai/1991/geiger1991aaai-optimal/)BibTeX
@inproceedings{geiger1991aaai-optimal,
title = {{Optimal Satisficing Tree Searches}},
author = {Geiger, Dan and Barnett, Jeffrey A.},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {1991},
pages = {441-445},
url = {https://mlanthology.org/aaai/1991/geiger1991aaai-optimal/}
}