A method of finding constraints by conjecture

✍ Scribed by Hidehiro Shimizu; Ikuo Tahara

• Publisher: John Wiley and Sons
• Year: 1994
• Tongue: English
• Weight: 765 KB
• Volume: 25
• Category: Article
• ISSN: 0882-1666
• DOI: 10.1002/scj.4690250407

✦ Synopsis

Abstract

This paper proposes a method of finding constraints by conjecture and its application to combinatorial problems. By the term conjecture is meant the strategy that people use when solving problems by trial‐and‐error, guessing the causes of failure. The problem of finding the maximal (or minimal) subsets whose elements satisfy (or do not satisfy) the conditions through selecting subsets and testing whether their elements satisfy the conditions is a typical combinatorial problem. In this case, the search process is considered to be a process of finding new constraints, and the search space can be represented by lattice.

The conjecture that is based on experiences can be well formulated as the strategy for finding maximal (or minimal) constraints in such a lattice structure. The proposed method can be applied particularly to the problems such that the conditions are not given explicitly in advance.