1

我的书（人工智能一种现代方法）说遗传算法从一组k随机生成的状态开始，称为种群。每个状态都表示为一个有限字母表上的字符串——最常见的是一个由 0 和 1 组成的字符串。例如，8 个皇后状态必须指定 8 个皇后的位置，每个皇后在一列 8 个方格中，因此需要 8 * log(2)8 = 24 位。或者，状态可以表示为 8 位数字，每个数字的范围从 1 到 8。

[ http://en.wikipedia.org/wiki/Eight_queens_puzzle ]

我不明白表达式 8 * log(2)8 = 24 bits ，为什么是 log2 ^ 8？这些 24 位应该是做什么用的？

4

2 回答 2

1

如果我们在维基百科页面上举第一个例子，解决方案可以编码为 [2,4,6,8,3,1,7,5] ：第一个数字给出 A 列中皇后的行号，第二个对于 B 列中的女王，依此类推。现在，我们将从 0 开始，而不是从 1 开始行编号。然后使用 [1,3,5,7,0,6,4] 对解决方案进行编码。任何位置都可以这样编码。
我们只有 0 到 7 之间的数字，如果我们用二进制 3 位 (=log2(8)) 编写它们就足够了：

000 -> 0
001 -> 1
...
110 -> 6
111 -> 7

一个位置可以使用 8 乘以 3 位进行编码，例如从 [1,3,5,7,2,0,6,4] 我们得到 [001,011,101,111,010,000,110,100] 或更简单地说 001011101111010000110100 : 24 位。
另一方面，位串 000010001011100101111110 解码为 000.010.001.011.100.101.111.110 然后 [0,2,1,3,4,5,7,6] 并给出 [1,3,2,4,5,8, 7] : A 列中的皇后在第 1 行，B 列中的皇后在第 3 行，依此类推。

于 2012-09-13T18:19:19.713 回答
0

存储可能的正方形（8 种可能性 0-7）所需的位数是 log(2)8。请注意，二进制的 111 是十进制的 7。您必须为 8 列指定正方形，因此需要 3 位 8 次

于 2012-09-13T18:19:33.740 回答