logo
Redian新闻
>未名空间
>PDA - 掌中宝
>
iGO HERE map 2014.Q1为什么比2013.Q4小很多
avatar
iGO HERE map 2014.Q1为什么比2013.Q4小很多# PDA - 掌中宝
s*u
1 楼
看了不少这方面的讨论，写的很玄乎。以前学的时候就没太明白。
我感觉是，动态规划就是f(n) = F( n,f(n-1),f(n-2),f(n-3)....f(1) )，就是当前解
取决于之前所有解或者部分解。
而贪心算法则是f(n) = G( n,f(n-1))，也就是当前解只取决于前一步的解。
是这么个意思么。。
avatar
l*s
2 楼
请问版上各位大侠，我现在是拿到EAD卡，在公司工作，学校里想请我去做part time
faculty，院里都同意，就是学校律师说不行，说这样对拿绿卡有风险，这是为什么？
我所了解的是EAD可以兼职工作了，只要保持我的公司的全职身份，对吗？谢谢解惑！
avatar
k*e
3 楼
我们小公司的长途电话用量比较大，之前是用ATT的$15固定月费的长途计划，上个月某
天突然接到PDL公司agent的电话，claim他们是att的分公司，att把部分长途服务转包
给他们，如果现在愿意swith长途服务到他们公司下面，可以获得更低的每月费用。结
果没有警惕的情况下就同意了，结果这个月的电话账单过来才发现他们居然charge了我
们$103!!! 每个长途电话都单独收费。等你发现了再terminate他们的服务，或者要求
投诉拒付，他们的丑恶面目才展现出来，百般无赖和推诿。发此贴希望引起各位的警惕
和注意，而且他们目标也不只是business line用户或者长途服务的switch,他们会各种
忽悠你全部或者部分转你们的各种服务～
另外2个link给大家看看他们的面目：
http://como.typepad.com/community_mobilization/2005/04/prefered
http://www.la.bbb.org/business-reviews/Long-Distance-Telephone-
这个link下面可以看到complaint detail里面他们response的无赖嘴脸
avatar
m*h
4 楼
牦牛的气管，还蛮耐啃的
avatar
M*0
5 楼
我下的2013.Q1 map 2.31GB
2014.Q1 map 1.51GB
avatar
k*6
6 楼
是的，greedy一旦made choice,就不再多考虑了，以后都base on这个choice. sub
problem 的其他借解都扔掉了。 通过local optimal try to 找到global optimal，可
以是近似的最优解。当然有的书说一定要保证greedy能找到最优解。但实际上有时候可
以根据具体问题采用greedy simplify problem.
DP是不放弃所有的choice, 保持所有sub problem 的solutions都考虑，最后因该一定
会找到最优解。所以DB经常有sub problem大量的重复计算，搞个大表memorize一下去
避免重复计算。

【在 s********u 的大作中提到】
: 看了不少这方面的讨论，写的很玄乎。以前学的时候就没太明白。
: 我感觉是，动态规划就是f(n) = F( n,f(n-1),f(n-2),f(n-3)....f(1) )，就是当前解
: 取决于之前所有解或者部分解。
: 而贪心算法则是f(n) = G( n,f(n-1))，也就是当前解只取决于前一步的解。
: 是这么个意思么。。
avatar
p*i
7 楼
没有问题

【在 l***s 的大作中提到】
: 请问版上各位大侠，我现在是拿到EAD卡，在公司工作，学校里想请我去做part time
: faculty，院里都同意，就是学校律师说不行，说这样对拿绿卡有风险，这是为什么？
: 我所了解的是EAD可以兼职工作了，只要保持我的公司的全职身份，对吗？谢谢解惑！
avatar
k*e
8 楼
第一张可真像PUPPY
avatar
M*0
9 楼
刚刚发现 2013.Q4里面有271 files
2014.Q1只有165 files
难道我下载的不全？
avatar
f*s
10 楼
不是的。
贪心不是只取决于上一步(或上几步)的解。
我对greedy的理解是， 当前的解就是最优解，不用管下面一个进来的input是什么。。
。 也就是说，根据现有的input就能知道怎么solve optimal solution， 将来进来的
input不会影响现在算出来的解。
相对的DP, 跟greedy不是互斥的。dp只是说， 一个problem可以break成几个类似的sub
-problem,并且sub-problem的解可以用来解开原本的problem
avatar
s*u
11 楼
开Uber也可以？
avatar
m*h
12 楼
小白狗的优势，哈哈

【在 k*******e 的大作中提到】
: 第一张可真像PUPPY
avatar
i*y
13 楼
能不能提供连接？谢谢

【在 M********0 的大作中提到】
: 我下的2013.Q1 map 2.31GB
: 2014.Q1 map 1.51GB
avatar
s*u
14 楼
嗯，我好像理解你的意思了。
就像这一段（维基百科）：
In other words, a greedy algorithm never reconsiders its choices. This is
the main difference from dynamic programming, which is exhaustive and is
guaranteed to find the solution. After every stage, dynamic programming
makes decisions based on all the decisions made in the previous stage, and
may reconsider the previous stage's algorithmic path to solution
一个简单的例子是，找硬币的问题，比如硬币面值是1,3,4.要组成6，贪心法就会得到(
4,1,1)，而dp则能解出（3,3）。
但我奇怪的是，如果按照这样的说法，我们平时绝大多数的dp题，难道实际上都是贪心
算法了。（或者把贪心看成dp的一种特殊情况？）
比如：leetcode的unique path，wordladder，或者subsequence问题（例如longest
increasing subsequence）。甚至最简单的fibnacci数列，因为f(n)都不会影响f(n-1)或
者更之前的决策，这样的话，都属于贪心算法？

sub

【在 f**********s 的大作中提到】
: 不是的。
: 贪心不是只取决于上一步(或上几步)的解。
: 我对greedy的理解是， 当前的解就是最优解，不用管下面一个进来的input是什么。。
: 。 也就是说，根据现有的input就能知道怎么solve optimal solution， 将来进来的
: input不会影响现在算出来的解。
: 相对的DP, 跟greedy不是互斥的。dp只是说， 一个problem可以break成几个类似的sub
: -problem,并且sub-problem的解可以用来解开原本的problem
avatar
k*e
15 楼
黑脸的要气哭了。。

【在 m***h 的大作中提到】
: 小白狗的优势，哈哈
avatar
k*6
17 楼
没有说greedy跟DP是互斥的，有说法greedy是DP的一个special case。其他没明白你说
的跟我说的有什么区别。。。
我觉得以下这个对于both greedy and DP都是true的，
〉我对greedy的理解是， 当前的解就是最优解，不用管下面一个进来的input是什么。。
sub
avatar
m*h
18 楼
将来会变成白脸的一天

【在 k*******e 的大作中提到】
: 黑脸的要气哭了。。
avatar
c*x
19 楼
下载完并安装到GPS里，貌似没啥问题。明天路测看看如何。
avatar
s*u
20 楼
嗯，的确是有这么说法。就是贪心法可以看做是一个特例。
是我主贴写的是错的。
但如果是这样的话，我们讨论的绝大多数（几乎所有）的dp题实际都是贪心算法，就是
f(n)不会影响f(n-1),f（n-2)。。。f(1)的解。

【在 k*********6 的大作中提到】
: 没有说greedy跟DP是互斥的，有说法greedy是DP的一个special case。其他没明白你说
: 的跟我说的有什么区别。。。
: 我觉得以下这个对于both greedy and DP都是true的，
: 〉我对greedy的理解是， 当前的解就是最优解，不用管下面一个进来的input是什么。。
: sub
avatar
k*e
21 楼
再说我都要哭了 ┬＿┬

【在 m***h 的大作中提到】
: 将来会变成白脸的一天
avatar
f*s
23 楼
Greedy是一条线做下来，比如f(n)依赖f(n-1)
DP可以看成一个parallel universe，每一步有多种走法，你把每一步都走一遍，然后
看看每一种情况对下一步有什么影响。。
所以当每一步只有一个可能的走法时，dp就接近greedy了
纯个人理解，完全不严谨不学术呵呵

嗯，的确是有这么说法。就是贪心法可以看做是一个特例。是我主贴写的是错的。但如
果是这样的话，我们讨论的绝大多数（几乎所有）的dp题实际都是贪心算法，就是f(n)
不会影响f(n-1........

【在 s********u 的大作中提到】
: 嗯，的确是有这么说法。就是贪心法可以看做是一个特例。
: 是我主贴写的是错的。
: 但如果是这样的话，我们讨论的绝大多数（几乎所有）的dp题实际都是贪心算法，就是
: f(n)不会影响f(n-1),f（n-2)。。。f(1)的解。
avatar
m*h
24 楼
别哭啊，想想他幸福的狗生

【在 k*******e 的大作中提到】
: 再说我都要哭了 ┬＿┬
avatar
i*y
25 楼
能不能把种子文件发给我？谢谢。说是什么megnet的协议，连接打不开

【在 c**x 的大作中提到】
: 估计更新压缩了，需换新的Global_cfg后才能使用新地图。下面是狗狗的连接：
: 地图
: iGO8 R3 HERE (Navteq) 2014.Q1 North America
: BT 下载
: MAP: http://www.yyv.co/AHoGi
: POI: http://www.yyv.co/AHoHb
: 文件 Global_cfg_423294
: 位置:\Primo\content\global_cfg\
: 下载:
: https://onedrive.live.com/?cid=f3786629ffb3ee33&id=F3786629FFB3EE33!217&
avatar
s*u
26 楼
今天想了一想，觉得可以分为两类问题：
1.节点空间两端收敛，中间可以发散，但是两端必须收敛。因此前驱节点一定能决定当
前节点（唯一解）。最典型的，就是leetcode的unique path，或者fibnacci数列。这
类问题，总是可以用dp bottom-up的做。
2.节点空间一端发散，也就是说前驱节点不能决定当前节点（可能有很多方向，很多解
）。这类问题一般可以用backtracking做。最典型的，自然是tree的dfs
avatar
l*8
27 楼
一白遮百丑.

【在 m***h 的大作中提到】
: 小白狗的优势，哈哈
avatar
c*x
28 楼
哦用utorrent下载地
地图：
magnet:?xt=urn:btih:27C88E702E66B47DE05B4A78DCAA83C05FBAC00A&dn=iGO8%20R3%
20HERE%20%28Navteq%29%202014.Q1%20North%20America%20-%20map&tr=udp%3a%2f%
2ftracker.publicbt.com%3a80%2fannounce&tr=udp%3a%2f%2ftracker.openbittorrent
.com%3a80%2fannounce&tr=udp%3a%2f%2fopen.demonii.com%3a1337%2fannounce&tr=
udp%3a%2f%2ftracker.istole.it%3a80%2fannounce&tr=udp%3a%2f%2f9.rarbg.com%
3a2710%2fannounce&tr=udp%3a%2f%2f10.rarbg.com%3a80%2fannounce&tr=udp%3a%2f%
2f11.rarbg.com%2fannounce&tr=udp%3a%2f%2f11.rarbg.com%3a80%2fannounce&tr=udp
%3a%2f%2f12.rarbg.me%3a80%2fannounce&tr=udp%3a%2f%2fipv4.tracker.harry.lu%
3a80%2fannounce&tr=udp%3a%2f%2fcoppersurfer.tk%3a6969%2fannounce&tr=udp%3a%
2f%2ftpb.tracker.prq.to%3a80%2fannounce
POI
magnet:?xt=urn:btih:7D99C263F006243C45B98319B0667635BA15B46D&dn=iGO8%20R3%
20HERE%20%28Navteq%29%202014.Q1%20North%20America%20-%20poi&tr=udp%3a%2f%
2ftracker.publicbt.com%3a80%2fannounce&tr=udp%3a%2f%2ftracker.openbittorrent
.com%3a80%2fannounce&tr=udp%3a%2f%2fopen.demonii.com%3a1337%2fannounce&tr=
udp%3a%2f%2ftracker.istole.it%3a80%2fannounce&tr=udp%3a%2f%2f9.rarbg.com%
3a2710%2fannounce&tr=udp%3a%2f%2f10.rarbg.com%3a80%2fannounce&tr=udp%3a%2f%
2f11.rarbg.com%2fannounce&tr=udp%3a%2f%2f11.rarbg.com%3a80%2fannounce&tr=udp
%3a%2f%2f12.rarbg.me%3a80%2fannounce&tr=udp%3a%2f%2fipv4.tracker.harry.lu%
3a80%2fannounce&tr=udp%3a%2f%2fcoppersurfer.tk%3a6969%2fannounce&tr=udp%3a%
2f%2ftpb.tracker.prq.to%3a80%2fannounce
avatar
s*u
29 楼
今天想了一想，觉得可以分为两类问题：
1.节点空间两端收敛，中间可以发散，但是两端必须收敛。因此前驱节点一定能决定当
前节点（唯一解）。最典型的，就是leetcode的unique path，或者fibnacci数列。这
类问题，总是可以用dp bottom-up的做。
2.节点空间一端发散，也就是说前驱节点不能决定当前节点（可能有很多方向，很多解
）。这类问题一般可以用backtracking做。最典型的，自然是tree的dfs
avatar
K*a
30 楼
哈哈哈表情太逗了。
avatar
N*k
31 楼
2014Q2没有fsp fda文件
avatar
b*e
32 楼
Here’s a pretty extreme way of looking at it:
Every problem has a brute-force solution, that is, to search the space of
all the possible solutions. Usually the space of all the possible solutions
is a tree like structure, where starting from the root, there’s a bunch of
possibilities branching out, and on and on.
DP is still searching the full space, traversing all the nodes in the
possible solution space. The only thing it does better than naive brute-
force is that, DP would reuse the search results of the nodes that had been
traversed before.
Greedy algorithm, on the other hand, is not traversing the full search space
. It plays as an oracle and cleverly picks up a path from the root leading
to the solution node. But usually one needs to prove that this path is
truly leading to the solution, and that’s the hard part.
If you look at the real tricky graph theory algorithms, most of them are
greedy.

【在 s********u 的大作中提到】
: 看了不少这方面的讨论，写的很玄乎。以前学的时候就没太明白。
: 我感觉是，动态规划就是f(n) = F( n,f(n-1),f(n-2),f(n-3)....f(1) )，就是当前解
: 取决于之前所有解或者部分解。
: 而贪心算法则是f(n) = G( n,f(n-1))，也就是当前解只取决于前一步的解。
: 是这么个意思么。。
avatar
s*1
33 楼
哪里买的？
avatar
s*n
34 楼
我感觉不是，我觉得是F和G的差别，dp里面F肯定是对的，可以证明的，贪心里面的G只
是local optimal，无法证明global optimal

【在 s********u 的大作中提到】
: 看了不少这方面的讨论，写的很玄乎。以前学的时候就没太明白。
: 我感觉是，动态规划就是f(n) = F( n,f(n-1),f(n-2),f(n-3)....f(1) )，就是当前解
: 取决于之前所有解或者部分解。
: 而贪心算法则是f(n) = G( n,f(n-1))，也就是当前解只取决于前一步的解。
: 是这么个意思么。。
avatar
m*h
35 楼
附近一个宠物店发现的

【在 s********1 的大作中提到】
: 哪里买的？
avatar
c*e
36 楼
well said.

solutions
of
been
space

【在 b***e 的大作中提到】
: Here’s a pretty extreme way of looking at it:
: Every problem has a brute-force solution, that is, to search the space of
: all the possible solutions. Usually the space of all the possible solutions
: is a tree like structure, where starting from the root, there’s a bunch of
: possibilities branching out, and on and on.
: DP is still searching the full space, traversing all the nodes in the
: possible solution space. The only thing it does better than naive brute-
: force is that, DP would reuse the search results of the nodes that had been
: traversed before.
: Greedy algorithm, on the other hand, is not traversing the full search space
avatar
d*n
37 楼
说得很好
DP很多时候要解决所有的子问题，跟Brute Force相比优点是解决得很快，因为消除了
重复计算
Greedy用一个或多个简单rules，只解决基本一部分子问题，认为局部最优最导致全局
最优，这对不少问题是适用的。DP跟greedy相比是有些问题greedy没法找到全局最优方案
另外一方面我发现有些同学在面试中喜欢上DP，喜欢用DP作为终极利器。可是很多时候
面试官都没搞清楚什么DP，而且确实有比DP好的方案(不一定表现在快，而是表现在可
读性可维护性)
个人觉得把DFS研究得很深比DP更有用
如果DFS研究透了再研究一下DP

solutions
of
been
space

【在 b***e 的大作中提到】
: Here’s a pretty extreme way of looking at it:
: Every problem has a brute-force solution, that is, to search the space of
: all the possible solutions. Usually the space of all the possible solutions
: is a tree like structure, where starting from the root, there’s a bunch of
: possibilities branching out, and on and on.
: DP is still searching the full space, traversing all the nodes in the
: possible solution space. The only thing it does better than naive brute-
: force is that, DP would reuse the search results of the nodes that had been
: traversed before.
: Greedy algorithm, on the other hand, is not traversing the full search space
相关阅读
Nokia 928 $29.99了有类似软件么Thinkpad Helix上市了，值得入手么？分享一下HTC One手动关闭LTE的方法还是melissa给力 flickr免费空间扩到1T了联想服务很好，YOGA真心不错哪里买Galaxy S4裸机比较便宜？刚刚收到HTC One trade in $100 Debit card.求android下语音翻译app求问哪里能买到无锁版的S4 i9502HTC的又一致命伤another nail on Apple's coffinat&t 两年合约到期 iphone 4 升级到 iphone 5nokia eos 7月第二周， 和中国好声音看来xbox one看电视是通过hdmi in了？xbox reveal live最快的平板来了craiglist 随便买个iphone 4可以带回国入网吗?11 inch tablet版上有人用 Motorola Atrix HD 吗
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。