home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / cognitiv / 688 < prev    next >
Encoding:
Internet Message Format  |  1992-11-19  |  1.5 KB
  1. Path: sparky!uunet!ogicse!uwm.edu!linac!mp.cs.niu.edu!uxa.ecn.bgu.edu!news.ils.nwu.edu!pautler
  2. From: pautler@ils.nwu.edu (David Pautler)
  3. Newsgroups: sci.cognitive
  4. Subject: Re: hierarchies
  5. Message-ID: <1992Nov19.160031.17428@ils.nwu.edu>
  6. Date: 19 Nov 92 16:00:31 GMT
  7. Article-I.D.: ils.1992Nov19.160031.17428
  8. Sender: usenet@ils.nwu.edu (Mr. usenet)
  9. Organization: The Institute for the Learning Sciences
  10. Lines: 24
  11. Nntp-Posting-Host: aristotle.ils.nwu.edu
  12.  
  13. In article <1992Nov17.150028.9905@coe.montana.edu>, wombat@cs.montana.edu (Izurieta) writes:
  14. > 
  15. >     I have been reading a few papers in segmentation of environments
  16. > into regions.  Apparently, this is done by humans to create cognitive
  17. > maps of some areas.  These regions in turn, form part of a hierarchy.
  18. > 
  19. >     Here is my question,  What are the advantages of using a hierarchy
  20. > to subdivide an environment?  Are there any computational advantages?
  21.  
  22. (I posted in order to prevent tens of messages being sent to Izurieta).
  23.  
  24. There's certainly a search-time advantage relative to searching a list.
  25. If the tree has N leaves and the list N elements, a branching factor of
  26. 2 would get you from the root to a leaf in log-base-2-of N steps, while
  27. it may take you a full N steps for an unsorted list.
  28.  
  29. But depending on whether you interpret the nonterminal nodes in the tree
  30. as representing something essential or not, binary trees require more
  31. space (2N - 1) than lists (N).
  32.  
  33. You might want to look at Aho, Hopcroft, and Ullman, _Data Structures
  34. and Algorithms_.
  35.  
  36.     -dp-
  37.