算法分析与设计习题

1.0-1背包问题可用动态规划、回溯法、分支限界法解决。比较用不同算法处理0-1背包问题各有什么特点和利弊。 2. 简述BP算法的学习过程 3. 如何证明一个问题是NPC问题。已知TSP（旅行售货员问题）是NPC问题，证明Hamilton 问题也是NPC的。 4.根据下面的代价矩阵，求出最小代价路径及状态空间树的情况 ∞ 20 30 10 11 15 ∞ 16 4 2 3 5 ∞ 2 4 19 6 18 ∞ 3 16 4 7 16 ∞ 5. 设I是一个n 位十进制整数，如果将I划分为k段，则可得到k个整数。这k个整数的乘积称为I的一个k乘积。设计算法，对于给定的I和k，求出I的最大k 乘积。 6. 设计一个拉斯维加斯算法，对于给定的奇素数p和整数x,计算x的模p平方根，算法的计算时间应为log2p的多项式.（模平方根问题：设p是一个奇素数，1<=x<=p-1,如果存在一个整数y，1<=y<=p-1,使得x=y2(mod p)。则称y是x 的模平方根）.