I was just reading about it on a book and wikipedia but still dont understand it 100%.
I would really appreciate it if someone could explain it with an example or two.
Thanks
Say I'm looking at a map, searching for a pizza place near my block in the city. A few different strategies I could use:
Breadth first search (BFS): Look at concentric circles of blocks around my block, farther and farther outward until I find a pizza place. This will give me one of the pizza places which is closest to my block as the crow flies. Depth first search (DFS): Follow a road until I hit a dead end, then backtrack. Eventually all possible branches will be searched, so if there's a pizza place out there somewhere then I'll find it, but it probably won't be very close to my block. Uniform cost search (UCS): Say traffic is bad on some streets, and I'm really familiar with the city. For any given location I can say how long it will take me to get there from my block. So, looking at the map, first I search all blocks that will take me 1 minute or less to get to. If I still haven't found a pizza place, I search all blocks that will take me between 1 and 2 minutes to get to. I repeat this process until I've found a pizza place. This will give me one of the pizza places which is the closest drive from my block. Just as BFS looks like concentric circles, UFS will looks like a contour map. Typically you will implement UCS using a priority queue to search nodes in order of least cost.
I assume you were looking at this Wikipedia page. What it means is that the time required for a given operation (adding two numbers, comparing two numbers, retrieving data from memory, etc.) is independent of the size of the variables involved. In other words, an 8-bit comparison takes the same amount of time as a 32-bit comparison. Making this assumption allows you to simplify an efficiency analysis and compare algorithms without getting bogged down in implementation details.
链接地址:
http://www.djcxy.com/p/39728.html
上一篇:
在证明Big时找到C和N是一种简单的方法
下一篇:
成本搜索算法
