A spanning heuristic for the unordered and ordered matching identification problem

Douglas M. Kline, Charlene G. Riggle and Abraham Mehrez

Omega, 2005, vol. 33, issue 6, 483-490

Abstract: The matching identification problem (MIP) is a combinatoric search problem related to the fields of learning from examples, boolean functions, and knowledge acquisition. The MIP involves identifying a single "goal" item from a large set of items. Because there is commonly a cost associated with evaluating each guess, the goal item should be identified in as few guesses as possible. As in most search problems, the items have a similar structure, which allows an evaluation of each guessed item. In other words, each guessed item elicits partial information about the goal item, i.e. how similar the guess is to the goal. With this information the goal is more quickly identified. The unordered MIP has been studied by Mehrez and Steinberg (ORSA J. Comput. 7 (1995) 211) in which they proposed two different types of algorithms. The purpose of the present paper is to suggest an improved Spanning Heuristic algorithm. Its improvement increases as the problem size increases. Further results and comparisons are derived for the unordered and ordered cases. This research shows that when the search space is very large, it is better to inquire from items that are known not to be the goal (they have been ruled out by previous guesses), for the purpose of acquiring more information about the goal. As the search space is narrowed, it is better to guess items that have not been ruled out.

Keywords: Heuristics; Combinatoric; search; Boolean; functions; Knowledge; acquisition (search for similar items in EconPapers)
Date: 2005
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0305-0483(04)00106-9
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:jomega:v:33:y:2005:i:6:p:483-490

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

Access Statistics for this article

Omega is currently edited by B. Lev

More articles in Omega from Elsevier
Bibliographic data for series maintained by Catherine Liu (repec@elsevier.com).