{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T05:23:48Z","timestamp":1648617828341},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Artif. Intell. Tools"],"published-print":{"date-parts":[[1997,6]]},"abstract":"<jats:p> In this paper, we develop TCGD, a problem-independent, time-constrained, approximate guided depth-first search (GDFS) algorithm. The algorithm is designed to achieve the best ascertained approximation degree under a fixed time constraint. We consider only searches with finite search space and admissible heuristic functions. We study NP-hard combinatorial optimization problems with polynomial-time computable feasible solutions. For the problems studied, we observe that the execution time increases exponentially as approximation degree decreases, although anomalies may happen. The algorithms we study are evaluated by simulations using the symmetric traveling-salesperson problem. <\/jats:p>","DOI":"10.1142\/s0218213097000141","type":"journal-article","created":{"date-parts":[[2003,10,22]],"date-time":"2003-10-22T05:26:17Z","timestamp":1066800377000},"page":"255-271","source":"Crossref","is-referenced-by-count":1,"title":["TCGD: A Time-Constrained Approximate Guided Depth-First Search Algorithm"],"prefix":"10.1142","volume":"06","author":[{"given":"Benjamin W.","family":"Wah","sequence":"first","affiliation":[{"name":"Department of Electrical and Computer Engineering and the Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL 61801, U.S.A."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lon-Chan","family":"Chu","sequence":"additional","affiliation":[{"name":"Microsoft Corporation, Redmond, WA 98052, U.S.A."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"container-title":["International Journal on Artificial Intelligence Tools"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218213097000141","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T13:45:46Z","timestamp":1565185546000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218213097000141"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,6]]},"references-count":0,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[1997,6]]}},"alternative-id":["10.1142\/S0218213097000141"],"URL":"https:\/\/doi.org\/10.1142\/s0218213097000141","relation":{},"ISSN":["0218-2130","1793-6349"],"issn-type":[{"value":"0218-2130","type":"print"},{"value":"1793-6349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,6]]}}}