Document (#8236)

Author

Dillenburg, J.F.
Nelson, P.C.

Title

Perimeter search

Source

Artificial intelligence. 65(1994) no.1, S.165-178

Year

1994

Abstract

Presents a technique for improving heuristic search efficiency. This admissible technique is referred to as perimeter search since it relies on a perimeter of nodes around the goal. The perimeter is generated by a breadth-first search from the goal to all nodes at a given depth d. The path back to the goal along with each perimeter node's state descriptor are stored in a table. The search then proceeds normally from the start node on the perimeter. If a match is found, the search can terminate with the path being formed with the path from the start to the perimeter node together with the previously stored path from the perimeter node to the goal. Both analytical and experimental results are presented to show that perimeter search is more efficient than IDA* and A* in terms of time complexity and number of nodes expanded for two problem domains

Similar documents (author)

1. Nelson, M.J.: Correlation of term usage and term indexing frequencies (1988) 5.02

   5.023691 = sum of:
     5.023691 = weight(author_txt:nelson in 650) [ClassicSimilarity], result of:
       5.023691 = fieldWeight in 650, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         8.037906 = idf(docFreq=38, maxDocs=44421)
         0.625 = fieldNorm(doc=650)
   

2. Nelson, M.G.: Catalogers as librarians (1986) 5.02

   5.023691 = sum of:
     5.023691 = weight(author_txt:nelson in 2879) [ClassicSimilarity], result of:
       5.023691 = fieldWeight in 2879, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         8.037906 = idf(docFreq=38, maxDocs=44421)
         0.625 = fieldNorm(doc=2879)
   

3. Nelson, T.H.: ¬A file structure for the complex, the changing, and the indeterminate (1965) 5.02

   5.023691 = sum of:
     5.023691 = weight(author_txt:nelson in 4467) [ClassicSimilarity], result of:
       5.023691 = fieldWeight in 4467, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         8.037906 = idf(docFreq=38, maxDocs=44421)
         0.625 = fieldNorm(doc=4467)
   

4. Nelson, M.J.: ¬The design of a hypertext interface for information retrieval (1991) 5.02

   5.023691 = sum of:
     5.023691 = weight(author_txt:nelson in 4804) [ClassicSimilarity], result of:
       5.023691 = fieldWeight in 4804, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         8.037906 = idf(docFreq=38, maxDocs=44421)
         0.625 = fieldNorm(doc=4804)
   

5. Nelson, S.J.: From meaning to term : semantic locality in the UMLS metathesaurus (1992) 5.02

   5.023691 = sum of:
     5.023691 = weight(author_txt:nelson in 5610) [ClassicSimilarity], result of:
       5.023691 = fieldWeight in 5610, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         8.037906 = idf(docFreq=38, maxDocs=44421)
         0.625 = fieldNorm(doc=5610)
   

Similar documents (content)

1. Rada, R.: Hypertext writing and document reuse : the role of a semantic net (1990.) 0.14

   0.13850771 = sum of:
     0.13850771 = product of:
       0.8656732 = sum of:
         0.014044346 = weight(abstract_txt:with in 5910) [ClassicSimilarity], result of:
           0.014044346 = score(doc=5910,freq=1.0), product of:
             0.060015213 = queryWeight, product of:
               1.6419091 = boost
               2.4961398 = idf(docFreq=9949, maxDocs=44421)
               0.014643448 = queryNorm
             0.23401311 = fieldWeight in 5910, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               2.4961398 = idf(docFreq=9949, maxDocs=44421)
               0.09375 = fieldNorm(doc=5910)
         0.026832018 = weight(abstract_txt:from in 5910) [ClassicSimilarity], result of:
           0.026832018 = score(doc=5910,freq=2.0), product of:
             0.07334197 = queryWeight, product of:
               1.8150756 = boost
               2.759399 = idf(docFreq=7646, maxDocs=44421)
               0.014643448 = queryNorm
             0.36584806 = fieldWeight in 5910, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               2.759399 = idf(docFreq=7646, maxDocs=44421)
               0.09375 = fieldNorm(doc=5910)
         0.5305683 = weight(abstract_txt:node in 5910) [ClassicSimilarity], result of:
           0.5305683 = score(doc=5910,freq=3.0), product of:
             0.42566493 = queryWeight, product of:
               3.7868927 = boost
               7.676116 = idf(docFreq=55, maxDocs=44421)
               0.014643448 = queryNorm
             1.2464459 = fieldWeight in 5910, product of:
               1.7320508 = tf(freq=3.0), with freq of:
                 3.0 = termFreq=3.0
               7.676116 = idf(docFreq=55, maxDocs=44421)
               0.09375 = fieldNorm(doc=5910)
         0.2942285 = weight(abstract_txt:path in 5910) [ClassicSimilarity], result of:
           0.2942285 = score(doc=5910,freq=1.0), product of:
             0.4560896 = queryWeight, product of:
               4.526302 = boost
               6.881186 = idf(docFreq=123, maxDocs=44421)
               0.014643448 = queryNorm
             0.6451112 = fieldWeight in 5910, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.881186 = idf(docFreq=123, maxDocs=44421)
               0.09375 = fieldNorm(doc=5910)
       0.16 = coord(4/25)
   

2. Vocht, L. De: Exploring semantic relationships in the Web of Data : Semantische relaties verkennen in data op het web (2017) 0.12

   0.12223489 = sum of:
     0.12223489 = product of:
       0.38198403 = sum of:
         0.017009206 = weight(abstract_txt:match in 232) [ClassicSimilarity], result of:
           0.017009206 = score(doc=232,freq=1.0), product of:
             0.097672395 = queryWeight, product of:
               1.0473078 = boost
               6.3687487 = idf(docFreq=206, maxDocs=44421)
               0.014643448 = queryNorm
             0.17414548 = fieldWeight in 232, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.3687487 = idf(docFreq=206, maxDocs=44421)
               0.02734375 = fieldNorm(doc=232)
         0.009159532 = weight(abstract_txt:with in 232) [ClassicSimilarity], result of:
           0.009159532 = score(doc=232,freq=5.0), product of:
             0.060015213 = queryWeight, product of:
               1.6419091 = boost
               2.4961398 = idf(docFreq=9949, maxDocs=44421)
               0.014643448 = queryNorm
             0.15262018 = fieldWeight in 232, product of:
               2.236068 = tf(freq=5.0), with freq of:
                 5.0 = termFreq=5.0
               2.4961398 = idf(docFreq=9949, maxDocs=44421)
               0.02734375 = fieldNorm(doc=232)
         0.012374002 = weight(abstract_txt:from in 232) [ClassicSimilarity], result of:
           0.012374002 = score(doc=232,freq=5.0), product of:
             0.07334197 = queryWeight, product of:
               1.8150756 = boost
               2.759399 = idf(docFreq=7646, maxDocs=44421)
               0.014643448 = queryNorm
             0.1687165 = fieldWeight in 232, product of:
               2.236068 = tf(freq=5.0), with freq of:
                 5.0 = termFreq=5.0
               2.759399 = idf(docFreq=7646, maxDocs=44421)
               0.02734375 = fieldNorm(doc=232)
         0.06521802 = weight(abstract_txt:technique in 232) [ClassicSimilarity], result of:
           0.06521802 = score(doc=232,freq=8.0), product of:
             0.15073273 = queryWeight, product of:
               1.8399551 = boost
               5.5944448 = idf(docFreq=448, maxDocs=44421)
               0.014643448 = queryNorm
             0.43267325 = fieldWeight in 232, product of:
               2.828427 = tf(freq=8.0), with freq of:
                 8.0 = termFreq=8.0
               5.5944448 = idf(docFreq=448, maxDocs=44421)
               0.02734375 = fieldNorm(doc=232)
         0.047891725 = weight(abstract_txt:stored in 232) [ClassicSimilarity], result of:
           0.047891725 = score(doc=232,freq=2.0), product of:
             0.19475538 = queryWeight, product of:
               2.0914533 = boost
               6.3591332 = idf(docFreq=208, maxDocs=44421)
               0.014643448 = queryNorm
             0.24590707 = fieldWeight in 232, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               6.3591332 = idf(docFreq=208, maxDocs=44421)
               0.02734375 = fieldNorm(doc=232)
         0.046449594 = weight(abstract_txt:goal in 232) [ClassicSimilarity], result of:
           0.046449594 = score(doc=232,freq=1.0), product of:
             0.3029171 = queryWeight, product of:
               3.6887593 = boost
               5.6078978 = idf(docFreq=442, maxDocs=44421)
               0.014643448 = queryNorm
             0.15334095 = fieldWeight in 232, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.6078978 = idf(docFreq=442, maxDocs=44421)
               0.02734375 = fieldNorm(doc=232)
         0.098065294 = weight(abstract_txt:search in 232) [ClassicSimilarity], result of:
           0.098065294 = score(doc=232,freq=19.0), product of:
             0.22513387 = queryWeight, product of:
               4.206858 = boost
               3.654598 = idf(docFreq=3123, maxDocs=44421)
               0.014643448 = queryNorm
             0.4355866 = fieldWeight in 232, product of:
               4.358899 = tf(freq=19.0), with freq of:
                 19.0 = termFreq=19.0
               3.654598 = idf(docFreq=3123, maxDocs=44421)
               0.02734375 = fieldNorm(doc=232)
         0.085816644 = weight(abstract_txt:path in 232) [ClassicSimilarity], result of:
           0.085816644 = score(doc=232,freq=1.0), product of:
             0.4560896 = queryWeight, product of:
               4.526302 = boost
               6.881186 = idf(docFreq=123, maxDocs=44421)
               0.014643448 = queryNorm
             0.18815742 = fieldWeight in 232, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.881186 = idf(docFreq=123, maxDocs=44421)
               0.02734375 = fieldNorm(doc=232)
       0.32 = coord(8/25)
   

3. Bressan, M.; Peserico, E.: Choose the damping, choose the ranking? (2010) 0.12

   0.11907046 = sum of:
     0.11907046 = product of:
       0.7441904 = sum of:
         0.036589514 = weight(abstract_txt:analytical in 3563) [ClassicSimilarity], result of:
           0.036589514 = score(doc=3563,freq=1.0), product of:
             0.102533765 = queryWeight, product of:
               1.0730548 = boost
               6.5253177 = idf(docFreq=176, maxDocs=44421)
               0.014643448 = queryNorm
             0.3568533 = fieldWeight in 3563, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.5253177 = idf(docFreq=176, maxDocs=44421)
               0.0546875 = fieldNorm(doc=3563)
         0.0081925355 = weight(abstract_txt:with in 3563) [ClassicSimilarity], result of:
           0.0081925355 = score(doc=3563,freq=1.0), product of:
             0.060015213 = queryWeight, product of:
               1.6419091 = boost
               2.4961398 = idf(docFreq=9949, maxDocs=44421)
               0.014643448 = queryNorm
             0.13650765 = fieldWeight in 3563, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               2.4961398 = idf(docFreq=9949, maxDocs=44421)
               0.0546875 = fieldNorm(doc=3563)
         0.19399995 = weight(abstract_txt:nodes in 3563) [ClassicSimilarity], result of:
           0.19399995 = score(doc=3563,freq=2.0), product of:
             0.3568842 = queryWeight, product of:
               3.4674702 = boost
               7.028639 = idf(docFreq=106, maxDocs=44421)
               0.014643448 = queryNorm
             0.5435935 = fieldWeight in 3563, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               7.028639 = idf(docFreq=106, maxDocs=44421)
               0.0546875 = fieldNorm(doc=3563)
         0.5054084 = weight(abstract_txt:node in 3563) [ClassicSimilarity], result of:
           0.5054084 = score(doc=3563,freq=8.0), product of:
             0.42566493 = queryWeight, product of:
               3.7868927 = boost
               7.676116 = idf(docFreq=55, maxDocs=44421)
               0.014643448 = queryNorm
             1.1873386 = fieldWeight in 3563, product of:
               2.828427 = tf(freq=8.0), with freq of:
                 8.0 = termFreq=8.0
               7.676116 = idf(docFreq=55, maxDocs=44421)
               0.0546875 = fieldNorm(doc=3563)
       0.16 = coord(4/25)
   

4. Falquet, G.; Guyot, J.; Nerima, L.: Languages and tools to specify hypertext views on databases (1999) 0.11

   0.106506124 = sum of:
     0.106506124 = product of:
       0.6656633 = sum of:
         0.011703622 = weight(abstract_txt:with in 4968) [ClassicSimilarity], result of:
           0.011703622 = score(doc=4968,freq=1.0), product of:
             0.060015213 = queryWeight, product of:
               1.6419091 = boost
               2.4961398 = idf(docFreq=9949, maxDocs=44421)
               0.014643448 = queryNorm
             0.19501092 = fieldWeight in 4968, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               2.4961398 = idf(docFreq=9949, maxDocs=44421)
               0.078125 = fieldNorm(doc=4968)
         0.01581092 = weight(abstract_txt:from in 4968) [ClassicSimilarity], result of:
           0.01581092 = score(doc=4968,freq=1.0), product of:
             0.07334197 = queryWeight, product of:
               1.8150756 = boost
               2.759399 = idf(docFreq=7646, maxDocs=44421)
               0.014643448 = queryNorm
             0.21557805 = fieldWeight in 4968, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               2.759399 = idf(docFreq=7646, maxDocs=44421)
               0.078125 = fieldNorm(doc=4968)
         0.27714276 = weight(abstract_txt:nodes in 4968) [ClassicSimilarity], result of:
           0.27714276 = score(doc=4968,freq=2.0), product of:
             0.3568842 = queryWeight, product of:
               3.4674702 = boost
               7.028639 = idf(docFreq=106, maxDocs=44421)
               0.014643448 = queryNorm
             0.77656215 = fieldWeight in 4968, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               7.028639 = idf(docFreq=106, maxDocs=44421)
               0.078125 = fieldNorm(doc=4968)
         0.361006 = weight(abstract_txt:node in 4968) [ClassicSimilarity], result of:
           0.361006 = score(doc=4968,freq=2.0), product of:
             0.42566493 = queryWeight, product of:
               3.7868927 = boost
               7.676116 = idf(docFreq=55, maxDocs=44421)
               0.014643448 = queryNorm
             0.848099 = fieldWeight in 4968, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               7.676116 = idf(docFreq=55, maxDocs=44421)
               0.078125 = fieldNorm(doc=4968)
       0.16 = coord(4/25)
   

5. Scholer, F.; Williams, H.E.; Turpin, A.: Query association surrogates for Web search (2004) 0.10

   0.10046785 = sum of:
     0.10046785 = product of:
       0.41861606 = sum of:
         0.01655142 = weight(abstract_txt:with in 3236) [ClassicSimilarity], result of:
           0.01655142 = score(doc=3236,freq=2.0), product of:
             0.060015213 = queryWeight, product of:
               1.6419091 = boost
               2.4961398 = idf(docFreq=9949, maxDocs=44421)
               0.014643448 = queryNorm
             0.2757871 = fieldWeight in 3236, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               2.4961398 = idf(docFreq=9949, maxDocs=44421)
               0.078125 = fieldNorm(doc=3236)
         0.01581092 = weight(abstract_txt:from in 3236) [ClassicSimilarity], result of:
           0.01581092 = score(doc=3236,freq=1.0), product of:
             0.07334197 = queryWeight, product of:
               1.8150756 = boost
               2.759399 = idf(docFreq=7646, maxDocs=44421)
               0.014643448 = queryNorm
             0.21557805 = fieldWeight in 3236, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               2.759399 = idf(docFreq=7646, maxDocs=44421)
               0.078125 = fieldNorm(doc=3236)
         0.06588015 = weight(abstract_txt:technique in 3236) [ClassicSimilarity], result of:
           0.06588015 = score(doc=3236,freq=1.0), product of:
             0.15073273 = queryWeight, product of:
               1.8399551 = boost
               5.5944448 = idf(docFreq=448, maxDocs=44421)
               0.014643448 = queryNorm
             0.437066 = fieldWeight in 3236, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.5944448 = idf(docFreq=448, maxDocs=44421)
               0.078125 = fieldNorm(doc=3236)
         0.096755885 = weight(abstract_txt:stored in 3236) [ClassicSimilarity], result of:
           0.096755885 = score(doc=3236,freq=1.0), product of:
             0.19475538 = queryWeight, product of:
               2.0914533 = boost
               6.3591332 = idf(docFreq=208, maxDocs=44421)
               0.014643448 = queryNorm
             0.49680728 = fieldWeight in 3236, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.3591332 = idf(docFreq=208, maxDocs=44421)
               0.078125 = fieldNorm(doc=3236)
         0.13271314 = weight(abstract_txt:goal in 3236) [ClassicSimilarity], result of:
           0.13271314 = score(doc=3236,freq=1.0), product of:
             0.3029171 = queryWeight, product of:
               3.6887593 = boost
               5.6078978 = idf(docFreq=442, maxDocs=44421)
               0.014643448 = queryNorm
             0.43811703 = fieldWeight in 3236, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.6078978 = idf(docFreq=442, maxDocs=44421)
               0.078125 = fieldNorm(doc=3236)
         0.09090452 = weight(abstract_txt:search in 3236) [ClassicSimilarity], result of:
           0.09090452 = score(doc=3236,freq=2.0), product of:
             0.22513387 = queryWeight, product of:
               4.206858 = boost
               3.654598 = idf(docFreq=3123, maxDocs=44421)
               0.014643448 = queryNorm
             0.40377986 = fieldWeight in 3236, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               3.654598 = idf(docFreq=3123, maxDocs=44421)
               0.078125 = fieldNorm(doc=3236)
       0.24 = coord(6/25)